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

Define asymptotic notation. Explain big-oh (O) notation with example. (1 + 2)

How do you implement enqueue and dequeue operations in linear queue? (3)

What is precondition for binary search? Explain binary search algorithm. (1 + 2)

Explain preorder traversal with example. (3)

What is spanning tree? Explain minimum spanning tree in brief. (1 + 2)

Explain algorithm for converting an infix expression to postfix using stack. Use this algorithm to convert $(A + B - C) * D$ to postfix. (4 + 2)

OR

List some applications of stack. Explain algorithm for evaluating a postfix expression using stack with suitable example. (1.5 + 4.5)

Compare linked list with array. How do you insert and remove nodes in singly linked list? (2 + 4)

OR

What is circular linked list? How do you implement stack using linked list? (1.5 + 4.5)

Explain quick sort along with its time complexity. Trace the execution of quick sort algorithm with the array of numbers 30, 20, 15, 37, 45, 9, 23, 15, and 3. (2 + 4)

Define AVL tree. Construct AVL tree for the sequence 27, 66, 80, 9, 4, 14, 28, 8, and 6. (1 + 5)

Use Dijkstra's shortest path algorithm to find the shortest path between the vertices a and z in the graph given below. (6)

Graph (undirected, weighted) with vertices a, b, c, d, e, z and edges: a–b = 2, a–c = 3, b–d = 5, b–e = 2, c–e = 5, d–e = 1, d–z = 2, e–z = 4.