- August 9, 2020

EL9343 Final Exam (2020 Spring) Name: ID: Exam Time: 9:30 AM -12:00 PM, Upload Deadline: 12:10 PM May 13, 2020 Write all answers on your own blank answer sheets. Scan and upload answer sheets to NYUclasses at the end of the exam, and keep your answer sheets until the grading is finished. Make sure you use Adobe Scan to have all you pages in one single PDF file. Check your submission online before leaving the exam. Multiple choice questions may have multiple correct answers. You will get partial credit if you only select a subset of correct answers, and zero points if you select one or more wrong answers. 1. (24 points) True or False (3 points each) (a) T or F: Worst case tree height for AVL tree with n nodes is θ(log(n)); (b) T or F: For an undirected graph with n vertices to be acyclic, the maximum number of edges is n− 1; (c) T or F: For an undirected graph, DFS yields no forward or cross edges; (d) T or F: Any P problem is also a NP problem; (e) T or F: 0-1 knapsack problem can be solved by dynamic programming, and compu- tation time is a polynomial function of the input size; (f) T or F: If adjacency list is used to represent a graph, the worst case time complexity to determine whether an edge (u, v) exists is θ(E). (g) T or F: There is only one valid topological ordering of vertices in a directed acyclic graph. (h) T or F: Kruskal’s algorithm for minimum spanning tree does not work on a graph with negative weight edges. 2. (4 points) For a given node v in a binary search tree, which of the following statements about its successor are true? (a) v always has a successor in the tree; (b) The successor can be the left child of v’s right child; (c) The successor can be the right child of v’s left child; (d) The successor can be v’s right child; 1 (e) The successor can be an ancestor of v. 3. (4 points) Which of the following statements are true? (a) The algorithm to decide whether there is a Hamiltonian cycle in a graph cannot always be completed in polynomial time; (b) If problem A is reducible to problem B in polynomial time, then problem B is easier to solve than problem A; (c) All NP-complete problems can be verified in polynomial time; (d) If a polynomial time algorithm is found for a NP-complete problem, all NP-complete problems are solvable in polynomial time; (e) None of the above. 4. (4 points) Which of the following statements about breadth-first search (BFS) are true? (a) Complexity of BFS on a dense graph is θ(E); (b) BFS search starting from a single vertex s always visits all vertices in a graph; (c) BFS employs a queue to store the grey nodes; (d) BFS can be used to solve single source shortest path in an unweighted graph; (e) None of the above. 5. (4 points) Which of the following sets of codewords can be Huffman codes? (a) [0,1]; (b) [00, 10, 11]; (c) [000,001, 01, 10, 11]; (d) [1, 01, 000, 001]; (e) None of the above. 6. (4 points) Which of the following statements about shortest path are true? (a) In Bellman-Ford algorithm, the edges can be relaxed in any given order; (b) Greedy-based shortest path algorithms work on a graph with negative weight edges; (c) In a directed acyclic graph, shortest path distance between any pair of vertices is always well-defined; (d) In Floyd-Warshall, the sub-problems are limited by the number of hops allowed; (e) None of the above 7. (4 points) In the activity selection problem, which of the following is true? (a) It can be solved by divide-and-conquer; (b) It can be solved by greedy and select the activity with earliest finish time; (c) It can be solved by greedy and select the activity with shortest duration; (d) Any optimal solution cannot include the activity with the latest finish time; (e) None of the above. 2 8. (8 points) For the AVL Tree in Figure 1, when a key with value 8 is inserted, how many rotations are needed to restore the AVL tree property? what is the restored AVL tree with the inserted key? 4 6 25 11 14 16 9 10 18 12 21 6 Figure 1: AVL Tree for Question 8 9. (10 points) Show how depth-first search works on the graph in Figure 2. Assume that the main loop of DFS considers vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification of each edge. F B A D C E Figure 2: Directed Graph for Question 9 3 10. (8 points) Compute the transitive closure of the following directed graph using modified Floyd-Warshall algorithm, show the T (k) matrices at all steps, show the final transitive closure. 1 2 3 654 Figure 3: Directed Graph for Question 10 11. (12 points) For a given array A[1 · · ·n], the Maximum Subarray problem is to find the contiguous subarray A[l · · · r], such that the summation of A[l] + A[l + 1] + · · · + A[r] is the maximum among all contiguous subarrays. It can be solved by a divide-and-conquer algorithm with O(n log n) complexity. Develop another algorithm to solve it with O(n) complexity. (Hint: use dynamic programming, write down the recurrence of optimal solutions and the detailed pseudo code, and complexity analysis) 12. (14 points) Given a weighted undirected graph G = (V,E), suppose all the edge weights are distinct, and a minimum-spanning tree T has been found, if the weight on one edge e ∈ E is reduced from we to w ′ e, (a) (6 points) design an O(|V |) algorithm to construct a new minimum-spanning tree T ′ for the updated graph G′; (b) (3 points) justify the complexity of your algorithm; (c) (5 points) prove the correctness of your algorihtm. 4