This is the official question paper of Design and Analysis of Algorithms of B.Sc. (Hons.) Computer Science Course at the University of Delhi.
Question 1 is compulsory.
Attempt any four questions from question 2 to question 8.
Part of a question must be answered together.
Some symbols may not be visible on mobile devices. Hence we recommend that you use a desktop to view the solutions to the questions.
Question 1(a): Use master's theorem to give tight asymptotic bounds for the recurrence T(n) = 8 T(n/2) + θ(n²)
Question 1(b): Discuss the running time of following snippet of code:
count=0
for (i=l, i<=n, i++)
for (j=1, j<=n, j=2*j)
count++Question 1(c): A team of explorers is visiting the Sahara desert. Due to the extreme heat, they need to stay hydrated and have brought n bottles of different sizes to carry water. After travelling a few kilometres, they run out of water but luckily find a water source. This water source has only L litres of water available, which is less than the combined capacity of all their bottles. They need to fill L litres of water using the minimum number of bottles. Describe a greedy algorithm to help them fill L litres of water using the minimum number of bottles.
Question 1(d): Will the greedy strategy with the greedy parameter being value per unit weight of the items yield an optimal solution for the 0-1 knapsack problem? Justify.
Question 1(e): Can dynamic programming be applied to all optimization problems? Why or why not?
Question 1(f): Why is the worst-case running time for bucket sort θ(n²)? What changes would you make to the algorithm so that its worst-case running time becomes O(nlgn)?
Question 1(g): Let G be a tree graph. Further, let A and B be the trees produced by performing BFS and DFS respectively on G. Can A and B be different trees? Why or why not?
Question 1(h): Consider the following graph:
Specify whether the above graph is bipartite or not. If yes, give the partition, else justify.
Question 1(i): We are given a weighted graph G in which edge weights are not necessarily distinct. Can graph G have more than one minimum spanning tree (MST)? If yes, give an example, else justify.
Question 1(j): Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree.
Question 2(a): Consider the scheduling problem wherein you are given a single resource and a set of requests having deadlines. A request is said to be late be late if it misses the deadline, Your goal is to minimize the maximum lateness. With respect to a schedule S, idle time is defined as the time during which the resource is idle, in between two requests. S is said to have an inversion when request i has been scheduled before j and d(i) > d(j), where d(i) and d(j) are the deadlines of the requests i and j respectively. Argue that all schedules with no idle time and no inversions have the same maximum lateness.
Question 2(b): For each of the following sorting algorithms, merge sort and insertion sort, discuss whether or not it is (i) stable and (ii) in-place
Question 3(a): Let G = (V,E) be a directed unweighted graph. Given two vertices s and t in V, what is the time required to determine if there exists at least one s-t path in G? Can we use the DFS algorithm to find the shortest-path distance from the s to t? If yes, justify, otherwise give a counter-example.
Question 3(b): Suppose we perform a sequence of stack operations on a stack whose size never exceeds k. After every k operations, we make a copy of the entire stack for backup purposes. Show that the cost of n stack operations, including copying the stack, is O(n) by assigning suitable amortized costs to the various stack operations.
Question 4(a): Show that, with the array representation for sorting an n-element heap, the leaves are the nodes indexed by floor(n/2+1), floor(n/2+2), …,n. What would be the location of the minimum element in the above heap?
Question 4(b): Given an array A of n integers, you need to find the maximum sum of any contiguous subarray. For instance, the maximum sum of any contiguous subarray in the array -1, 2, 3, -2, 5, -6, 7, -8 is 9 (which is the sum of the subarray 2, 3, -2, 5, 6, 7). Complete the following Dynamic Programming solution for the above problem:
DP[0] = A[0]
For i = 1 to n
DP[i] = max(A[i],____)
Question 5(a): How many topological orderings does the following graph have? Specify all of them.
Question 5(b): A student was asked to sort a list of n numbers in decreasing order. The student writes an algorithm that works iteratively as follows. In every iteration, the following two steps are done:
Linear search is used to find the maximum element in the portion of the array which is not yet sorted.
The maximum element found in step 1 is placed at the beginning of the not-yet-sorted portion of the array.
This algorithm is given as input a list already sorted in descending order. What would be the time complexity of the algorithm on this input? Explain.
Question 6(a)(i): What is the smallest possible depth of a leaf in a decision tree for a comparison sort? Name a sorting technique to which this smallest depth would correspond.
Question 6(a)(ii): What is the minimum number of leaves in the decision tree for a comparison sort? Use this observation to derive a lower bound on the number of comparisons performed by a comparison sort in the worst case.
Question 6(b): Show that at most 3*floor(n/2) comparisons are sufficient to find both the minimum and maximum in a given array of size n.
View Solution
Question 7(a): The BFS algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G. Can Dijkstra's algorithm be used in place of BFS? In a different scenario. Dijkstra's algorithm has been used to produce the shortest paths from a node s to all other nodes in a graph G'. Can BFS be used in place of the Dijkstra's algorithm? Explain your answers for both scenarios.
Question 7(b): Write a pseudocode for the memoized recursive algorithm to compute the nth Fibonacci number. What would be its time complexity?
END OF THE PAPER