Master in Data Science (SMS, TU) Data Structures and Algorithms Question Paper 2081 Nepal

Why do you study efficiency of algorithms? What is big-oh (O) notation? (1.5 + 1.5)

What is priority queue? Why do we need this queue? (1.5 + 1.5)

Compare recursion with iteration. Write a recursive function to find greatest common divisor. (1.5 + 1.5)

What are the benefits of using linked list? Compare singly linked list with doubly linked list. (1.5 + 1.5)

Compare linear search with binary search? What are their time complexities? (2 + 1)

Explain algorithm to convert an infix expression to postfix using stack. Use this algorithm to convert $A * B + C / D - E$ into postfix. (3 + 3)

OR

List some applications of stack. Explain algorithm to evaluate a postfix expression using stack with suitable example. (1 + 5)

Explain merge sort. Trace the execution of merge sort algorithm with the array of numbers 34, 23, 17, 31, 45, 7, 21, 15, 8, and 1. (2 + 4)

OR

Explain shell sort. Trace the execution of shell sort algorithm with the array of numbers 34, 23, 17, 31, 45, 7, 21, 15, 8, and 1. (2 + 4)

Explain linear probing. Suppose, the set of keys is $\{17, 12, 14, 10, 49, 58, 9, 50\}$, $m = 10$, and $h(x) = x \bmod 10$. Show the effect of successively inserting these keys using quadratic probing. (2 + 4)

What is AVL tree. Construct AVL tree for the sequence 21, 26, 30, 9, 4, 14, 28, and 18. (1 + 5)

What is graph traversal? Explain breadth first search (BFS) algorithm for traversing graphs with example. (1 + 5)