BE Computer Engineering (Pokhara University) Data Structure and Algorithms (PU, CMP 160) Question Paper 2079

(a) Define asymptotic notations. Explain Big-O, Big-Omega ($\Omega$) and Big-Theta ($\Theta$) notations with the help of suitable graphs and examples. (8)

(b) Compute the worst-case and best-case running time of the following code segment in terms of Big-O notation, clearly showing the frequency count of each statement: (6)

for (i = 0; i < n; i++) {
    for (j = i; j < n; j++) {
        sum = sum + a[i][j];
    }
}

(a) What is an AVL tree? Construct an AVL tree by inserting the following keys one by one in the given order, showing the rotation performed (LL, RR, LR or RL) at each step where rebalancing is required: 30, 31, 32, 23, 22, 24, 16, 17, 18. (10)

(b) Differentiate between a binary tree and a binary search tree. Write down the in-order, pre-order and post-order traversal sequences of the final AVL tree obtained in part (a). (4)

(a) Consider a weighted, undirected graph with vertices {A, B, C, D, E} and the following edges with weights: A-B(4), A-C(1), C-B(2), B-D(5), C-D(8), C-E(10), D-E(2). Represent this graph using an adjacency matrix. (4)

(b) Apply Dijkstra's shortest path algorithm to find the shortest path from source vertex A to all other vertices. Show the contents of the distance table at every iteration. (8)

(a) Convert the following infix expression into its equivalent postfix expression using a stack, showing the status of the stack and output at each scanned symbol: A + B * (C - D) / E ^ F. (6)

(b) Explain how recursion is implemented internally using the system stack. Write a recursive function to compute the factorial of a non-negative integer and trace its execution for n = 4. (4)

Write an algorithm (or C function) to insert a node at the beginning, at the end, and after a given node in a singly linked list. State one advantage of a linked list over an array.

Insert the keys 72, 27, 36, 24, 63, 81, 92 into a hash table of size 10 using the hash function $h(k) = k \bmod 10$. Resolve collisions using quadratic probing. Show the final contents of the hash table.

Sort the following list using quick sort, taking the first element as the pivot. Show the array after each partitioning step: 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88. State the worst-case time complexity of quick sort and the input condition that causes it.

What is a circular queue? Explain how it overcomes the limitation of a linear queue. Write the conditions to detect queue-full and queue-empty states in a circular queue implemented using an array.

Explain radix sort with a suitable example. Sort the list 170, 45, 75, 90, 802, 24, 2, 66 using radix sort and show the buckets/passes. Compare its complexity with comparison-based sorting algorithms.

Differentiate between Breadth First Search (BFS) and Depth First Search (DFS) traversal of a graph. For the graph having edges {(1,2),(1,3),(2,4),(3,4),(4,5),(3,5)}, write the BFS and DFS traversal order starting from vertex 1.

Construct a binary search tree (BST) by inserting the keys 50, 30, 70, 20, 40, 60, 80, 10 in the given order. Then show the resulting tree after deleting the node with key 30, explaining the deletion case applied.

Write a recursive algorithm for the Tower of Hanoi problem with n disks. Derive its recurrence relation and solve it to show that the number of moves required is $2^n - 1$.