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



















































































































学霸联盟