MCQ Answer the questions

Although the questions are of MCQ types, you are required to write explanations for your answers. Answers with no or copied explanations will not be evaluated.

Only handwritten answers (in a channel file) will be accepted.

Answer the questions in your own words.

1. Consider the following variation of the merge function, where the input lists A and B are assumed to be sorted, with no duplicated elements, and C is the output list.

function StrangeMerge(A,m,B,n,C)

{

// A has m elements, B has n elements

i = 0; j = 0; k = 0;

while (k < m+n)

{

if (i == m){j++;k++;}

if (j == n){C[k] = A[i];i++;k++;}

if (i != m and j != n)

{

if (A[i] < B[j]){C[k] = A[i];i++;k++;}

if (A[i] == B[j]) {i++; j++;}

if (A[i] > B[j]) {j++;}

}

}

}

What does C contain after executing StrangeMerge(A,m,B,n,C)?

1. C contains the intersection of A and B.
2. C contains all values in B that do not occur in A.
3. C contains all values in A that do not occur in B.
4. C contains all values that occur in either A or B, but not in both input lists.
5. Suppose we modify mergesort as follows. We split the input into three equal segments, recursively sort each segment and then do a three way merge of the three sorted segments to obtain a fully sorted output.

If we work out the recurrence for this variant, we find that the worst case complexity is O(n log3 n), as opposed to O(n log2 n) for the usual divide and conquer that splits the input into two equal segments.

Let us call the new version 3-way mergesort. What can we say about the asymptotic worst case complexity of 3-way-mergesort with the usual mergesort?

1. The asymptotic worst case complexity of 3-way mergesort is better than that of usual mergesort.
2. The asymptotic worst case complexity of 3-way mergesort is the same as that of usual mergesort.
3. The asymptotic worst case complexity of 3-way mergesort is worse than that of usual mergesort.
4. This depends on the length and the initial arrangement of values of the input.
5. Suppose a new generation CPU can process 10¹⁰operations per second. You have to sort an array with 10⁸ Which of the following is true?
6. Insertion sort could take several hours while merge sort will always take less than 1 second.
7. Insertion sort will always take several hours while quicksort will always take less than 1 second.
8. Insertion sort will always take several hours while merge sort will always take less than 1 second.
9. Insertion sort could take several hours while quicksort will always take less than 1 second.
10. Which of the following statements is not true about quicksort?
11. For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n²).
12. If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
13. If we could find the median in time O(n), quicksort would have worst case complexity O(n log n).
14. Quicksort and merge sort are both examples of divide and conquer algorithms.
15. We have a list of three dimensional points [(7,1,8),(3,5,7),(6,1,4),(6,5,9),(0,2,5),(9,0,9)]. We sort these in ascending order by the second coordinate. Which of the following corresponds to a stable sort of this input?
16. [(9,0,9),(7,1,8),(6,1,4),(0,2,5),(6,5,9),(3,5,7)]
17. [(0,2,5),(3,5,7),(6,1,4),(6,5,9),(7,1,8),(9,0,9)]
18. [(9,0,9),(6,1,4),(7,1,8),(0,2,5),(3,5,7),(6,5,9)]
19. [(9,0,9),(7,1,8),(6,1,4),(0,2,5),(3,5,7),(6,5,9)]
20. An array A contains N integers arranged in a random sequence. We want to check if any value is duplicated in the sequence. Which of the following would be the most efficient algorithm, asymptotically.
21. For each pair of positions i and j, check if A[i] is equal to A[j].
22. Sort the array using insertion sort. When inserting each element into the sorted prefix, check if there is already a value equal to it in the prefix.
23. Sort the array using merge sort. Scan the sorted array from beginning to end looking for adjacent equal elements.
24. Sort the array using quick sort. Use binary search on the sorted array to find duplicated values.
25. A CPU can perform 10⁸operations a second. You are implementing an O(n²log₂n) algorithm to solve a problem. You want to demonstrate the algorithm to your boss, and ensure that the program runs within 1 second on all the demos. Among the following values of n, which is the largest safe value for the demo?
26. n = 7500 b) n = 5000 c) n = 2000 d) n = 1000

8. An airline serves 200 cities and runs 1100 direct flights each day between these cities. Which of the following is a good data structure to represent the collection of flights?
9. A 200 × 200 array A, where A[i][j] = 1 if there is a direct flight from city i to city j and 0 otherwise.
10. A stack containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j.
11. A queue containing values (i,j) for each pair of cities i, j for which there is a direct flight from city i to city j.
12. A list containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j.
13. An undirected graph G has 300 nodes and the minimum degree of any vertex is 3. Which of the following is the most precise statement we can make about m, the number of edges in G?
14. m is at least 900. b) m is at least 450.
15. c) m is at least 300. d) m is at least 100.
16. Which of the following statements is not true about breadth-first search (BFS) in an undirected graph starting at a vertex v?
17. BFS identifies all vertices reachable from v.
18. Using an adjacency list instead of an adjacency matrix can improves the worst case complexity to O(n + m).
19. BFS cannot be used to check for cycles in the graph.
20. BFS can be used to identify the furthest vertex from v in any graph, in terms of number of edges.
21. Applying for permits to put up a factory is an 11 step process. Some steps depend on others, as described below.

Step 1 must be completed before steps 3 and 4 start.

Step 2 must be completed before steps 3, 6 and 7 start.

Step 3 must be completed before step 7 starts.

Step 4 must be completed before step 5 starts.

Step 5 must be completed before step 7 starts.

Step 7 must be completed before steps 8 and 9 start.

Step 9 must be completed before steps 10 and 11 start.

Each step takes a week to complete. What is the minimum number of weeks required to get all the permits in place?

1. 4 b) 6 c) 8 d) 9

12. We are given a directed graph, using an adjacency matrix representation. For each vertex v, we want to compute the set of incoming edges (u, v). Which of the following is the most accurate description of the complexity of this computation. (Recall that n is the number of vertices and m is the number of edges.)
13. O(n) b) O(n+m) c) O(n²) d) O(m)
14. Consider the following strategy to solve the single source shortest path problem with edge weights from source s.
15. Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes.
16. Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph. Which of the following statements is correct?
17. This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm.
18. This strategy will solve the problem correctly and is as efficient as Dijkstra's algorithm.
19. This strategy will not solve the problem correctly.
20. None
21. Suppose we run Prim’s algorithm and Kruskal’s algorithm on a graph G and the two algorithms produce minimum-cost spanning trees T_Pand T_K, respectively. Which of the following is true?
22. T_Pmust be identical to T_K.
23. If e is a minimum cost edge in G, e belongs to both T_Pand T_K.
24. If T_Pis different from T_K, some pair of edges in G have the same weight.
25. If e is a maximum cost edge in G, e belongs to neither T_Pnor T_K.
26. Suppose we want to extend the union-find data structure to support the operation Reset(c), which takes as input the name of a component c and then breaks up c into singleton components, like MakeUnionFind(). For instance if c = 3 and c currently consists of {1,3,7}, then Reset(c) will produce three components called 1, 3 and 7 consisting of {1}, {3} and {7}, respectively. Which of the following is correct about the cost of adding Reset(c) to the array and pointer implementations of union-find discussed in the lecture?
27. Array representation: O(size(c)), Pointer representation: O(size(c))
28. Array representation: O(n), Pointer representation: O(size(c))
29. Array representation: O(size(c)), Pointer representation: O(n)
30. Array representation: O(n), Pointer representation: O(n)
31. Suppose we want to delete an arbitrary element from a max heap. (Assume we have auxiliary arrays NodeToHeap[] and HeapToNode[] required for the update() operation.) Consider the following strategies.

Strategy 1: Remove the element from the array, compress the array and reheapify.

Strategy 2: Update the value of this node to the current maximum value in the heap + 1, then delete_max. Which one of the following is TRUE?

1. Strategy 1 takes time O(n) and Strategy 2 takes time O(log n)
2. Strategy 1 takes time O(log n) and Strategy 2 takes time O(n)
3. Strategy 1 takes time O(n) and Strategy 2 takes time O(n log n)
4. Strategy 1 takes time O(n log n) and Strategy 2 takes time O(n)
5. Suppose we want to support the operations predecessor and successor in a heap. Given a value v in the heap, pred(v) tells us the next smaller value currently in the heap and succ(v) tells us the next larger value currently in the heap.
6. In both min heaps and max heaps, both operations take time O(log n).
7. In both min heaps and max heaps, both operations take time O(n).
8. In a min heap, pred(v) takes time O(log n) and succ(v) takes O(n) whereas in a max heap pred(v) takes time O(n) and succ(v) takes O(log n).
9. In a min heap, pred(v) takes time O(n) and succ(v) takes O(log n) whereas in a max heap pred(v) takes time O(log n) and succ(v) takes O(n).
10. Suppose you are playing game of shooting balloon. You expect to shoot n balloons in the board, assuming you are sharpshooter, 100% hit. There are two scenarios, you need find the appropriate Big Oh notation for each scenario. In these problems, one unit of work is shooting one balloon.

Scenario 1: For every 2 balloons you are able to shoot, one new balloon is inserted in the board. So, if there were 20 balloons, after you shoot the first 2, there are 19 on the board. After you shoot the next 2, there are 18 on the board. How many balloons do you shoot before the board is empty?

Scenario 2: By the time you have shoot the first n balloons, n-1 new balloons have been inserted on the board. After shooting those n-1 balloons, there are n-2 new balloons are inserted on the board. After checking out those n-2 balloons, there are n-3 new balloons on the board. This same pattern continues until on new balloons are inserted on the board. How many total balloons do you shoot before the board is empty?

1. O(n) and O(n²) b) O(1) and O(n)
2. c) O(n) and O(1) d) O(lg n) and O(n lg n)
3. Which sequence corresponds to that of depth first search for the graph given below. The search starts at vertex 0 and lexicographic ordering is assumed for the edges emanating from each vertex.

1. a) 0 1 2 4 3 5 b) 0 1 2 5 4 3 c) 0 1 2 3 4 5 d) 0 1 3 4 2 5
2. Correct choice of data structures can improve the performance of algorithms. Match the following algorithms with appropriate data structures:
3. Breadth first search a. Heap
4. Depth first search b. Stack

iii. Sorting c. Queue

1. a) i-a ii-b iii-c b) i-b ii-a iii-c
2. c) i-c ii-b iii-a d) i-b ii-c iii-a
3. What is the shortest path from node A to node F?

1. A -> B -> D -> F B. A -> C -> B -> E -> F
2. A -> F D. A -> C -> E -> F
3. Using the graph from the previous question, if we apply Dijkstra's algorithm to find the shortest distance between node A and all the others, in what order do the nodes get included into the visited set (i.e their distances have been finalized)?

A - B C F G E D B - B C G E F D

C - C B E F G D D - C B E G F D