Data Structures and Algorithms — Winter 2022

Define algorithm. Discuss key characteristics of algorithms.

Arrange the following functions in increasing order of growth. 2n , n2 , 1, 0 n log n

Explain Worst Case, Best Case and Average Case Complexity.

Give the difference between Stack and Queue.

Write a brief note on Priority Queue.

Explain how to evaluate postfix expression using stack with suitable example.

Write algorithm to insert and delete elements in circular queue.

Explain the structure of Circular linked list.

Write user defined ‘C’ function to insert node at a specific location in singly linked list.

Write an algorithm of Selection Sort. Also, explain it with suitable example.

Compare and contrast array with linked list.

Write user defined ‘C’ function to delete the last node in doubly linked list.

Write an algorithm of Insertion Sort. Also, explain it with suitable example.

Define following with respect to Tree:

In Degree ii) Out Degree iii) Leaf

Write a brief note on AVL Tree.

Create an algorithm for multiplying large Integers using divide and conquer approach.

Explain double hashing in brief.

Compare and contrast linear search with binary search.

Create an algorithm to find the kth minimum element in a Binary Search Tree.

Give the difference between BFS and DFS.

Explain Backtracking Method.

Explain activity selection problem using greedy method with suitable example.

Explain principle of optimality.

Explain Prim’s algorithm.

Explain knapsack problem using dynamic programming approach with suitable example.