Consider the following recursive function which performs redundant computations:
ID: 3583247 • Letter: C
Question
Consider the following recursive function which performs redundant computations:
else {
2
} }
Answer the following questions about a dynamic programming solution which performs no redundant computations.
13. Suppose the initial call to the function is knapsack(100,weights,values,20) where the length of the weights and values arrays is 20. What are the row × column dimensions of the table needed for a dynamic programming solution? Choose the most informative answer.
(A) the correct answer is not listed (B) 100×21
(D) the correct table is not two-dimensional (E) 101×20
(F) 101×21
(C) 100×20
14. Which direction is the table populated, where low means a low index and high means a high index? Choose the most
informative answer.
(A) the table is not two-dimensional
(B) the correct answer is not listed
(C) from high rows to low rows, from low columns to high columns
(D) from low rows to high rows, from low columns to high columns
(E) from low rows to high rows, from high columns to low columns
(F) from high rows to low rows, from high columns to low columns
15. Suppose instead of a dynamic programming solution, the results of the recursive calls were memoized in a red-black tree. What would be the asymptotic runtime of the memoized function?
(A) (ilogi)
(B) (wlogw)
(C) (i)
(D) (w × i × (logw + logi)))
16. What is the best description of a cycle?
(A) a path that visits all vertices
(B) a set of edges from which the removal of any edge leaves a single path
(E) (w)
(F) the correct answer is not listed
(G) (w×i)
(C) a path plus one edge connecting the starting and end- ing vertices
(D) a trail that ends up back at the starting vertex
Consider running Kruskal’s algorithm on the undirected, complete graph KN . What is the largest number of edges that can be processed before all remaining edges cause a cycle? Be sure to include the last edge that doesn’t cause a cycle in your count.
(A) (N1)(N2) +1 (E) N(N1) +1 22
(B) N(N1) 1 (F) (N1)(N2) 1 22
(C) N(N 1)1 (G) N(N 1)+1
(D) (N 1)(N 2) + 1 (H) the correct answer is not listed
Suppose Dijkstra’s algorithm for shortest paths was implemented using an ordered linked list as a priority queue. What would be the runtime contributions of c, the creation of the priority queue, m, the extract min operations (in total), and d, the decrease key operations (in total), respectively. Assume the ordered linked list is created by merge-sorting an array of vertices, then generating the linked list from the sorted array.
(A) c = V log V, d = V, m = E log V (B) c = V log V, d = V, m = EV
(C) c = V log V, d = V log V, m = E (D) c = V log V, d = V, m = E
(E) c = V 2, d = V log V, m = EV
(F) c = V 2, d = V log V, m = E log V
(G) c = V 2, d = V log V, m = E (H) the correct answer is not listed
19. Some one shows you a correct algorithm for an NP-complete program X that can be veriied in polynomial time. Is this a new result? If so, what is that new result? Choose the best answer.
(A) Yes, problem X is in P
(B) Yes,P!=NP
(C) Yes, problem X is not in P (D) Yes, problem X is in NP
(E) No
(F) Yes, problem X is not in NP
(G) Yes,P=NP
20. What is the best deinition of an NP-complete problem? Assume we already know the problem is in NP. Also assume reductions can be accomplished in polynomial time and space.
(A) it can be reduced to any problem in NP
(B) any NP-complete problem can be reduced to it (C) it can be reduced to any problem in P
(D) it can be reduced to any NP-complete problem (E) any problem in NP can be reduced to it
(F) any problem in P can be reduced to it
Explanation / Answer
Answer :
13. Suppose the initial call to the function is knapsack(100,weights,values,20) where the length of the weights and values arrays is 20. What are the row × column dimensions of the table needed for a dynamic programming solution? Choose the most informative answer.
(A) the correct answer is not listed (B) 100×21
(D) the correct table is not two-dimensional (E) 101×20
(F) 101×21
(C) 100×20
14. Which direction is the table populated, where low means a low index and high means a high index? Choose the most
informative answer.
(A) the table is not two-dimensional
(B) the correct answer is not listed
(C) from high rows to low rows, from low columns to high columns
(D) from low rows to high rows, from low columns to high columns
(E) from low rows to high rows, from high columns to low columns
(F) from high rows to low rows, from high columns to low columns
15. Suppose instead of a dynamic programming solution, the results of the recursive calls were memoized in a red-black tree. What would be the asymptotic runtime of the memoized function?
(A) (ilogi)
(B) (wlogw)
(C) (i)
(D) (w × i × (logw + logi)))
16. What is the best description of a cycle?
(A) a path that visits all vertices
(B) a set of edges from which the removal of any edge leaves a single path
(E) (w)
(F) the correct answer is not listed
(G) (w×i)
(C) a path plus one edge connecting the starting and end- ing vertices
(D) a trail that ends up back at the starting vertex
Consider running Kruskal’s algorithm on the undirected, complete graph KN . What is the largest number of edges that can be processed before all remaining edges cause a cycle? Be sure to include the last edge that doesn’t cause a cycle in your count.
(A) (N1)(N2) +1 (E) N(N1) +1 22
(B) N(N1) 1 (F) (N1)(N2) 1 22
(C) N(N 1)1 (G) N(N 1)+1
(D) (N 1)(N 2) + 1 (H) the correct answer is not listed
Suppose Dijkstra’s algorithm for shortest paths was implemented using an ordered linked list as a priority queue. What would be the runtime contributions of c, the creation of the priority queue, m, the extract min operations (in total), and d, the decrease key operations (in total), respectively. Assume the ordered linked list is created by merge-sorting an array of vertices, then generating the linked list from the sorted array.
(A) c = V log V, d = V, m = E log V (B) c = V log V, d = V, m = EV
(C) c = V log V, d = V log V, m = E (D) c = V log V, d = V, m = E
(E) c = V 2, d = V log V, m = EV
(F) c = V 2, d = V log V, m = E log V
(G) c = V 2, d = V log V, m = E (H) the correct answer is not listed
19. Some one shows you a correct algorithm for an NP-complete program X that can be veriied in
polynomial time. Is this a new result? If so, what is that new result? Choose the best answer.
(A) Yes, problem X is in P
(B) Yes,P!=NP
(C) Yes, problem X is not in P (D) Yes, problem X is in NP
(E) No
(F) Yes, problem X is not in NP
(G) Yes,P=NP
20. What is the best deinition of an NP-complete problem? Assume we already know the problem is in NP. Also assume reductions can be accomplished in polynomial time and space.
(A) it can be reduced to any problem in NP
(B) any NP-complete problem can be reduced to it (C) it can be reduced to any problem in P
(D) it can be reduced to any NP-complete problem (E) any problem in NP can be reduced to it
(F) any problem in P can be reduced to it
Answer :
13. Suppose the initial call to the function is knapsack(100,weights,values,20) where the length of the weights and values arrays is 20. What are the row × column dimensions of the table needed for a dynamic programming solution? Choose the most informative answer.
(A) the correct answer is not listed (B) 100×21
(D) the correct table is not two-dimensional (E) 101×20
(F) 101×21
(C) 100×20
Answer :
(F) 101×21
......
14. Which direction is the table populated, where low means a low index and high means a high index? Choose the most
informative answer.
(A) the table is not two-dimensional
(B) the correct answer is not listed
(C) from high rows to low rows, from low columns to high columns
(D) from low rows to high rows, from low columns to high columns
(E) from low rows to high rows, from high columns to low columns
(F) from high rows to low rows, from high columns to low columns
Answer :
(C) from high rows to low rows, from low columns to high columns
......