CS570
Analysis of Algorithms Summer 2008 Exam I
Name: _____________________ Student ID: _________________
____4:00 – 5:40 Section ____6:00 – 7:40 Section
Maximum
Received
Problem 1
20
Problem 2
20
Problem 3
10
Problem 4
15
Problem 5
10
Problem 6
10
Problem 7
15
Total
100
2 hr exam
Close book and notes
1) 20 pts
Mark the following statements as TRUE or FALSE. No need to provide any justification.
[ TRUE/FALSE ]
There exist a perfect matching and a corresponding preference list such that every man is part of an instability, and every woman is part of an instability.
FALSE
[ TRUE/FALSE ]
A greedy algorithm always returns the optimal solution.
FALSE
[ TRUE/FALSE ]
The function 100n + 3 is O(n^2) FALSE
[ TRUE/FALSE ]
You are given n elements to insert into an empty heap. You could directly call heap insert n times. Or you could first sort the elements and then call heap insert n times. In either case, the asymptotic time complexity is the same.
TRUE
[ TRUE/FALSE ]
If a problem can be solved correctly using the greedy strategy, there will only be one greedy choice (e.g. “choose the object with highest value to weight ratio”) for that problem that leads to the optimal solution.
FALSE
[ TRUE/FALSE ]
The Depth First Search algorithm can not be used to test whether a directed graph is strongly-connected.
FALSE
[ TRUE/FALSE ]
Consider an undirected graph G=(V, E) with non-negative edge weights. Suppose all edge weights are different. Then the edge of maximum weight can be in the minimum spanning tree.
TRUE
[ TRUE/FALSE ]
Consider a perfect matching S where Mike is matched to Susan. Suppose Mike prefers Winona to Rachel. Then the pair (Mike, Rachel) can never be an instability with respect to S.
FALSE
[ TRUE/FALSE ]
Consider an undirected graph G=(V, E). Suppose all edge weights are different. Then the shortest path from A to B must be unique.
FALSE
[ TRUE/FALSE ]
The number of elements in a heap must always be an integer power of 2. FALSE
2) 20 pts
Given two graphs G and G’ that have the same sets of vertices V and edges E, however different weight functions (W and W’ respectively) on their edges. Suppose for each graph the weights on the edges are distinct and satisfy the following relation: W'(e)=W(e)2 (Note: all edge weights in G and G’ are positive integers) for every edge e of E. Decide whether each of the following statements is true. Give either a short proof or a counter example.
a) The minimum spanning tree of G is the same as the minimum spanning tree of G’.
Solution
This statement is true
Now, since the edges costs are all distinct, the order of the sorted lists of the edges will be the same in G and G’. This is because if a > b , then a2>b2.
Now, if we run, Prims algorithm, it will consider the edges in the same order in the case of both G and G’. Therefore, since the structure of G and G’ are same and also the ordering of the edges (with respect to edge cost) is the same, the same MST will be produced.
b) For a pair of vertices a and b in V, a shortest path between them in G is also a shortest path in G’.
Solution
This statement is false. Hint : Pythagoras’s theorem
3) 10 pts
Prove or give a counterexample: An array that is sorted in ascending order is a min- heap.
Solution
Let’s assume that the statement is false. Suppose H is a binary tree for the array sorted in ascending order. By the statement, for every element v at a node i in H,
1. the element w at i’s parent satisfies key(w) ≤ key(v).
2. the element w at node i and its right sibling w’ satisfies key(w) ≤ key(w’).
Min-heap property: for every element v at a node i and the element w at i’s parent satisfies key(w) ≤ key(v).
H satisfies the min-heap property. Contradiction. Thus, the statement is true.
4) 15 pts
Let G = (V,E) be an undirected graph with maximum degree d. A coloring of G is an assignment to each vertex of G of a “color” such that adjacent vertices have distinct colors. Consider the greedy algorithm that colors as many vertices as possible with color “j” before moving to color “j+1.”
Prove or give a counterexample: This greedy algorithm never requires more than d+1 colors to color G.
Solution:
Proof: Let χ(G) denotes number of colors this greedy algorithm requires to color G. Prove by contradiction.
Assume there exists a graph G’ with maximum degree d such that χ(G’)>=d+2. Let v be the first vertex in G’ colored with color “d+2” by the algorithm. Hence all vertices adjacent to v must have used up color “1” through “d+1” (otherwise by the algorithm color “d+2” would not be used), which means v has at least d+1 adjacent vertices, that is, the degree of v is at least d+1. But the maximum degree in G’ is d. Contradiction. Therefore, this greedy algorithm never requires more than d+1 colors to color G.
5) 10 pts
You and your eight-year-old nephew Shrek decide to play a simple card game. At the
beginning of the game, the cards are dealt face up in a long row. Each card is worth a different number of points. After all the cards are dealt, you and Shrek take turns removing either the leftmost or rightmost card from the row, until all the cards are gone. At each turn, you can decide which of the two cards to take. The winner of the game is the player that has collected the most points when the game ends.
Having never taken an algorithms class, Shrek follows the obvious greedy strategy— when it’s his turn, Shrek always takes the card with the higher point value. Your task is to find a strategy that will beat Shrek whenever possible. (It might seem mean to beat up on a little kid like this, but Shrek absolutely hates it when grown-ups let him win.)
Prove that you should not also use the greedy strategy. That is, show that there is a game that you can win, but only if you do not follow the same greedy strategy as Shrek.
Solution
Let S be shrek’s total point and S’ be my total point at ith turn. Let pk, pk+1, pk+2, pk+3, pk+4, pk+5 be the sums of each pair of cards that remained, where k >= 1 and pk+2 >> pk+3 > pk+4 > pk+1 > pk+2. By the greedy strategy, the order that Shrek picks the pair of cards would be pk+4, pk+2, pk+1 and my order would be pk+3 then pk. The total point at the final turn is that S + pk+4 + pk+2 + pk+1 > S’ + pk+3 + pk. If I don’t use the greedy strategy, the result at the final turn would be S + pk+4 + pk+3 + pk+1 < S’ + pk + pk+2. Contradiction. Thus, the greedy strategy is not an optimal solution.
6) 10 pts
Arrange the following functions in increasing order of asymptotic complexity. If f(n)=Ө(g(n)) then put f=g. Else, if f(n)=O(g(n)), put f < g.
4n2, log2(n), 20n, 2, log3(n), nn, 3n, nlog(n), 2n, 2n+1, log(n!)
Solution:2
G is a bipartite graph => it can not contain an odd cycle => all the cycle(s) have even number of nodes=> all the cycle(s) have length 2n (since edge weight is 1)
Take a smallest loop with 2m nodes and length 2m in G, then any pair of nodes (u,v) that are farthest away have two paths with equal length m. Also, since the loop is smallest, there doesn’t not exist any path