Exam I Review Session
DFS/BFS
Danyong Zhao 5:00~5:50 PM
Question 1/4
Given an undirected graph G = (V, E) and a particular edge e ε E, determines whether G has a cycle containing e. The running time should be bounded by
O(|V | + |E|).
Let s and t denote the ending nodes of the edge e.Delete e from G to obtain a new graph G’, run the DFS or BFS algorithm starting from s, if t can be traversed, then G has a cycle containing e, otherwise G does not have such a cycle.
In the worst case, all the edges and nodes are traversed,
resulting in O(|V | + |E|) time; or you can say the running time of DFS or BFS is O(|V | + |E|).
Question 2/4
We are given a graph G = (V; E) with uniform cost edges and two vertices s and t within G. We are told that the length of the shortest path from s to t is more than n/2 (where n is the number of vertices within G). Give a linear time algorithm to find a vertex v (other than s and t) such that every path from s to t contains v
Algorithm:
a)Based on the uniform edge cost assumption, we run BFS from s and find the shortest path from s to t.
b) Since the shortest distance from s to t is more than n/2, other than the s layer and t’s belonged layer in the BFS tree, there must be at least one layer crossed by the shortest path that has only 1 vertex. Choose this single vertex that forms a layer by itself, and this vertex is a valid one we want.
c) Running BFS and searching takes linear time in total.
Question 3/4
Suppose a CS curriculum consists of n courses, all of them mandatory. The prerequisite graph G has a node for each course, and an edge from course v to course w if and only if v is a prerequisite for w. Find an algorithm that works directly with this graph representation, and computes the minimum number of semesters necessary to complete the curriculum (assume that a student can take any number of courses in one semester). The running time of your algorithm should be linear.
First do a BFS/DFS to make sure that the graph is a directed acyclic graph (DAG) (otherwise, the coursework cannot be completed in finitely many semesters since there would be a cycle of prerequisite dependencies).
Do a topological sort, let the resulting set of vertices be {v1,v2,v3,…,vn} in O(|V|+|E|) time.
If vi does not have an incoming edge, then set L(vi)=0. If vi has an incoming edge, then L(vi) = max ( L(vk) + 1) where the maximum is taken over all vk such that (vk,vi) is present in the graph.
The number of semesters required then turns out to be 1 + max(L(v)).
Question 4/4
You are given a weighted directed graph G =(V,E,w) and the shortest path distances δ(s, u) from a source vertex s to every other vertex in G. However, you are not given π(u) (the predecessor pointers). With this information, give an algorithm to find a shortest path from s to a given vertex t in O(|V| + |E|) time.
Remove edges ei,j that wi,j ≠ |δ(s, i)-δ(s, j)| Using DFS/BFS to find a path from s to t
Greedy Algorithms
Ta-Yang Wang 5:50~6:40 PM
Question 1/3
Greedy Algorithms Q1
Given two lists of positive integers, A and B, each of size n. Design an algorithm to rearrange their elements such that
is maximized. Prove that the solution is optimal.
Greedy Algorithms Q1
● Example
○ A = [5, 8, 6]
○ B = [4, 3, 2]
● The optimal solution is 52 ‧ 63 ‧ 84
Greedy Algorithms Q1
● Algorithm
○ Sort both A and B in ascending order.
● Proof of correctness (sketch)
○ Claim: swapping two items of A decreases the value.
■ Say swapping Ai and Aj where i < j, then
Question 2/3
Greedy Algorithms Q2
Given n files of size s1, ..., sn (unsorted). One may merge any two file i, j into a file of size si + sj in total time si + sj at a time. Design an algorithm to minimize the amount of time needed for merging all n files. Prove that the solution is optimal.
Greedy Algorithms Q2
● Example
○ 6 files of size 2, 3, 4, 5, 6, 7
● Solution
○ 2+3 = 5
○ 4+5 = 9
○ 5+6 = 11
○ 7+9 = 16
○ 11+16 = 27
○ Total time = 5+9+11+16+27 = 68
Greedy Algorithms Q2
● Algorithm
○ Merge together the two smallest-size files.
● Proof of correctness
○ View the solution as a binary tree, then the total
contribution of a file i is its depth in the tree times si.
○ Suppose there is an optimal solution such that the two
smallest-size items p and q are not merged together, then swapping them with p and q will decrease the amount of time.
Question 3/3
Greedy Algorithms Q3
Suppose you are organizing a company party. The corporation has a hierarchical ranking structure; that is, the CEO is the root node of the hierarchy tree, and the CEO's immediate subordinates are the children of the root node, and so on in this fashion. To keep the party fun for all involved, you will not invite any employee whose immediate superior is invited. Every employee is equally valued, so we would like to maximize the total number of employees invited.
Greedy Algorithms Q3
Assume every employee has at most one immediate superior. Design an algorithm to maximize the total number of employees invited. Prove that the solution is optimal.
Greedy Algorithms Q3 ● Example
Greedy Algorithms Q3
● Algorithm
○ Invite every leaf node; remove them and parents from
the tree, and repeat recursively. ● Proof of correctness
○ Claim: Every optimal solution missing any leaf can be made to include that leaf without decreasing the number of employees.
■ For any leaf, either it or its parent must be invited. Otherwise it is not an optimal solution
Shortest Path & MST
Wenxuan Zhou 6:40 ~ 7:20 PM
Question 1/4
Shortest Path 1
One cow from each of N farms is going to attend the big cow party to be held at farm f. A total of M unidirectional (one-way roads) connects pairs of farms; road i requires t_i units of time to traverse. (assume the graph is connected)
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way. Of all the cows, design an algorithm longest amount of time a cow must spend walking to the party and back?
Shortest Path 1
1. Reverse all roads and run Dijkstra from farm f to get distance D_if.
2. Run Dijkstra from farm f to get distance D_fi.
3. Return max_i (D_if + D_fi) as the result.
Question 2/4
Shortest Path 2
Given n points, m undirected edges, each edge has length d and cost p (d, p > 0). Return the shortest distance and its cost from start point s to all other points. If the shortest path has multiple routes, design an algorithm to return the one that has the least cost.
Shortest Path 2
Modify the Dijkstra algorithm by adding a new key “cost” to the priority queue. Node u < node v if (1) d(u) < d(v) and (2) d(u) == d(v) and cost(u) <= cost(v) Update step:
If d(u) > d(v) + le or (d(u) == d(v) + le and cost(u) > cost(v) + cost_e) then Decrease_key(Q, u, d(v) + le, cost(v) + cost_e)
Question 3/4
MST 1
T/F If the weight of each edge in a connected graph is distinct, then the graph contains exactly one unique minimum spanning tree.
MST 1
True. Proof: Suppose there are two MSTs T1 and T2 of G, let E be the set of edges that is in either T1 or T2 but not both, let e be the minimum edge in E.
Suppose e is not in T2. Adding e to T2 creates a cycle. Then in this cycle, at least one edge (except e), say f, is not in T1. By our choice of e, w(e) <= w(f). Since all edges have distinct weights, w(e) < w(f). Replacing f with e results in a new spanning tree with less weight than T1 and T2. Contradiction!
Thus, the MST must be unique if the weights of edges in a connected graph are distinct.
Question 4/4
MST 2
There are n cities and existing roads R_u. The government plans to build more roads such that any pair of cities are connected by roads. The candidate roads are R_p = {r_1, r_2, ..., r_m} and each road has a cost (cost > 0). Design an algorithm to decide the roads to be built such that all cities are connected by road(s) and the cost is minimized.
MST 2
Construct a graph with n nodes.
1. Add R_u to the graph and set the edge weights to 0.
2. Add R_p to the graph and set the edge weights to the cost of construction.
3. Run MST, find roads that in R_p.
True/False
Di Huang 7:20 ~ 8:10 PM
True/False
1. The shortest path between two points in a graph could change if the weight of each edge is increased by an identical number.
2. In a simple, undirected, connected, weighted graph with at least three vertices and unique edge weights, the heaviest edge in the graph never belongs to the minimum spanning tree.
True/False
1. The shortest path between two points in a graph could change if the weight of each edge is increased by an identical number.
True. For example, AB = 2, BC = 2, AC = 4.5, the shortest path from A to C is AB+BC=4; add 2 to each edge, AB = 4, BC = 4, AC = 6.5, the shortest path from A to C is AC=6.5
2. In a simple, undirected, connected, weighted graph with at least three vertices and unique edge weights, the heaviest edge in the graph never belongs to the minimum spanning tree.
False. If the heaviest edge in the graph is the only edge connecting some vertex to the rest of the graph, then it must be in every minimum spanning tree.
True/False
3. Algorithm A has a running time of Ө(n2) and algorithm B has a running time of Ө(n log n). From this we can conclude that A can never run faster than B on the same input set.
4. In a divide & conquer algorithm, the size of each sub-problem must be at most half the size of the original problem.
True/False
3. Algorithm A has a running time of Ө(n2) and algorithm B has a running time of Ө(n log n). From this we can conclude that A can never run faster than B on the same input set.
False. For example, n^2 vs 1000*n*log(n) for n =10
4. In a divide & conquer algorithm, the size of each sub-problem must be at most half the size of the original problem.
False. Can be larger than half the size
True/False
5. If every node in a binary tree has either 0 or 2 children, then the height of the tree is Θ(log n).
6. Let G be a graph with a negative cycle. Then there is no pair of vertices that has a finite cost shortest path
True/False
5. If every node in a binary tree has either 0 or 2 children, then the height of the tree is Θ(log n).
False. For example, the height is Θ(n)
6. Let G be a graph with a negative cycle. Then there is no pair of vertices that has a finite cost shortest path
False. Consider a graph that has an edge (s, t) with cost 1 and a disjoint negative cycle. In this graph the shortest s − t path has cost 1
True/False
7. If a connected undirected graph G has the same weights for every edge, then every spanning tree of G is a minimum spanning tree, but such a spanning tree cannot be found in linear time.
8. The total amortized cost of a sequence of n operations (i.e., the sum over all operations, of the amortized cost per operation) gives a lower bound on the total actual cost of the sequence.
True/False
7. If a connected undirected graph G has the same weights for every edge, then every spanning tree of G is a minimum spanning tree, but such a spanning tree cannot be found in linear time.
False. Just use BFS.
8. The total amortized cost of a sequence of n operations (i.e., the sum over all operations, of the amortized cost per operation) gives a lower bound on the total actual cost of the sequence.
False. The reason is that with amortized cost analysis to get to the upper bound on the actual cost, we need to consider a “worst case sequence of n operations” not just any sequence of n operations.