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