BIT Data Structure and Algorithms

What is data Structure? Explain an array as an abstract data type.

Define ADT. Explain array as an ADT.

Define data type and ADT. What are the benefits of using ADT? Explain

Explain big oh(O) notation with suitable example.

What is time complexity? Explain big oh notation with example.

What is space complexity? Explain omega notation with example.

Explain algorithm to convert an infix expression to postfix using stack? Use this algorithm to convert \((A+B)*C-D\) to postfix.

How stack is used in recursion? Explain different stack operations. Explain algorithm to convert an infix expression to postfix using stack.

What is stack? Explain different stack operations. Explain algorithm to evaluate postfix expression.

Define priority queue. How do you implement priority queue? Explain.

Explain priority queue with example. What is circular queue?

What is circular queue? How can you implement circular queue?

Define recursion. Explain Tower of Hanoi algorithm in detail.

What are the benefits of using recursion? Write a recursive function to find \(n^{th}\) Fibonacci number.

Define recursion. Explain Tower of Hanoi (TOH) with example.

How can you implement queue using linked list? Explain.

Explain singly linked list with example. Compare singly linked list with doubly linked list.

How can we use linked list to implement queue? Explain.

Write short notes on:

a. Doubly circular linked list

b. Breadth first search

What is binary tree? Explain different application of binary tree.

Explain complete binary tree with example. Starting with an empty binary search tree, show the effect of successively adding the following elements: 47, 50, 25, 2 7, 17, 61, 5, and 26. Also, traverse the resulting tree in pre-order, in-order, and post-order.

Explain different applications of binary tree.

Explain almost complete binary tree with example. How do you insert, search, and delete nodes in a binary search tree? Explain with suitable example?

What are different applications of binary tree? Explain.

Explain merge sort along with its time complexity. Use this algorithm to sort array of numbers given below:

25, 37, 48, 25, 23, 17, 31, 45, 7, 21, 15, 8, 11

Explain quick sort algorithm. Use this algorithm to sort the numbers 35, 82, 18, 54, 13, 31, 20, 69, and 19.

Discuss the limitation of choosing first element as pivot in quick sort. Using merge sort algorithm, sort the numbers 40, 6, 5,21, 3, 100, 90, 7, 8, 12, 30.

Explain sequential search. How is it different from binary search?

Define hashing. Explain quadratic probing with example.

Explain collision and collision resolution in hashing. What is double hashing?

Why do we need hashing? Explain quadratic probing.

Write short notes on:

a. Linear Search

b. Minimum Spanning Tree

What is shortest path algorithm? Use Dijkstra’s algorithm to find shortest path between the vertices of a and z in the graph given below.

What is graph traversal? Explain breadth first search.

Define spanning tree. Explain minimum spanning tree with example.

Explain adjacency matrix representation of graphs with example.