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

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

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

What is asymptotic analysis? Explain theta notation with example.

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

Explain tail recursion with example. Compare recursion with iteration.

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

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

Write Dijkstra’s algorithm to find shortest path between any two vertices of a graph.

Write a program to implement insertion sort.

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

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