Full Marks: 60
Pass Marks: 24
Time: 3 hours

Attempt any two questions: (2 x 10 = 20)

1. Trace out Infix to Postfix conversion algorithm with given Infix expression.
   A + (((B-C) * (D-E) + F)/G) $ (H-I)
   Evaluate the postfix expression acquired from above for the given values:
   A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1.
2. Explain the structure of Doubly Linked List (DLL). Differentiate the difference between DLL and Doubly Circular Linked List (DCLL). Explain the procedures to insert a node in DLL at the beginning and at the last.
3. Define Binary Search Type (BST). Write an algorithm to insert a node in non-empty BST. Construct BST from the data:
   10, 20, 30, 25, 27, 7, 4, 23, 26, 21

Attempt any eight questions: (8 x 5 = 40)

4. Write C function to insert an item circular queue in array implementation. Write assumptions, you need.
5. What is an algorithm? What is to analyze in algorithm? Define Big C = Oh notation for time complexity measurement of algorithm.
6. State TOH problem. Explain a recursive algorithm to solve the problem.
7. Trace selection – sort algorithm for the following data:
   42, 23, 74, 11, 65, 58, 94, 86
8. What is Hashing? What collision means? State collision resolution techniques. Explain one of them in brief.
9. What is weighted graph? Explain Depth-first traversal of a graph.
10. Create a Huffman tree for the following set of data:

    Characters	a	b	c	d	e	f
    Probability	48	13	11	16	07	05
    Encode	0	101	100	111	1101	1100

11. What is dynamic memory allocation? How it is achieved for declaring low dimensional array? Explain.
12. Explain efficiency of
    • a) Binary Searching
    • b) Quick sort
13. Write short notes on (any two):
    • a) Queue in circular linked list
    • b) ADT
    • c) MST (Minimum Cost Spanning Tree) of a graph.