Description
1. [10 pts] Explain why O(log(E) = O(log(V)), but O(E) is not necessarily O(V).
2. [6 pts] The following courses: LA15, LA16, LA22, LA31, LA32, LA126,
LA127, LA141, and LA169 have these prerequisites.
LA15: (none)
LA16: LA15
LA22: (none)
LA31: LA15
LA32: LA16, LA31
LA126: LA22, LA32
LA127: LA16
LA141: LA22, LA16
LA169: LA32
Find a viable course plan that meets the prerequisites.
3. [6 pts] Here is a graph given by the adjacency list:
vertex adjacent vertices
0: [1, 2, 3]
1: [0, 2, 3]
2: [0, 1, 3]
3: [0, 1, 2, 5]
4: [5, 6, 7]
5: [3, 4, 6]
6: [4, 5, 7]
7: [4, 6]
You always get the adjacent list for a node in the shown order.
Problem: Starting at node 0, Give the order that DFS visits the nodes
4. [6 pts] For the same graph as problem 3, starting at node 0, give the order
that BFS visits the nodes.
5. [15 pts] Recall the unit on Priority Queues. Give Python code for the
arbitrary update of priority for any element. Your algorithm should be able to
update any element of a priority queue in O(log(N)), where N is the number of
items in the priority queue
6. [10 pts] Modify Dijkstra’s Algorithm as given in the notes to actully give a
shortest path, not just the distance. Your Modified Dijkstra’s Algorithm should
be in Python.
7. [13 pts] Give a counterexample of what goes wrong when Dijkstra
encounters negative edge weights
(even with no negative cycles)
8. [13 pts] Give an example to show that adding a positive offset to all
negative edge weights will not succeed in computing shortest paths
9. [15 pts] In a graph G, a vertex is a universal sink if it has in-degree |V|-1, and
out-degree 0. Give an algorithm that finds a universal sink if there is 1, or
reports that there is no such node. Your algorithm, however, must work with
the ADJACENCY MATRIX representation.
The complexity should be O(|V|).
10. [6 pts] Give a step-by-step execution trace of Kruskal’s algorithm on the
following graph:
A,C 7
A,D 5
B,C 8
B,E 4
C,D 9
C,E 10
D,E 15
D,F 6
E,F 12
G,F 11
G.E 13
