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 PNext;

After P = PNext;

PNext = After PNext;

Before PNext = After P;

After PNext = 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?

where E - no. of edges and V - no. of verticies

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

for large n.

11.(ii) Design an algorithm to compute the sum of the squares of n numbers.

That is (8)

(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 gives

2S = 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 {an Arbitrary member 2 N}

While (B#N) do

{

Find e = (u, v) of minimum length such that UEB and VEB

T TU {e}

T BU{v}

}

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 0)do

{

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