CS570
Analysis of Algorithms Spring 2007 Exam 1
Name: _____________________ Student ID: _________________
Maximum
Received
Problem 1
14
Problem 2
6
Problem 3
15
Problem 4
20
Problem 5
15
Problem 6
20
Problem 7
10
Note: The exam is closed book closed notes.
1) 14 pts
Mark the following statements as TRUE or FALSE. No need to provide any justification.
[ TRUE/FALSE ]False
3n2n3n Functionf(n)=5n 2 +6n 3 isO(n 2 ).
[ TRUE/FALSE ] True 3
nlog n is NOT O(nlogn)
[ TRUE/FALSE ] True
In an undirected graph, the shortest path between two nodes lies on some minimum spanning tree.
[ TRUE/FALSE ] False
Max base heap can be converted into Min based heap by reversing the order of the elements in the heap array.
[ TRUE/FALSE ] False
Kruskal’s algorithm for finding a MST of a weighted, undirected graph is a form of a dynamic programming technique.
[ TRUE/FALSE ] True
In the case of applying Dijkstra’s algorithm for dense graph, Fibbonacci implementation is the best one among Binary, Binomial, and Fibbonacci.
[ TRUE/FALSE ] False
If all of the weights from a connected and weighted graph are distinct, then distinct spanning trees of the graph have distinct weights.
2) 6pts
What is the worst-case complexity of the each of the following code fragments?
a) for(i=0;i<2N;i++){ sequence of statements
}
for (j = 0; j < 3M; j++) {
sequence of statements }
O(M+N)
b) for(i=0;i
⇔bj logai +bi logaj >bj logaj +bi logai
which contradicts that {a1,…,an} and {b1,…bn} is an optimal solution
Running time: Sorting takes O(nlog n). Hence the running time of our algorithm is O(nlog n)
5) 15 pts
Given a connected graph G = (V,E) with positive edge weights and two nodes s,t in V, prove or disprove:
a. If all edge weights are unique, then there is a single shortest path between any
two nodes in V.
b. If each edge’s weight is increased by k, the shortest path cost will increase by
a multiple of k.
c. If the weight of some edge e decreases by k, then the shortest path cost will
decrease by at most k.
a) False. Counter Example: (s,a) with weight 1, (a,t) with weight 2 and (s,t) with weight 3. There are two shortest path from s to t though the edge weights are unique.
b) False.Example:supposetheshortestpathstconsistoftwoedges,each with cost 1, and there is also an edge e=(s,t) in G with cost(e)=3. If now we increase the cost of each edge by 2, e will become the shortest path (with the total cost of 5).
c) True. For any two nodes s,t, assume that P1,…,Pk are all the paths from s to t. If e belongs to Pi then the path cost decrease by k, otherwise the path cost unchanged. Hence all paths from s to t will decrease by at most k. As shortest path is among them, then the shortest path cost will decrease by at most k.
Grading policy: 5 points for each item. 2 points for TRUE/FALSE part and 3 points for prove/disprove part.
6) 20 pts
Sam is shocked to find out that his word processor has corrupted his text document and has eliminated all spacing between words and all punctuation so his final term paper looks something like: “anawardwinningalgorithmto…”. Luckily he has access to a Boolean function dictionary( ) that takes a string s and returns true if s is a valid word and false otherwise. Considering that he has limited time to turn in his paper before the due date, find an algorithm that reconstructs his
2
paper into a sequence of valid words with no more than O(n ) calls to the
dictionary( ) function.
Solution: We denote that the string as s[1],….,s[n]. For the sub string s[1],….,s[m], we construct the table P as follows: if s[1],….,s[m] is composed of a sequence of valid words, then P[m]=true; otherwise P[m]=false. The recursive relation is as follows:
P[0] = true
P[m]=∨0≤i≤m−1(P[i]∧dictionary (s[i+1],…,s[m]))
If P[m] is true, we denote q[m]=j where j is such that P[ j] ∧ dictionary(s[ j + 1],…, s[m])
is true. By the definition of P[m], it is obvious that such a j must exist when P[m] is true. To reconstruct the paper into a sequence of valid words, we just need to output n, q[n],q[q[n]],…,0 as segmentation points.
Running time: The length of table of P and q is n and each step when we compute P[m] we need at most m calls of function dictionary(). Note the m ≤ n . Hence the running time is bounded by O(n^2)
Remark: Actually this question is exactly the same as the first problem in HW4: Problem 5 in Chapter 6 if we set quality(Yi+1,k) = 0if dictionary(Yi+1k) = falseand
quality(Yi+1,k) =1if dictionary(Yi+1k) = true.
7) 10 pts
An n × n array A consists of 1’s and 0’s such that, in any row of A, all the 1’s come before any 0’s in that row. Give the most efficient algorithm you can for counting the number of 1’s in A.
Algorithm: For each row i, we use binary search to find the index of last element of 1 in the array Ai[1,….n]. Suppose the index is ai. Then the sum of ai(0