Define Big Theta and Omega notations. Is a function b . log(n) where b is a positive constant? Justify.

On what input data does Quick sort algorithm for sorting exhibit its worst case behaviour? Justify with an example of 8 elements. Determine the maximum space needed.

Prove that all the leaves of a binary tree will be traversed in the same sequence in all the three traversals.

Draw a binary tree whose preorder and inorder traversals are

A B D C E G H I J K F
B D A G E J I K H C F

If the complexity of the algorithm can be expressed as calculate the complexity of the following program segment:
i
loop(i
doit
I 2

2. Define a spanning tree. Write an algorithm to determine maximum spanning tree·of a weighted graph. Also argue for the correctness of your algorithm. Also determine the time complexity of the algorithm. Will an edge of highest cost always be in the solution obtained?

What is hashing Explain the following terms used in it:

Hashing function

Synonyms

Overflow

Collision resolution

Define an AVL tree. Where is it used and why Construct one such tree for the following list of elements:

6+8

A circular singly linked list contains integer elements. Variable pointer points to the last node in the list. Write a procedure to print the positive (not including zero) elements in the list.

Explain three applications each of stacks and queues in Computer science.

Change the following infix expression to post-fix and prefix expressions.
f
Show all the steps. Why is post-fix. preferred to infix form Which data structure is used for it and why?

Describe the data structure to represent the following:

Sparse Matrix

Priority Queue

Threaded Link

An algebraic expression of the form
anx^n a1x ao

How can a sparse matrix be stored as a linked list so that the element of a given row i and column j can be accessed easily? Store the following matrix in the suggested format:

0 0 0 0 0 0
1 0 0 0 0 2
0 3 0 0 0 5
0 0 0 4 0 0

Write the procedure to reverse a singly linked list without creating an extra linked
list.

7. Design a method for keeping two stacks within a single array S (space size) so that neither the stack overflows until all of memory reserved is used and an entire stack is never shifted to a different location within the array. Write C routines for push1, push2, pop1 and pop2 to manipulate the two stacks.

8. Explain the following:

Difference between Class P and Class NP

Difference between Internal and External sorting

Difference between Linear and Non-linear data structures

Different representations of a graph

Difference between Dynamic Programming and Divide and Conquer approach