ALCCS

 

FEBRUARY 2009

 

Code: CS21††††††††††††††††††††††††††††††††††† Subject: DATA STRUCTURES & ALGORITHM DESIGN

Time: 3 Hours††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††† Max. Marks: 100

 

NOTE:

      Question 1 is compulsory and carries 28 marks. Answer any FOUR questions from the rest.Marks are indicated against each question.

      Parts of a question should be answered at the same place.

 

 

Q.1 †††††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (7 x 4)

†††††††††††† a.Consider a queue whose capacity is 6. Following operations are carried out in the sequence shown:

††††††††††††††††† (i)†† Objects A, B, D, H added

††††††††††††††††† (ii)An object removed

††††††††††††††††† (iii) Object I added

††††††††††††††††† (iv) An object removed

††††††††††††††††† (v)Object C added

††††††††††††††††† Show the 5 queue representations after each operation is carried out.

 

†††††††††††† b.Write a recursive function, which computes mn where both m and n are integers.

†††††††††††††††††††††††††††††††††††

†††††††††††† c.Calculate the asymptotic complexity of the code segments shown below (using big-O notation) with respect to the problem size n:

††††††††††††††††††††††††††††††††††† (i)††††††† for (i = 0; i < n; i=i*2) {

for (j = 1; j < n; j++) {

...

}

††††††††††††††††† ††††††††† ††††††††††††††††††††}

††††††††††††††††††††††††††††††††††† (ii)††††† for (i = 0; i < n-2; i++) {

for (j = 0; j < n; j=j*2) {

for (k = 1; k < 5000; k=k*5) {

...

}

††††††††††††††††††††††††††††††††††††††††††††††† }

for (j = 0; j < 1000*n; j=j+1) {

...

}

for (j = 0; j < n/5; j=j+5) {

...

}

††††††††††††††††† ††††††††††††††††††††††††††††† }

 


 

†††††††††††† d.Suppose we build the Huffman code tree for the set of letters and frequencies given below:

††††††††††††††††††††††††††††††††††† Character: A B C D E F

††††††††††††††††† †††††††††††††††††††††††††† Frequency: 1 5 20 30 40 50

††††††††††††††††† What will be the length of the code for the character B?

 

†††††††††††† e.An array contains n random integers.It is sorted using merge sort method.Indicate the time complexity if this new sorted array is again sorted using

††††††††††††††††† (i)†† merge sort

††††††††††††††††† (ii)quick sort

 

†††††††††††† f.†† Given a sequence S containing the elements 4, 15, 6, 3, 21, and 2.Insert these elements in the given order into an initially empty Binary Search tree.

 

†††††††††††† g. A singly linked list STAR contains an integer in each node.Show how one can delete the first node from this list.

 

Q.2†††††† a.Write the adjacency matrix AND the adjacency linked list for this undirected graph.†††† (10)

††††††††††††††††† ††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

 

 

 

 

 

 

 

††††††††††††

†††††††††††† b.Given a tree with n vertices, how many edges does it have? Prove the correctness of your conclusion.††††††††† (8)

 

Q.3†††† a.Show the operation of applying the MergeSort algorithm on the list

††††††††††††††††† 14, 25, 3, 21, 7, 35, 18, 27††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (10)

 

†††††††††††† b.What is the efficiency of the MergeSort algorithm? What is the efficiency of InsertionSort, BubbleSort and SelectionSort algorithms in the worst case?††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (8)

†††††††

Q.4†††† a.What is meant by breadth-first traversal and breadth-first search of an undirected graph? Write down an iterative breadth-first traversal algorithm.††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (10)

 

†††††††††††† b.Consider the following undirected graph.†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††

†††††††

†††††††††††††††††

†††††††††††††††††

††††††††††††††††† Draw a DFS and BFS tree for the graph starting at node A. If several nodes can be chosen at some step, pick the vertex that is alphabetically first.†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (8)

 

Q.5†††† a.Two stacks are implemented using an array A [10] as shown in the figure. What would be the initial values of top for the two stacks? Arrows shows the direction of growth of the stack.

††††††††††††††††††††††††††††††††††† ††††††††††††††††††††††† Array A [10]

†† S1†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† ††††††† S2

†††††††††††††††††††††††

††††††††††††††††† Code the PUSH and POP routines for the stacks.†††††††††††††††††††††††††††††††††††††††††††††††††††††† (10)

 

†††††††††††† b.Convert the following infix expression to postfix expression

††††††††††††††††††††††††††††† A+B*(C+D)/F+D*E

††††††††††††††††† Draw a binary tree containing keys P, L, A, C, E, such that the postorder traversal visits nodes in this order: E, A, L, C, P and the inorder traversal visits nodes in order: E, L, A, P, C.†††††††††††††††††††††††† (8)

†††††††

Q.6†††† a.Write a recursive algorithm to compute the sum of squares from given number m to n i.e. Compute m2 + (m+1) 2 Ö..+ n2††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† (8)

 

†††††††††††† b.An array contains the following elements [17 46 5 23 20].Use the heap sort method to sort the elements in increasing order.Draw the heap trees as you move through each step.††††††††††††††††††††††† (10)

 

Q.7†††† a.Consider the following graph. Using Kruskalís algorithm, calculate the minimum spanning tree, listing edges in the minimal spanning tree in the order they are added to the tree.†††††††††††††††††††††††††††††††††††††† (10)

 

 


 

 

 

†††††††††††††††††

 

†††††††

†††††††††††† b.Solve the following recurrence relation T(n) = T(n-1) + n.††††††††††††††††††††††††††††††††††††††††††††† (8) †††††††††††††††††††††††