Sample Test 2

NAME:
Questions To be Graded:

Design and Analysis of Algorithms
Test 2
Take Home
Summer 2009

Notes

1. Answer any four questions. Your solutions are due at the beginning of class Wednesday. Plan your time wisely. Do not overwork. Be clever. Read all the problems; do easy problems first, then work on the harder problems. If you get stuck, take time outs - you may get new insights or a fresh start. You have enough time to do this exam, so be neat and precise. To guard against silly mistakes, do your solutions on scratch paper, and then neatly copy them over for final submission.

2. For each algorithm that you design, describe it stepwise in English, and give pseudocodes only if clarity demands it, and calculate its worst-case time and space complexities. More efficient your (correct) algorithm is, the better your score will be. Also, the more concise and simple your solution is, the better your grade will be. Use algorithms and theorems from the lectures and the text to simplify your solutions. If you are solving a simpler problem than the one given, state your simplifying assumptions at the beginning of your solution. For graph problems, assume $n$ and $m$, respectively, to be the number of nodes and edges.

3. Policy on academic honesty: You may use your notes, your text, and other books. You may not communicate with any person, except me, about any aspect of the exam until after the hand-in deadline.
4. Bugs: If you are in doubt about the interpretation of a question, clarify it with me. Email: sprasad@gsu.edu. Good luck!

Questions

1. Give a modified algorithm for Counting Sort which does not use an output array, and is able to genearte sorted output in the input array itself. You may use a count array and an additional constant number of variables. Additionally, the Counting Sort need not remain stable.

2. Here is a divide-and-conquer based algorithm which employs Kruskal's algorithm as a subroutine to find minimum spanning forest (MSF):

   Given a undirected weighted graph $G=(V,E)$, divide the set of edges $E$ into two equally-sized disjoint subsets $E_1$ and $E_2$ (such that $E = E_1 \cup E_2$) thus obtaining two subgraphs $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$. Recursively, find the MSF $F_1 = (V, T_1)$ of $G_1$ and $F_2=(V,T_2)$ of $G_2$. Then ``merge" the two forests into one $(V,T_1 \cup T_2)$ and run the kruskal's algorithm on it to find an MSF for the original graph $G$. A subgraph is recursively split into two until the number of edges in it becomes less than or equal to $n$ in which case Kruskal's algorithm is employed to find a MSF for the subgraph.

   Argue in a few sentences that this algorithm produces an MSF of graph $G$. Notice that algorithm is based on successively eliminating edges from the graph. You simply need to prove that those edges which are discarded could not belong to the MSF of $G$. That is, if an edge in a subgraph $G'$ of $G$ does not belong to the MSF of $G'$, then that edge does not belong to the MSF of $G$ either. For the purpose of this proof, assume that all weights are distinct, and therefore, $G$ has a unique MSF.

   What is the time complexity of this algorithm. Do you see any advantage of this algorithm over basic Kruskal's algorithm if you wanted to employ a parallel/multicore system.

3. Write an efficient algorithm that will find an optimal order for multiplying n matrices $A_1 X A_2 X \ldots A_n$ where dimension of each matrix is $i X i$, $i X j$, $j X i$, or $j X j$ for some fixed positive integers $i and j$. Analyze your algorithm.

4. Prove or disprove that if the weights on the edges of a connected graph are distinct, then there is a unique shortest path tree.

5. A bipartite graph is a graph whose vertices can be partitioned into two subsets such that there is no edge between any two vertices in the same subset. Develop an efficient algorithm to determine if a graph is bipartite. Analyze its time complexity in detail.

6. Here is a proposed shortest path algorithm to handle the case of graphs with negative edge weights. The idea is to add a large positive constant to the weight of every edge, thereby making all the weights positive, and then run Dijkstra's algorithm to find the shortest path in the new graph. So for example, if the negative edge weight is -42, one could add 50 to all edges. If this works, explain why. If it does not work, provide counter examples.