xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-CS330

时间：2021-05-02

Spring 2021 CS330 Midterm 2

March 17, 2021

Instructions

• This exam is open book. You may consult your textbook, notes, slides, or other course

materials, but no external sources.

• You may reference and use anything without having to prove or explain in detail (e.g.,

algorithms, proofs, running time) discussed in lecture, lab or the textbook.

• Absolutely no collaboration is allowed. You cannot discuss the contents of this

exam with anyone except the instructors.

• The exam consists of 3 questions. With question 1 consisting of subproblems a - e.

• The exam has quite a few questions. Don’t get stuck on one, if it takes you a long time,

move on to the next question and you can come back to it later. Also, the deadline

is a hard deadline. It’s better to submit a not fully completed exam, than miss your

deadline.

• You can write your answers by hand on paper, on a tablet, or you can type your

solutions. Make sure to clearly write which problem you are answering and also label

your answers with the problem number and the problem part at the top of each page

when you upload to Gradescope. If we cannot find or read your answers they will not

be graded.

• From the time you download this pdf you have exactly 120 minutes time to upload

your final pdf to Gradescope. The system is set not to accept exams after your time

has expired.

• If you have questions, you may ask them via private post on Piazza or via the Zoom

link. (This link is also posted on Piazza in @309)

1

Problem 1 Short answers (8 points)

(a) (2 points) For each of the below determine whether the complexity is Θ(n2). Write

True or False, no explanation needed.

(a) Smallest complexity of an algorithm which finds the largest and smallest element

in a list.

(b) Complexity of Dijkstra’s algorithm (with the implementation discussed in class).

(c) Smallest complexity of finding a minimum weight spanning tree in a graph that

has n vertices and 3n many edges. (Answer this question with regard to the

algorithms and implementations that we studied in class.)

(d) Let G(U,W,E) be a complete bipartite graph. Suppose that |U | = |W | = √n.

The number of edges in G is Θ(n2).

Here is the definition of a complete bipartite graph: the nodes in G are divided in

to two sets U and W that form a partition, i.e. each node is assigned to exactly

one of the two. There is an edge between every pair of nodes u,w where u ∈ U

and w ∈ W , but there are NO edges between pairs of nodes in the same set.

(b) (3 points) Consider the graph G below. Note, that this graph is undirected. Answer

both parts (a.) and (b.). In both parts there may be more than one correct answer,

and you should list all the answers that are correct. No explanation needed.

a

b

c

d e

f

g

h

(a) Which of the following is NOT a possible order in which vertices of G are dis-

covered when a depth-first search (DFS) on G is done? Assume that the search

starts at vertex a.

(A) abcdefgh (B) acfghedb (C) abceghedb

(D) acefhgbd (E) None of them

(b) Which of the following ARE possible orders in which the vertices of G are dis-

covered when a breadth-first search (BFS) on G is done? Assume that the search

starts at vertex f .

(A) fchgaedb (B) fhgecabd (C) fgchabd

(D) fghcaedb (E) chgebda (F) None of them

2

(c) ( 1 point) Suppose you are given an undirected, connected graph G(V,E). Suppose

you run DFS on this graph started from a randomly chosen node. How can you use the

outcome of DFS to assign a direction to each edge, so that the resulting directed graph

is a DAG? Give a very short explanation (you should be able to do this in one or two

sentences). You don’t need to describe an efficient implementation of your algorithm

or prove its correctness, only state your approach clearly.

(d) (1 point) Given a weighted graph where weights of all edges are unique (no two edge

have same weights), there is always a unique shortest path from a source to destination

in such a graph. Explain why or provide a counter example.

(e) (1 point) Let G = (V,E, c) be an undirected graph with costs c(e) on each edge e

and let T be a minimum weight spanning tree on G. Suppose the cost of each edge is

increased by 1. Is T still an MST? Explain why or provide a counter example.

3

Problem 2 (7 points)

Exam 2 In the Interval Partitioning problem we are given a set of n requests, where the

ith request starts at time si and finishes at time fi, find the minimum number of resources

needed to schedule all requests so that no two requests are assigned to the same resource at

the same time.

We propose the Earliest-Finish-Time-First (EFTF) algorithm to solve this problem. It

works as follows; first, we sort the requests in ascending order of finish time. Then we

consider requests in this order. We assign a request to one of the resources it’s compatible

with at random. If a request is incompatible with all resources being used, then we choose

a new resource to use for this request.

(a) (3 points) Give an example of jobs, such that the EFTF algorithm does not yield an

optimal solution (that is a minimum size list of resources).

Note: For this part of the problem it is sufficient to draw a picture of the intervals

(jobs) that are in your example as was done in our textbook. You should number the

jobs and use this numbering to specify which jobs are scheduled using ESTF as well

as a list of jobs which are optimal for this problem.

(b) (4 points) Prove that when all jobs are of equal length, then the Earliest-Finish-Time-

First algorithm does yield an optimal solution. (You may reference proofs from class

if you think they are relevant.)

4

Problem 3 (7 points)

A graph G(V,E) is called BIPARTITE if V can be decomposed into two disjoint sets U

and W such that every edge in E joins a vertex in U to one in W . (Thus there is no edge

between two nodes in the same set.) You can see an example in the picture on the right.

(a) (3 points) Observe the two graphs depicted in the picture. If you look at it carefully,

you can see that the two graphs are identical, just drawn in a different layout. You

can also clearly see from the drawing on the right that it’s bipartite.

Suppose we have a connected graph G(V,E) that we know to be bipartite, but don’t

know which of the two sets U and W each node belongs to. (e.g. you would see

something like the drawing on the left.) Design a simple greedy algorithm that assigns

the nodes to the two sets. (Hint: start from an arbitrary node v and assign it to set

U . Then consider the neighbors of v. ) Describe your algorithm and give a short

explanation why it is correct in assigning the vertices (we are not expecting a rigorous

formal proof here.)

(b) ( 1 point) Analyze the algorithm’s running time assuming it’s stored in an adjacency

list.

(c) (3 points) A cycle in a graph is even length if it consists of even number of nodes (and

of course the same number of edges). Based on the algorithm you designed in (a.),

prove that any cycle in a bipartite graph has to be of even length. (Hint: think of

which sets U or W each subsequent node along the cycle is in.)

5

学霸联盟

March 17, 2021

Instructions

• This exam is open book. You may consult your textbook, notes, slides, or other course

materials, but no external sources.

• You may reference and use anything without having to prove or explain in detail (e.g.,

algorithms, proofs, running time) discussed in lecture, lab or the textbook.

• Absolutely no collaboration is allowed. You cannot discuss the contents of this

exam with anyone except the instructors.

• The exam consists of 3 questions. With question 1 consisting of subproblems a - e.

• The exam has quite a few questions. Don’t get stuck on one, if it takes you a long time,

move on to the next question and you can come back to it later. Also, the deadline

is a hard deadline. It’s better to submit a not fully completed exam, than miss your

deadline.

• You can write your answers by hand on paper, on a tablet, or you can type your

solutions. Make sure to clearly write which problem you are answering and also label

your answers with the problem number and the problem part at the top of each page

when you upload to Gradescope. If we cannot find or read your answers they will not

be graded.

• From the time you download this pdf you have exactly 120 minutes time to upload

your final pdf to Gradescope. The system is set not to accept exams after your time

has expired.

• If you have questions, you may ask them via private post on Piazza or via the Zoom

link. (This link is also posted on Piazza in @309)

1

Problem 1 Short answers (8 points)

(a) (2 points) For each of the below determine whether the complexity is Θ(n2). Write

True or False, no explanation needed.

(a) Smallest complexity of an algorithm which finds the largest and smallest element

in a list.

(b) Complexity of Dijkstra’s algorithm (with the implementation discussed in class).

(c) Smallest complexity of finding a minimum weight spanning tree in a graph that

has n vertices and 3n many edges. (Answer this question with regard to the

algorithms and implementations that we studied in class.)

(d) Let G(U,W,E) be a complete bipartite graph. Suppose that |U | = |W | = √n.

The number of edges in G is Θ(n2).

Here is the definition of a complete bipartite graph: the nodes in G are divided in

to two sets U and W that form a partition, i.e. each node is assigned to exactly

one of the two. There is an edge between every pair of nodes u,w where u ∈ U

and w ∈ W , but there are NO edges between pairs of nodes in the same set.

(b) (3 points) Consider the graph G below. Note, that this graph is undirected. Answer

both parts (a.) and (b.). In both parts there may be more than one correct answer,

and you should list all the answers that are correct. No explanation needed.

a

b

c

d e

f

g

h

(a) Which of the following is NOT a possible order in which vertices of G are dis-

covered when a depth-first search (DFS) on G is done? Assume that the search

starts at vertex a.

(A) abcdefgh (B) acfghedb (C) abceghedb

(D) acefhgbd (E) None of them

(b) Which of the following ARE possible orders in which the vertices of G are dis-

covered when a breadth-first search (BFS) on G is done? Assume that the search

starts at vertex f .

(A) fchgaedb (B) fhgecabd (C) fgchabd

(D) fghcaedb (E) chgebda (F) None of them

2

(c) ( 1 point) Suppose you are given an undirected, connected graph G(V,E). Suppose

you run DFS on this graph started from a randomly chosen node. How can you use the

outcome of DFS to assign a direction to each edge, so that the resulting directed graph

is a DAG? Give a very short explanation (you should be able to do this in one or two

sentences). You don’t need to describe an efficient implementation of your algorithm

or prove its correctness, only state your approach clearly.

(d) (1 point) Given a weighted graph where weights of all edges are unique (no two edge

have same weights), there is always a unique shortest path from a source to destination

in such a graph. Explain why or provide a counter example.

(e) (1 point) Let G = (V,E, c) be an undirected graph with costs c(e) on each edge e

and let T be a minimum weight spanning tree on G. Suppose the cost of each edge is

increased by 1. Is T still an MST? Explain why or provide a counter example.

3

Problem 2 (7 points)

Exam 2 In the Interval Partitioning problem we are given a set of n requests, where the

ith request starts at time si and finishes at time fi, find the minimum number of resources

needed to schedule all requests so that no two requests are assigned to the same resource at

the same time.

We propose the Earliest-Finish-Time-First (EFTF) algorithm to solve this problem. It

works as follows; first, we sort the requests in ascending order of finish time. Then we

consider requests in this order. We assign a request to one of the resources it’s compatible

with at random. If a request is incompatible with all resources being used, then we choose

a new resource to use for this request.

(a) (3 points) Give an example of jobs, such that the EFTF algorithm does not yield an

optimal solution (that is a minimum size list of resources).

Note: For this part of the problem it is sufficient to draw a picture of the intervals

(jobs) that are in your example as was done in our textbook. You should number the

jobs and use this numbering to specify which jobs are scheduled using ESTF as well

as a list of jobs which are optimal for this problem.

(b) (4 points) Prove that when all jobs are of equal length, then the Earliest-Finish-Time-

First algorithm does yield an optimal solution. (You may reference proofs from class

if you think they are relevant.)

4

Problem 3 (7 points)

A graph G(V,E) is called BIPARTITE if V can be decomposed into two disjoint sets U

and W such that every edge in E joins a vertex in U to one in W . (Thus there is no edge

between two nodes in the same set.) You can see an example in the picture on the right.

(a) (3 points) Observe the two graphs depicted in the picture. If you look at it carefully,

you can see that the two graphs are identical, just drawn in a different layout. You

can also clearly see from the drawing on the right that it’s bipartite.

Suppose we have a connected graph G(V,E) that we know to be bipartite, but don’t

know which of the two sets U and W each node belongs to. (e.g. you would see

something like the drawing on the left.) Design a simple greedy algorithm that assigns

the nodes to the two sets. (Hint: start from an arbitrary node v and assign it to set

U . Then consider the neighbors of v. ) Describe your algorithm and give a short

explanation why it is correct in assigning the vertices (we are not expecting a rigorous

formal proof here.)

(b) ( 1 point) Analyze the algorithm’s running time assuming it’s stored in an adjacency

list.

(c) (3 points) A cycle in a graph is even length if it consists of even number of nodes (and

of course the same number of edges). Based on the algorithm you designed in (a.),

prove that any cycle in a bipartite graph has to be of even length. (Hint: think of

which sets U or W each subsequent node along the cycle is in.)

5

学霸联盟