DSC 40B - Final Exam
August 3, 2019
Name: SOLUTIONS
PID:
By signing below, you are agreeing that you will behave honestly and fairly during and after
this exam. You should not discuss any part of this exam with anyone enrolled in the course
who has not yet taken the exam (this includes posting questions about the exam on Piazza!)
Signature:
Name of student to your left: Name of student to your right:
(Write “N/A” if a wall/aisle is to your left/right.)
Instructions:
• Write your solutions to the following problems in the boxes provided.
• The last two pages are scratch paper; you may remove these.
• No calculators are permitted, but a cheat sheet is.
• Write your name or PID at the top of each sheet in the space provided.
Tips:
• Show your work to receive partial credit.
• Look through the entire exam before starting.
• Make good use of all assumptions given to you.
(Please do not open your exam until instructed to do so.)
Problem 1. (16 points)
For the following problems, recall that (u; v) is a tree edge if node v is discovered while
visiting node u during a breadth-first or depth-first search. Assume the convention that a
node’s neighbors are produced in ascending order by label.
a) Suppose a breadth-first search is performed on the graph below, starting at node 1.
Mark every BFS tree edge with a bold arrow emanating from the predecessor.
1 2 3
4 5 6
7 8 9
b) Suppose a depth-first search is performed on the graph below, starting at node 1. Mark
every DFS tree edge with a bold arrow emanating from the predecessor.
1 2 3
4 5 6
7 8 9
2
PID or Name:
c) Fill in the table below so that it contains the start and finish times of each node after
a DFS is performed on the above graph using node 1 as the source. Begin your start
times with 1.
Node Start Finish
1 1 18
2 2 17
3 3 16
4 6 7
5 5 14
6 4 15
7 8 9
8 10 13
9 11 12
3
Problem 2. (24 points)
For each of the following statements write T if the statement is true, and F if the statement
is false.
a) T If f1(n) = O(g1(n)) and f2(n) = O(g2(n)) then f1(n)f2(n) = O (g1(n) g2(n)).
b) F
Because mergesort takes (n log n) time compared to selection sort’s (n2),
mergesort(arr) will execute in less time than selection_sort(arr), no mat-
ter what the input arr is.
Solution: While mergesort has better asymptotic time complexity, this only
means that mergesort is faster for n large enough. In fact, for small inputs, selection
sort is typically a little faster.
c) T If the input graph G = (V;E) is a tree, the time complexity of depth-firstsearch is (V ).
Solution: In general, the time complexity of DFS is (V + E). If G is a tree,
jEj = jV j 1, so the time complexity becomes (V + (V 1)) = (V ).
d) T
If a graph G has two connected components, there must exist a pair of distinct
nodes u and v such that adding the edge (u; v) to G would result in a graph
with one connected component.
e) T An undirected graph with n nodes can have at most n(n 1)=2 edges.
f) T
Suppose that T is a minimum spanning tree of a weighted graph G, and G0
is the weighted graph obtained by increasing the weight of each edge in G by
exactly one. Then T is also a minimum spanning tree of G0.
Solution: Increasing the weight of each edge by one increases the total
weight of a spanning tree by jEj. Since the total weight of each spanning
tree is increased by the same amount, an MST of the original graph is still
an MST of the new graph.
g) T
Suppose that a breadth-first search is run with node u as the source. Let v
and w be two nodes. If the shortest path from u to v is (strictly) shorter than
the shortest path from u to w, then u is added to the queue before w.
4
PID or Name:
h) T Suppose a full DFS is used to compute finish times. If v is reachable from u, itis possible for the finish time of v to be larger than the finish time of node u.
Solution: Consider this graph:
v w u
Start a DFS at node w. The DFS will then visit node u, then node v. The finish
time of node u will be 2, while the finish time of node v will be 5. But v is reachable
from u.
5
Optionally provide reasoning here to earn credit if your above answer(s) is (are) incorrect:
6
PID or Name:
Problem 3. (20 points)
Here is a simple way of clustering a weighted, undirected graph G = (V;E; !). Given a real
number t, place two nodes u and v in the same cluster if (and only if) there is a path between
u and v along which every edge has weight t. For instance, consider the graph below:
1
2
3
4
5
6
3.41.3
2.7 0.3
0.90.5 0.72.1
If t = 1, there are three clusters: f1; 2g, f4; 5; 6g and f3g. If t = 2, there are two clusters:
f1; 3g and f4; 5; 6g. And if t = 3, there is one cluster containing all of the nodes.
Design an algorithm which returns the clusters given an input graph, a weight function,
weights, and a threshold t. Your algorithm should take (V + E) time. To receive full
credit, your algorithm should not modify the graph or create a copy of it. Provide pseudocode
(or Python).
7
Solution: A BFS or DFS can be used to find the clusters. An unmodified BFS started
at node u will find all nodes reachable from u. We wish to find all nodes reachable from
u along paths whose edges have weight t. One simple way to do this is to delete all
edges of weight > t from the graph and run a full BFS, but the problem asked us not to
modify the graph or create a copy of it. We can achieve the same effect by having BFS
“ignore” the edges whose weight is above the threshold, essentially acting as if they are
deleted.
1 def cluster(graph, weights, t):
2 status = {'undiscovered' for node in graph.nodes}
3 clusters = []
4 for node in graph.nodes:
5 if status[node] == 'undiscovered':
6 cluster = bfs_cluster(graph, node, weights, status, t)
7 clusters.append(cluster)
8
9 def bfs_connected_components_with_threshold(
10 graph, source, weights, status, t):
11 cluster = [source]
12 pending = deque([source])
13 status[source] = 'pending']
14 while pending:
15 u = pending.popleft()
16 for v in graph.neighbors(u):
17 if status[v] == 'undiscovered' and weight(u, v) <= t:
18 pending.append(v)
19 status[v] = 'pending'
20 cluster.append(v)
21 status[u] = 'visited'
22 return cluster
This is essentially the same code as in full BFS, but a node v is “discovered” and added
to the pending queue only if the edge from the potential predecessor to v has weight t.
8
PID or Name:
Problem 4. (15 points)
Describe an algorithm for computing a maximum spanning tree. A maximum spanning tree
of a weighted graph G is a spanning tree of G with largest total edge weight. You do not need
to provide pseudocode, and you can use the algorithms discussed in class without needing to
write their code. Unlike the previous problem, you may modify the graph or create a copy
of it.
Solution: Create a copy G0 of the graph, G, in which the weight of each edge is the
negative of the original edge weight. A minimum spanning tree of G0 will be a maximum
spanning tree of G. Therefore, a maximum spanning tree of G is given by running
Kruskal’s algorithm on G0.
Or: run Kruskal’s in “reverse” by sorting the edges in descending order by weight, and
adding an edge to the tree if it connects two previously disconnected nodes.
9
Problem 5. (20 points)
For each of the following, state the most precise possible bound on the time complexity using
asymptotic notation.
a) What is the time complexity of this code? State your answer in terms of n.
for i in range(n):
for j in range(i, n):
print('Hello')
(n2)
b) What is the time complexity of this code? State your answer in terms of n.
def foo(n):
if n == 1:
return 2
return foo(n-1)*foo(n-1)
(2n)
c) What is the time complexity of this code? State your answer in terms of n.
def bar(n):
x = 1
total = 0
while x < n:
total += x
x = 2 * x
(log n)
d) The time complexity of full breadth-first search when run on a graph represented using
an adjacency matrix. State your answer in terms of the number of nodes jV j and/or
the number of edges, jEj.
(V 2)
10
PID or Name:
Problem 6. (20 points)
In the following problem, we will use a slight variant of the merge function seen in mergesort.
It accepts two sorted lists, left and right, and merges them into one sorted list. The only
difference between this and the merge used in mergesort is that this function returns its
result in a new array rather than modifying an input array.
def merge(left, right):
m = len(left) + len(right)
output = []
left.append(float('inf'))
right.append(float('inf'))
for i in range(m):
print('Hello')
if left[0] < right[0]:
output.append(left.pop(0))
else:
output.append(right.pop(0))
return output
Suppose collection is a list of k sorted lists, each of them containing n elements. The code
below performs a k-way merge by combining the k sorted lists into one large sorted list with
k n elements:
def k_way_merge(collection):
"""Assume collection is not empty."""
k = len(collection)
n = len(collection[0])
left = collection[0]
for i in range(1, k):
right = collection[i]
left = merge(left, right)
11
a) Fill in the box so that the following loop invariant is true: After the th iteration of
the for-loop in k_way_merge, left contains ( + 1) n elements.
b) Observe that the merge function contains a line which prints 'Hello'. Exactly how
many lines are printed in total during one call to k_way_merge? State your answer in
terms of k and n.
Solution: When merge(left, right) is called, it prints a number of lines equal
to len(left) + len(right). On the first iteration of the for-loop, merge is called
with two arrays of size n, and therefore prints 2n lines.
On the second iteration of the for-loop, left contains 2n elements, while right
contains n elements. Hence merge prints 3n lines.
On the third iteration, left contains 3n elements, and right contains n elements.
Hence 4n lines are printed.
On the th iteration of the for-loop, it is apparently the case that n + 1 lines
are printed.
The for-loop makes k 1 iterations, and so the total number of printed lines is:
2n+ 3n+ 4n+ : : :+ (k 1 + 1)n = 2n+ 3n+ : : :+ k n
= n(2 + 3 + : : :+ k)
The sum of 2 + 3 + : : :+ k is k(k + 1)=2 1. Hence the answer is
n [k(k + 1)=2 1] = n k(k + 1) n
2
Before turning in your exam, please check that your name is on every page.
12