What is asymptotic analysis? Explain theta notation with example. [5]

Write short notes on: a. Abstract data type b. Circular linked list [5]

How can you use linked list to implement stack? Explain. [5]

Explain queue as an ADT. Write a program to implement linear queue. Compare linear queue with circular queue. [10]

Explain tail recursion with example. Compare recursion with iteration. [5]

Define hash table and hash function. What is collision in hashing? Explain linear probing and quadratic probing with suitable example. [10]

Explain binary search with an example. What is the time complexity of binary search? [5]

Trace selection sort algorithm with array of numbers 2, 81, 6, 45, 11, 21, 23, 41, and 11. [5]

Write a program to implement insertion sort. [5]

Explain push and pop operations of stack. What are different applications of stack? [5]

Explain AVL tree with example. Also, explain balancing algorithm for this tree. [10]

Write Dijkstra's algorithm to find shortest path between any two vertices of a graph. [5]