Download DU (University of Delhi) B-Tech 4th Semester 2341401 Design and Analysis of Algorithms Question Paper

FirstRanker.com

Unique Paper Code: 2341401

Name of the Paper: Design and Analysis of Algorithms

--- Content provided by FirstRanker.com ---

Name of Course: B.Tech (Computer Science)

Semester:

Duration of Examination: Three Hours

Maximum Marks: 75 marks

Instructions:

--- Content provided by FirstRanker.com ---

Question No 1 of 35 marks is compulsory

Attempt any four questions from Q No 2 to Q no 7

Number of Printed Sheets in Question Paper:

FirstRanker.com

1. (a) What is the runtime of the naive string matching algorithm? (3)

--- Content provided by FirstRanker.com ---

2. (b) A sequence of n operations is performed on a data structure. The i^th operation costs i if i is a power of 3; otherwise it costs 1. Use aggregate analysis to determine the amortised cost per operation. (3)
3. (c) Show that there are at most [n/2^h+1] nodes of height h in a heap with n elements. (3)
4. (d) Which properties of a red-black tree can be violated on deleting a node? (4) (take two cases depending on whether the deleted node is red or black)
5. (e) When does quick sort show its worst case behaviour? What is the runtime in this case? (4)
6. (f) Run the BFS and DFS algorithms on the following graph and show the corresponding trees. (4)

--- Content provided by FirstRanker.com ---

7. (g) Give an efficient algorithm to find both the minimum and maximum of a given array of n elements. (5)
8. (h) Name and briefly explain (i) greedy choice property (ii) optimal substructure property. (5)
9. (i) Illustrate the operation of counting sort on the array <6,0,2,0,1,3,4,6,1,3,2> (5)

2. (a) Find the largest common subsequence in the following sequences: X = <PQRMPQR>, Y = <RPQN> (6)
3. (b) Give the adjacency list and adjacency matrix representation of the following graph: (4)

--- Content provided by FirstRanker.com ---

3. (a) Sort the following character array using heapsort: HEAPSORT (5)
4. (b) Show that the height of an n-node RBT is O(lg n). (5)

FirstRanker.com

4. (a) Derive an expression for the runtime of insertion sort. (5)
5. (b) Find the length of the shortest path between a and g using Dijkstra's algorithm. (5)

--- Content provided by FirstRanker.com ---

5. (a) Consider a stack S on which the following operations can be performed:
   • Push (S, x): push object x onto the stack S
   • Pop (S): pop the top element from stack S and return the popped object
   • Multipop (S, k): remove k top objects from S
   Using the accounting method of analysis, determine the amortised cost per operation when a sequence of n operations is performed on the stack S. (5)
6. (b) Name the design technique on which Kruskal’s and Prim’s algorithm are based. What are the two algorithms meant for? Mention the fundamental difference in the way these algorithms work. (5)

--- Content provided by FirstRanker.com ---

6. (a) Are the following algorithms (i) stable (ii) in-place: Merge sort, Quick sort. Briefly explain. (4)
7. (b) Show the ordering of vertices produced by topological sort when run on the following DAG. (6)

7. (a) A man rides a bike between 2 cities located m kilometres apart. His tank needs to be refilled after every n kilometres. There are p fuel stations s₁, s₂, ... , s_p along the way. The distance between a station s_i and its previous station s_i-1 is given by d(s_i). The distance between the starting point and the first station is d(s₁) and d(s_i) < n for all i. If the man starts with a full tank, suggest how he can minimize the number of stops during his trip. (6)
8. (b) A burglar has to decide which items to take from a loot. The maximum weight that his bag can carry is W. There are n items to choose from. The weight and value of the i^th item is given by w_i and v_i respectively. Suggest how he can determine the most valuable combination of items to fit into his bag. (5)

FirstRanker.com

--- Content provided by FirstRanker.com ---