Midterm (April 3, 2003)
Names:
Student ID:
Email:
Don’t panic!
Print your name, student id, and email in the box above, and print your name on top of every page.
Please write your answers on the front of the exam pages. Use the back of the page as scratch paper. Let us know if you need more paper.
Read the entire exam before writing anything. Make sure you understand what the questions are asking. If you give a beautiful answer to the wrong question, you’ll get no credit. If any question is unclear, please ask me for clarification.
Don’t spend too much time on any single problem (unless you solved all but one)
If you get stuck, move on to something else and come back later.
Write something down for every problem. Don’t panic and erase large chunks of work. It might be worth partial credit.
Don’t panic!
Problem Score
1
2
3
4
5
Problem 1: Multiple Choice (Every problem is 1 point)
1. What is n?
a) Q(nlog n) b) Q( n2) c) Q(n3) d) Q( n2log n)
2. What is ?
a) Q(log n) b) Q(n) c) Q(n log n) d) Q(n2)
3. What is the solution of the recurrence T(n) = T(n-1) + ?
a) Q(log n) b) Q(1) d) Q(n) e) Q(n log n)
4. How fast can we decide whether an undirected graph G = (V,E) is not connected?
a) Q(log |E|) b) Q(|V|) c) Q(|V| + |E|) d) Q(|V||E|)
5. A red-black tree on 127 keys must have at least 1 red node.
a) Yes b) No
6. If a direct graph has a topological ordering, then it is a DAG.
a) Always True b) Always False c) Sometime True and Sometime False
7. A rotation operation changes the height of a binary tree.
a) Always True b) Always False c) Sometime true and sometime false
8. If a problem can be solved by a dynamic programming algorithm, then it can be solved by a greedy algorithm.
a) Always True b) Always False c) Sometime true and sometime false
9. If a recurrence can be solved by the Master Theorem, then it can be solved the substitution method
a) Always True b) Always False c) Sometime true and sometime false
10. If a problem can be solved by a greedy algorithm, then it can be solved by a dynamic programming algorithm
a) Always True b) Always False c) Sometime true and sometime false
Problem 2: True or False and Justify (40 points total)
Circle T or F for each of the following statements to indicate whether the statement is true or false, respectively. If the statement is correct, briefly state why. If the statement is wrong, explain why or provide a counter example. The more content you provide in your justification, the higher your grade, but be brief. Your justification or explanation is worth more points than the true or false designation. Each statement is typically worth different amount of points depending on its difficulty. Here is an example of what we mean by justify:
T F Median-partitioned quick on n numbers runs in W(n 2) time in the wrost case.
Justification: A median partition is a balanced partition, which corresponds to the best case for quicksort. The recurrence is T(n) = 2T(n/2) + Q(n). So median-partitioned quicksort on n numbers runs in Q(n log n) time in the worst case.
T F [ 1 point for T-F, 2 points for explanation]
n lg2 n= O(n (log 2n) (loglog n))
T F [ 2 points for T-F, 5 points for explanation]
Suppose each element e in a red-black tree has some positive value v[e] stored with it. We can not augment the nodes in the red-black tree so that each node maintains the product of the values in its subtree without affecting the asymptotic running times of any standard tree operations.
T F [ 1 point for T-F, 3 points for explanation]
The Breadth-first search algorithm makes use of a FILO queue (Stack).
T F [ 2 points for T-F, 5 points for explanation]
We proved in class that given 2 arrays of n integers each, the longest common sub-sequence can be found in O(n2 ) time. We can infer from this that given an array of n integers, the longest monotonically increasing subsequence can be found in O(n2 ) time.
T F [ 2 points for T-F, 4 points for explanation]
A binary tree can be uniquely reconstructed from the output of the pre-order traversal of the tree, if all the elements in the tree are distinct. Recall that in a pre-order traversal, the root is first visited, the left-subtree is then recursively pre-order traversed and finally the right-subtree is recursively pre-order traversed.
T F [ 1 point for T-F, 3 points for explanation]
Radix sort does not require a “stable” sort in order to work properly.
T F [ 1 point for T-F, 2 point for explanation]
Depth-first search of a graph is asymptotically faster than breadth-first search.
T F [ 1 point for T-F, 4 points for explanation]
The component graph of strongly connected components of every directed graph may not always be a directly acyclic graph.
T F [ 1 point for T-F, 3 points for explanation]
For hashing an item into a hash table in which collisions are resolved by chaining, the best-case time is proportional to the load factor of the table.
T F [ 1 point for T-F, 2 points for explanation]
In the worst case, quick sort runs in O(n2 ) time
3. Depth-First Search [17 points]
Show a DFS walk on the graph below starting from the vertex a. Whenever the DFS algorithm has a choice as to which vertex to go to next, it should always choose the vertex with the lowest letter (closest to a in alphabetical order). Show the discovery and finish times on the graph on this page. Draw the DFS tree produced on the next page. Give each edge a label in {T, B,F,C} to indicate whether the edge is a tree, back, forward, or cross edge, respectively on the figure on page after the next page.
Show the discovery and finish time in the following figure. Use d=?? and f = ?? in the space for each vertex.
Problem. 3 continue:
Draw the DFS tree (forest) produced
Problem 3 Continue: Give each edge a label in {T, B, F,C} to indicate whether the edge is a tree, back, forward, or cross edge, respectively.
4. Red-Black tree [17 points]
Draw the evolution of the red-black tree after the following sequence of insertions.
Tree-Insert(8); Tree-Insert(7); Tree-Insert(6); Tree-Insert(5); Tree-Insert(4);
Tree-Insert(3); Tree-Insert(2); Tree-Insert(1).
Assuming initially the tree is empty.
Problem 4 continue
Problem 4 continue
Problem 5. Application background of this problem: Let’s consider a long country road with houses scattered very sparsely along it. Further let’s suppose that the residents of all these houses are wireless card users. You want to place wireless stations at certain points along the road, so that every house is within 4 miles of one of the base stations.
Formally, you are given a set of n positive real numbers . Design an algorithm that returns an integer k and a set of the integers such that (1) for all and (2) k is as small as possible.
Prove that your algorithm is correct, and analyze the running time of your algorithm.
[25 points if your algorithms runs in O(nlog n) time. 15 points if your algorithms runs in time]
Problem 6. Bipartite Graphs [20 points]
A graph G = (V,E) is said be to bipartite if we can partition the set of vertices into two disjoint sets and such that every edge in E has one endpoint in and one endpoint in . Design an efficient algorithm to compute whether or not a graph is bipartite, and provide an analysis of the running time of your algorithm.