![]() |
![]() |
![]() |
B.E./B.Tech, DEGREE EXAMINATION, NOVEMBER/DECEMBER 2005. Second Semester
Computer Science and Engineering
CS 1151 - DATA STRUCTURES
(Common to Information Technology and B.E. (Part-Time) I Semester Computer Science and Engineering (Regulations 2005))
Time : Three hours Maximum : 100 marks
Answer ALL questions. PART - A (10 x 2 = 20 marks)
1. Define the top-down design strategy. Start from beginning and explore the solution towards goal. 2. Define the worst case and average case complexities of an algorithm. The worst case complexity for a given problem size n corresponds to the maximum complexity encountered among all problems of size n. The average case complexity of the algorithm is averaged ones all possible problems of size n. 3. Swap two adjacent elements by adjusting only the pointers (and not the data) using : singly linked list. Void swap with next (position P, before P, List L) { Position P, After P; P = Before P After P = P P Before P After P } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
4. Define a queue model. The model of a queue is shown below:
Enqueue which inserts an element at the end and dequeue which deletes an element. 5. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a non empty binary tree. Let N = number of nodes, F = number of full nodes, L = number of leaves, and H = number of half nodes (nodes with one child). Clearly, N = F + H + L further 2F + H = N - 1. Subtraction L - F = 1. 6. Suppose that we replace the deletion function, which finds, return, and removes the minimum element in the priority queue, with find min, can both insert and find min be implemented in constant time? Yes, when an element is inserted, we compare it to the current minimum and change the minimum if the new element is smaller. Deletion operations are expensive in this scheme. 7. What is the running time of insertion sort if all keys are equal? 0(N) because the while loop terminates immediately. Of course, accidentally changing the test to include equalities the running time to quadratic for this type of input. 8. Determine the average running time of quicksort. The average running time of quicksort is o(n log n). 9. What is the space requirement of an adjacency list representation of a graph?
10. Define an NP-complete problem. A decision problem D is said to be NP - complete, if (i) it belongs to class NP; (ii) every problem in NP is polynomially reducible to D.
| ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
PART B - (5 x 16 = 80 marks)
11. (i) Find the average search cost of the binary search algorithm. (8) The average search cost of a binary search procedure with n keys is average search cost Note that
11.(ii) Design an algorithm to compute the sum of the squares of n numbers. That is (ii) Algorithm description : 1. Input n 2. Set sum s to o 3. Setting l = 1, input the value of ai 4. Add s and ai * ai 5. Increment the value of a by i 6. Repeat steps 3 to 5 for n times 7. Result the sum s. 12. (a) Give a procedure to convert an infix expression a + b * c + (d * e + f) * g to postfix notation. Algorithm description: 1. First, the symbol a is read, so it is passed through to the output. Then + is read and pushed onto the stack. Next 6 is read and passed through to the output. The state of affairs at this junction is | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
Step 1
Stack Output 2. Next a '*' is read. The top entry of the operator has lower precedence then *, so put '*' on the stack. Next c is read and output. Then we have Step 2
Stack Output 3. The next symbol is a '+'. Checking the stack, the symbol '*' is popped and place it on the output. Pop the other '+' which is out of lower but equal priority, on the stack; and then push the '+'. Step 3
Stack Output 4. The next symbol read is a `(`, which has higher precedence, is being placed on the stack. Then d is read output.Step 4
Stack Output 5. Continuing, the solution is obtained in the 9th step. Finally
Stack Output
| ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
Or
12 .(b) (i) Given two sorted lists L1 and L2 write a procedure to compute L1 L2 using only the basic operations. (8) Algorithm to compute L1 L2 : List intersect (List L1, List L2) { List Result; Position L1 pos, L2 pos. Result pos; L1 pos = First (L1); L2 pos = First (L2); Result = Make Empty (NULL); Result pos = First (Result); While (L1 pos! = NULL && L2 pos! = NULL) { if (L1 pos Element < L2 pos Element) L1 pos = Next (L1 pos, L1); else if (L1 pos -> Element > L2 pos -> Element) L2 pos == Next (L2 pos, L2); else { Insert (L1 pos -> Element, Result, Result pos); L1 =; Next (L1 pos, L1); La = Next (L2 pos, L2); Result pos = Next (Result pos, Result); } } return Result; } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
12 b) (ii) Write a routine to insert an element in a linked list. (8) Routine insert: void insert (Element Type x, List L, position P) { Position Tmp cell; Tmp Cell = malloc (Size of (struct node)); if (Tmp Cell == Null) Fatel error ("out of space !!!"); Tmp Cell Element = x; Tmp Cell Next = P Next; P Next = Tmp Cell; } 13. (a) (i) How do you insert an element in a binary search tree? (8) Algorithm routine for Search Tree: Insert (Element Type x, search Tree T) { if (T == Null) {/* create and return a one-node tree */ T = malloc (size of (struct Tree node)); if (T==Null) Fatel Error ("out of space ! '!"); else { T Element = x; T left = T right = Null; } } else if(x < T Element) T left = insert (x, T left); | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
else if(x>T Element) T Right = Insert (x, T Right) Return T; } 13 a) (ii) Show that for the perfect binary tree of height h containing 2h+1 - 1nodes, the sum of the heights of the nodes is 2h+1 - 1 - l(h + 1). (8) The tree consists of 1 node at height A, 2 nodes at height h -1, 22 nodes at height h - 2, and in general 2i nodes at height A - i. The sum of the heights of all nodes is = h + 2(h-1) + 4(h-2) + + 2h-1(1). Multiplying by 2 gives2S = 2h + 4 (h-1) + 8 (h-2) + + 2h(1) we have 2h _ 2(h-1) = 2, 4(h+1) _ 4(h-2) = 4 and so on. S = -h + 2 + 4 + 8 + + 2h-1 + 2h = (2h+1 _ 1) _ (h + 1) Or 13. (b) Given input ( 4371, 1323, 6173, 4199, 4344, 9679, 1989 ) and a hash function h(X) = X(mod lO), show the resulting : (i) Separate chaining table (ii) open addressing hash table using linear probing (iii) open addressing hash table using quadratic probing (iv) open addressing hash table with second hash function h2(X) = 7 - (X mod7). On the assumption that we add collisions to the end of the list (which is the easier way if hash table is being built by hand), the seperate chaining hash table that results is shown here, | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
![]() |
![]() |
(i) Separate chaining table
(ii) Open addressing hash table using linear probing
| ||||
| ||||
| ||||
Data Structures | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
(iii) Open addressing hash table using quadratic probing
(iv) open addressing hash table with second hash function h2(X) = 7 - (X mod7). 1989 cannot be inserted into the table became hash2( 1989 = 6, and the alternative location 5, 1,
7 and 3 are already taken. The table at this point is as follows :
| ||||
| ||||
| ||||
Data Structures | ||||
![]() |
![]() |
![]() |
14. (a) Write down the mergesort algorithm and give its worst case, best case and average case analysis. Merge Routine : Void Merge (Element Type A [ ], Element Type TmpArray [ ], int Lpos, int Rpos, int. Right End) int i, Left End, Num Elements, Tmp pos; Left End = Rpos - 1; Tmp pos = Lpos; Num Elements = Right End - L pos + 1; while (Lpos <= Left End && R pos <= Right End) if(A[Lpos] <=A[Rpos]) TmpArray [Tmppos ++] = A[Lpos ++]; else TmpArray [Tmppos ++] = A [Rpos + 1]; while (Lpos <= LeftEnd) TmpArray [Tmppos ++] = A[Lpos ++]; while (Rpos <= Right End) TmpArray [Tmp pos++] = A[Rpos ++]; for (i = 0; i < NumElements; i++, Right End-- ) A [Right End]= TmpArray [Right End]; } Mergesort Routine : Void Msort f Element Type A [ ], Element Type Tmp Array [ ], int left, int right) { int center; if (Left < Right) { center = (Left + Right)/2; Msort (A, Tmp Array, left, center); Msort (A, Tmp Array, center + 1, Right); Msort (A, Tmp Array, left, center + 1, Right); } } | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
Analysis of mergesort: For n = 1, the time to mergesort is constant, which we will denote by 1. Otherwise, the time to merge sort n number is equal to the to do two recursive merge sorts of size n/2, pins time to merge, which is linear. Therefore the running time is given by the relation. T(1) = 1 T(n) = 2T (n/2) + n Proceeding 2T(n/2) = 2 (2T(n/4) + n/2) = 4T(n/4) + n Continuing in this manner, the obtain T(n) = 2K T(n/2k) + K.n. Using 2K = n, we obtain T(n) = n + nlog2 n The running time of mergesort is O (n log2 n). Or 14.(b) Show how heap sort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102. The input is read in as 142, 643, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102. The result of the heap sort is 879, 811, 572, 434, 543, 123, 142, 65, 111, 242, 453, 102. 879 is removed from the heap and placed at the end. 102 is placed in the hole and bubbled down obtaining. 811, 543, 572, 434,453,123, 142, 65, 111, 242, 102, 879. Continuing the process, we obtain, 572, 543, 142, 434, 453, 123, 102, 65, 111, 242, 811, 879 543, 453, 142, 434, 242, 123, 102, 65, 111, 672, 811, 879 453, 434, 142, 111, 242, 123, 102, 65, 543, 572, 811, 879 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65, 102, 111, 123, 142, 242, 434, 453, 543, 572, 811, 879 | ||
| ||
Data Structures | ||
![]() |
![]() |
![]() |
![]() |
![]() |
15. (a) Find a minimum spanning tree for the graph
Using both Prim's and Kruskals algorithms. Prim's algorithm Prim (G(N,E)) T = 0 B While (B#N) do { Find e = (u, v) of minimum length such that UEB and VEB T T } return T Step 1
| ||||
| ||||
| ||||
Data Structures | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
Step 2
Step 3
Step 4
| ||||
| ||||
| ||||
Data Structures |
![]() |
![]() |
![]() |
![]() |
![]() |
Step 5
Step 6
Step 7
| ||||
| ||||
| ||||
Data Structures |
![]() |
||||
|
|
|
Data Structures |
Step 8
Step 9
Kruskal's Algorithm, T = 0 While ((T has less than n - 1 edges) and E { Choose an edge (u, v) from E of lowest cost delete (u, v) from E. if (u, v) does not create a cycle in T then add (u, v) to T else discard (u, v) }
Data Structures |
![]() |
![]() |
![]() |
![]() |
![]() |
Step 1
Step 2
Step 3
| ||||
| ||||
| ||||
Data Structures | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
Step 4
Step 5
Step 6
| ||||
| ||||
| ||||
Data Structures | ||||
![]() |
![]() |
![]() |
![]() |
![]() |
Step 7
Step 8
Step 9
| ||||
| ||||
| ||||
Data Structures | ||||
![]() |
![]() |
![]() |
15. (b) (i) Write down the Dijkstra's algorithm for the shortest path. (8) Dijkstra's Algorithm: Void Dijkstra (Table T) { Vertex V, W; for( ; ; ) ( V = smallest unknown distance vertex; if (V = = Not A vertex) break; T[V] .known = True; for each W adjacent to V if (!T(W). known) if(T[V]. Dist + CVW < T[W]. Dist) {/* update W */ Decrease (T[W]. Dist to T[V].Dist + (CVW); T[W].path=V; } } }
15. b) (ii) Explain how to modify Dijkstra's algorithm to produce a count of the number of different minimum paths from v to w. (8) Use an array count such that for any vertex x, count [x] is the number of distinct paths from s to u known so far. When a vertex is marked as known, its adjacency list is traversed. Let W be a vertex on the adjacency list. If dv + Cv,w = dw, then increment count [w] by count [v] because all shortest paths from s to u with last edge (v ,w) give a shortest path to w. If dv + Cv,w < dw, then pw and dw get updated. All presimsly known shortest paths to w are now invalid, but all shortest paths to v now lead to shortest paths for w, so set count [w] to equal count [v]. | ||
| ||
Data Structures | ||