BE Computer Engineering (IOE, TU) Data Structure and Algorithm (IOE, CT 552) Question Paper 2079

(a) Define a stack and explain its LIFO behaviour with the help of PUSH and POP operations. Write the algorithm to convert an infix expression into its equivalent postfix form using a stack. [6]

(b) Using your algorithm (or by tracing a stack), convert the infix expression A + B * (C - D) / E ^ F into postfix, clearly showing the contents of the operator stack at each step. [6]

(a) Construct a Binary Search Tree (BST) by inserting the following keys in the given order: 50, 30, 70, 20, 40, 60, 80, 35, 45. Show the resulting tree. [5]

(b) Write down the preorder, inorder and postorder traversal sequences of the BST obtained in (a). [3]

(c) Delete the node with key 30 from the BST and redraw the tree, explaining the deletion strategy used for a node with two children. [4]

(a) Differentiate between Breadth First Search (BFS) and Depth First Search (DFS) traversal of a graph, mentioning the auxiliary data structure used by each. [4]

(b) For the weighted, directed graph with vertices {A, B, C, D, E} and edges A→B(4), A→C(1), C→B(2), B→D(1), C→D(5), D→E(3), apply Dijkstra's shortest path algorithm taking A as the source. Show the working table for each iteration and give the shortest distance from A to every other vertex. [8]

(a) Explain the working principle of the Quick Sort algorithm and write its recursive algorithm using a partition procedure. [6]

(b) Sort the array {42, 23, 74, 11, 65, 58, 94, 36, 99, 87} using Quick Sort, showing the array after each partitioning step. [4]

(c) Derive the best-case and worst-case time complexity of Quick Sort. Under what condition does the worst case occur? [2]

Write an algorithm (or C function) to insert a new node at the end of a singly linked list and another to delete a node having a given key value. Illustrate both operations with suitable pointer diagrams.

(a) What is recursion? State the conditions a recursive function must satisfy to terminate correctly. [3]

(b) Write a recursive function to compute the n-th term of the Fibonacci sequence and explain why it is inefficient compared to its iterative version, referring to its time complexity. [5]

What is a circular queue and why is it preferred over a linear queue? Write the algorithms for the ENQUEUE and DEQUEUE operations on a circular queue implemented using an array, and state the conditions for queue-full and queue-empty.

(a) Define hashing and explain what is meant by a collision. [3]

(b) Describe linear probing and chaining as collision-resolution techniques, clearly stating one advantage and one disadvantage of each. [5]

What is an AVL tree? Insert the keys 30, 20, 40, 10, 25, 22 one by one into an initially empty AVL tree, showing the balance factors and naming the rotation performed at each point where rebalancing is required.

(a) Define Big-O, Big-Omega (Ω) and Big-Theta (Θ) asymptotic notations. [4]

(b) Determine the time complexity of the following code fragment in terms of Big-O notation, justifying your answer:

for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j = j * 2)
        x = x + 1;

[4]

(a) Write the algorithm for binary search on a sorted array and explain why the array must be sorted. [4]

(b) Compare linear search and binary search in terms of their average-case and worst-case time complexities. [4]

Explain how a stack can be implemented using a linked list. Write the push and pop operations for such an implementation and state one advantage of a linked-list-based stack over an array-based stack.