DSA Model Questions and Solutions (4)

Model Question

DSA(IT 237)

Group “A”

Very Short Questions Answer:

1. Define Big oh(O) notation.

Ans: Big Oh Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows. In other words, it calculates the worst-case time complexity of an algorithm. Big O Notation in Data Structure describes the upper bound of an algorithm’s runtime.

2. Write any two applications of priority Queue.

Ans: Few applications of priority Queue are :

• It is also used in Operating System for load balancing , interrupt handling. 
• Heap sort is typically implemented using Heap which is an implementation of Priority Queue.

3. Write the structure of circular linked list.

Ans: Circular linked lists are typically implemented using a singly linked list data structure. This means that each node in the list is connected to the next node via a pointer. The last node in the list is then connected back to the first node, creating the ring-like structure.

4. Define stack as an ADT.

Ans: A stack is an Abstract Data Type (ADT), that is popularly used in most programming languages. It is named stack because it has the similar operations as the real-world stacks, for example − a pack of cards or a pile of plates, etc.

5. Write recursive definition to find nth Fibonacci number.

Ans: Here’s a recursive Java method to find the nth Fibonacci number:

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10; // Change the value of n as needed
        int result = fibonacci(n);
        System.out.println("The " + n + "th Fibonacci number is: " + result);
    }

    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

6. Write any two differences between merge sort and quick sort.

Ans: The differences are:

7. Define balance binary tree.

Ans: A balanced binary tree, also referred as a height balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

8. Why hashing is considered as an efficient searching technique?

Ans: Hashing means using some function or algorithm to map object data to some representative integer value. It is also called hash code (or simply hash) that can be used as a way to narrow down our search when looking for the item in the map. So, Hashing is considered as an effective searching technique.

9. Define adjacency matrix representation of graph.

Ans: An adjacency matrix is a way of representing a graph as a matrix of Booleans (0’s and 1’s). A finite graph can be represented in the form of a square matrix on a computer, where the Boolean value of the matrix indicates if there is a direct path between two vertices.

10. Write any two applications of tree data structure.

Ans: Applications are:

•  Tree data structures are commonly used in decision-making algorithms in artificial intelligence, such as game-playing algorithms, expert systems, and decision trees
• Tree data structures, such as binary search trees, are commonly used to implement efficient searching and sorting algorithms.

Group “B”

Short Answer Questions:

1. Implement a “Circular Queue” using an array . Provide the algorithm for enqueue and dequeue operations.

Ans : Implementation of circular queue using an array is shown below:

public class CircularQueue {
    private int[] queue;
    private int front;  // Front of the queue
    private int rear;   // Rear of the queue
    private int capacity;
    private int size;   // Current size of the queue

    public CircularQueue(int capacity) {
        this.capacity = capacity;
        this.queue = new int[capacity];
        this.front = 0;
        this.rear = -1;
        this.size = 0;
    }

    // Method to enqueue an element into the circular queue
    public void enqueue(int data) {
        // Check if the queue is full
        if (isFull()) {
            System.out.println("Queue is full. Enqueue operation failed.");
            return;
        }

        // Move rear pointer circularly
        rear = (rear + 1) % capacity;
        // Add the element to the queue
        queue[rear] = data;
        // Increment the size of the queue
        size++;
        System.out.println("Enqueued: " + data);
    }

    // Method to dequeue an element from the circular queue
    public int dequeue() {
        // Check if the queue is empty
        if (isEmpty()) {
            System.out.println("Queue is empty. Dequeue operation failed.");
            return -1;
        }

        // Get the element to dequeue
        int data = queue[front];
        // Move front pointer circularly
        front = (front + 1) % capacity;
        // Decrement the size of the queue
        size--;
        System.out.println("Dequeued: " + data);
        return data;
    }

    // Method to check if the circular queue is full
    public boolean isFull() {
        return size == capacity;
    }

    // Method to check if the circular queue is empty
    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(5);

        cq.enqueue(1);
        cq.enqueue(2);
        cq.enqueue(3);
        cq.enqueue(4);
        cq.enqueue(5);

        cq.enqueue(6); // Queue is full, should print error message

        cq.dequeue();
        cq.dequeue();
        cq.dequeue();
        cq.dequeue();
        cq.dequeue();

        cq.dequeue(); // Queue is empty, should print error message
    }
}

The enqueue and dequeue a algorithm is given below in a stepwise manner.

Enqueue Algorithm:

• Step 1: Check if the queue is full or not by comparing the number of elements in the queue with the maximum size of the queue.
• Step 2: If the queue is full, then display an overflow message and return.
• Step 3: If the queue is not full, then increment the rear pointer and insert the new element at the position pointed by the rear pointer.

Dequeue Algorithm:

• Step 1: Check if the queue is empty or not by comparing the number of elements in the queue with 0.
• Step 2: If the queue is empty, then display an underflow message and end the program.
• Step 3: If the queue is not empty, then remove the element at the front of the queue and increment the front pointer.

2. Define recursive function.

Ans: A recursive function is a function that solves a problem by solving smaller instances of the same problem. This technique is commonly used in programming to solve problems that can be broken down into simpler, similar sub problems.

3. Define analysis of an algorithm. Explain time and space complexity of an algorithm.

Ans: The analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem.

Time Complexity:

Time complexity is defined in terms of how many times it takes to run a given algorithm, based on the length of the input. Time complexity is not a measurement of how much time it takes to execute a particular algorithm because such factors as programming language, operating system, and processing power are also considered.

Space Complexity:

When an algorithm is run on a computer, it necessitates a certain amount of memory space. The amount of memory used by a program to execute it is represented by its space complexity. Because a program requires memory to store input data and temporal values while running, the space complexity is auxiliary and input space.

4. Write java method to implement PUSH and POP operation in a stack with an array.

Ans: Implement of PUSH and POP operation in a stack with an array:

public class Stack {
    private int maxSize;
    private int[] stackArray;
    private int top; // index of the top element
    
    // Constructor to initialize the stack with a maximum size
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        this.stackArray = new int[maxSize];
        this.top = -1; // Stack is initially empty
    }
    
    // Method to push an element onto the stack
    public void push(int element) {
        if (isFull()) {
            System.out.println("Stack overflow! Cannot push element " + element);
            return;
        }
        stackArray[++top] = element;
        System.out.println("Pushed element: " + element);
    }
    
    // Method to pop an element from the stack
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack underflow! Cannot pop element.");
            return -1; // Returning -1 to indicate stack underflow
        }
        int poppedElement = stackArray[top--];
        System.out.println("Popped element: " + poppedElement);
        return poppedElement;
    }
    
    // Method to check if the stack is empty
    public boolean isEmpty() {
        return top == -1;
    }
    
    // Method to check if the stack is full
    public boolean isFull() {
        return top == maxSize - 1;
    }
    
    public static void main(String[] args) {
        Stack stack = new Stack(5); // Creating a stack with a maximum size of 5
        
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        
        // Trying to push more elements than the stack size
        stack.push(6);
        
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        stack.pop();
        
        // Trying to pop from an empty stack
        stack.pop();
    }
}

5. Explain post order and pre order traversal of a binary tree.

Ans: Traversing a tree means visiting and outputting the value of each node in a particular order.

Here is the diagram we will be working with:

1. Preorder Traversal:

The order here is Root, Left, Right.

Using the same diagram above, we have:

A, B, D, E, C, F, G

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expressions on an expression tree.

2. Post order traversal:

Postorder traversal is used to delete the tree. Please see the question for the deletion of a tree for details. Postorder traversal is also useful to get the postfix expression of an expression tree

The order for post order traversal is Left, Right, Root.

Here is the output:

D, E, B, F, G, C, A

Group “C”

Short answer questions:(Any three)

1. Compare pros and cons of implementing a stack using an array and a linked list.

Ans:

Pros and Cons of Stack Implementation Using Array 

There are various pros and cons of a stack implementation using an array, they are:

Pros: 

• It requires no extra memory to store the pointers in stack implementation using an array.
• More efficient in terms of time, compared to stack implementation using linked-list.

Cons: 

• The size of the stack is fixed, so it cannot increase and decrease stack implementation using an array.
• Insertion and deletion in an array are quite difficult as it stores the elements in consecutive memory locations.

Pros and Cons of Stack Implementation Using linked list

Pros

• The size of the stack can be adjusted dynamically as the linked list can grow or shrink according to the elements pushed or popped.
• Linked list implementation provides more flexibility than an array-based implementation as elements can be added or removed anywhere in the list.

Cons

• Managing pointers in linked lists is more challenging compared to arrays, leading to increased risk of bugs and data corruption.
• Operations on the linked list take more time compared to arrays, as accessing elements in linked lists require traversing through multiple nodes.

2. Provide the algorithm for inserting a node at the beginning of of a “Singly Linked List”. Show how the operations are performed.

Ans: The algorithm for inserting a node at the beginning of of a “Singly Linked List” is as follows:

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    // Method to insert a node at the beginning of the linked list
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
    }

    // Method to display the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        SinglyLinkedList myList = new SinglyLinkedList();

        // Insert nodes at the beginning
        myList.insertAtBeginning(3);
        myList.insertAtBeginning(5);
        myList.insertAtBeginning(7);

        // Display the linked list
        myList.display();
    }
}

3. Implement AVL tree.

Ans: A basic implementation of an AVL tree in Java. This implementation includes methods for insertion, deletion, and traversal (in-order traversal). AVL tree is a self-balancing binary search tree where the height difference between the left and right subtrees of any node is at most 1.

class Node {
    int key, height;
    Node left, right;

    Node(int d) {
        key = d;
        height = 1;
    }
}

class AVLTree {
    Node root;

    int height(Node N) {
        if (N == null)
            return 0;
        return N.height;
    }

    int max(int a, int b) {
        return (a > b) ? a : b;
    }

    Node rightRotate(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        x.right = y;
        y.left = T2;

        y.height = max(height(y.left), height(y.right)) + 1;
        x.height = max(height(x.left), height(x.right)) + 1;

        return x;
    }

    Node leftRotate(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        y.left = x;
        x.right = T2;

        x.height = max(height(x.left), height(x.right)) + 1;
        y.height = max(height(y.left), height(y.right)) + 1;

        return y;
    }

    int getBalance(Node N) {
        if (N == null)
            return 0;
        return height(N.left) - height(N.right);
    }

    Node insert(Node node, int key) {
        if (node == null)
            return (new Node(key));

        if (key < node.key)
            node.left = insert(node.left, key);
        else if (key > node.key)
            node.right = insert(node.right, key);
        else
            return node;

        node.height = 1 + max(height(node.left),
                              height(node.right));

        int balance = getBalance(node);

        if (balance > 1 && key < node.left.key)
            return rightRotate(node);

        if (balance < -1 && key > node.right.key)
            return leftRotate(node);

        if (balance > 1 && key > node.left.key) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        if (balance < -1 && key < node.right.key) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    Node minValueNode(Node node) {
        Node current = node;

        while (current.left != null)
            current = current.left;

        return current;
    }

    Node deleteNode(Node root, int key) {
        if (root == null)
            return root;

        if (key < root.key)
            root.left = deleteNode(root.left, key);
        else if (key > root.key)
            root.right = deleteNode(root.right, key);
        else {
            if ((root.left == null) || (root.right == null)) {
                Node temp = null;
                if (temp == root.left)
                    temp = root.right;
                else
                    temp = root.left;

                if (temp == null) {
                    temp = root;
                    root = null;
                } else
                    root = temp;
            } else {
                Node temp = minValueNode(root.right);
                root.key = temp.key;
                root.right = deleteNode(root.right, temp.key);
            }
        }

        if (root == null)
            return root;

        root.height = max(height(root.left), height(root.right)) + 1;

        int balance = getBalance(root);

        if (balance > 1 && getBalance(root.left) >= 0)
            return rightRotate(root);

        if (balance > 1 && getBalance(root.left) < 0) {
            root.left = leftRotate(root.left);
            return rightRotate(root);
        }

        if (balance < -1 && getBalance(root.right) <= 0)
            return leftRotate(root);

        if (balance < -1 && getBalance(root.right) > 0) {
            root.right = rightRotate(root.right);
            return leftRotate(root);
        }

        return root;
    }

    void preOrder(Node node) {
        if (node != null) {
            System.out.print(node.key + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    public static void main(String[] args) {
        AVLTree tree = new AVLTree();

        tree.root = tree.insert(tree.root, 10);
        tree.root = tree.insert(tree.root, 20);
        tree.root = tree.insert(tree.root, 30);
        tree.root = tree.insert(tree.root, 40);
        tree.root = tree.insert(tree.root, 50);
        tree.root = tree.insert(tree.root, 25);

        System.out.println("Preorder traversal of constructed tree is : ");
        tree.preOrder(tree.root);

        tree.root = tree.deleteNode(tree.root, 30);

        System.out.println("\nPreorder traversal after deletion of 30 :");
        tree.preOrder(tree.root);
    }
}

This implementation covers basic functionality such as insertion, deletion, and pre-order traversal of an AVL tree.

4. Quick Sort:10,13,14,19,12,16,25,18,20.

Ans:

the Quick Sort algorithm step by step with the given array: 10,13,14,19,12,16,25,18,20.

Quick Sort is a divide-and-conquer sorting algorithm. Here’s how it works:

1. Choose a Pivot: First, we need to choose a pivot element from the array. There are various ways to choose a pivot; a common approach is to select the last element. In our case, let’s choose 2020 as the pivot.
2. Partitioning: Rearrange the array so that all elements smaller than the pivot are moved to its left, and all elements greater than the pivot are moved to its right. The pivot element will be placed in its correct sorted position.After partitioning, the array might look like this: [10,13,14,19,12,16,18,20,25][10,13,14,19,12,16,18,20,25]Here, 2020 is in its correct sorted position, and all elements less than 2020 are to the left, while elements greater than 2020 are to the right.
3. Recursion: Recursively apply the above steps to the sub-arrays on the left and right of the pivot until the entire array is sorted.

Now, let’s go through each step in detail:

1. Choose Pivot: We choose 2020 as the pivot element.
2. Partitioning: Rearrange the array so that all elements smaller than 2020 are to its left, and all elements greater than 2020 are to its right.[10,13,14,19,12,16,18,20,25][10,13,14,19,12,16,18,20,25]
3. Recursion:
   • Left Sub-array: [10,13,14,19,12,16,18][10,13,14,19,12,16,18]
   • Right Sub-array: [25][25] (already sorted)

Now, let’s repeat the process for each sub-array:

Left Sub-array:

1. Choose Pivot: Choose 1818 as the pivot.
2. Partitioning:[10,13,14,12,16,18,19][10,13,14,12,16,18,19]
3. Recursion:
   • Left Sub-array: [10,13,14,12,16][10,13,14,12,16]
   • Right Sub-array: [19][19] (already sorted)

Repeat the process for the left sub-array:

Left Sub-array:

1. Choose Pivot: Choose 1616 as the pivot.
2. Partitioning:[10,13,14,12,16][10,13,14,12,16]
3. Recursion:
   • Left Sub-array: [10,13,14,12][10,13,14,12] (already sorted)
   • Right Sub-array: [][] (empty)

Now, for the right sub-array of the first partition:

Right Sub-array:

Since it contains only one element, [19][19], it’s already sorted.

After all the recursive calls, the sorted array becomes:

[10,12,13,14,16,18,19,20,25][10,12,13,14,16,18,19,20,25]

This completes the Quick Sort algorithm. Each element is now in its correct sorted position.

Group “D”

Long Answer Questions:

1. Define a “Binary Search Tree(BST)” and its properties. Provide the algorithm for insertion and deletion in BST.

Ans: BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Properties of Binary Search Tree:

• A BST is a recursive object that consists of the root node and two smaller binary search trees. This means many BST problems can be solved using recursion.
• A BST combines the fast search capabilities of a sorted array with the flexibility of insertion and deletion in a linked list.
• Many different BSTs can represent the same set of keys and values.
• The BST property allow us to explore all keys in sorted order by performing an in-order tree traversal.
• In a BST new nodes are inserted into null links at the bottom of tree, preserving the tree structure.

Algorithm for insertion in Binary Search Tree

Step 1 : Start at the root node of the BST.

Step 2: Compare the value of the new node with the value of the root node.

Step 3 : If the value of the new node is less than the value of the root node, go to the left subtree of the root node.

Step 4 : If the value of the new node is greater than the value of the root node, go to the right subtree of the root node.

Step 5 : Repeat steps 2-4 recursively until a leaf node is reached.

Step  6 : Insert the new node as a leaf node at the appropriate position in the BST

Algorithm for deletion in Binary Search Tree

Step 1 : Start at the root node of the BST.

Step 2 : Compare the value of the node to be deleted with the value of the root node.

Step 3 : If the value of the node to be deleted is less than the value of the root node, go to the left subtree of the root node.

Step 4 : If the value of the node to be deleted is greater than the value of the root node, go to the right subtree of the root node.

Step 5 : If the value of the node to be deleted is equal to the value of the root node, perform the deletion operation.

Step 6 : If the node to be deleted is a leaf node or has only one child, perform the deletion operation directly.

Step 7 : If the node to be deleted has two children, find the minimum value in the right subtree to replace it with and perform the deletion operation.

Step 8 : Rebalance the tree if necessary to maintain its height-balanced property.

2. Compare merge sort and heap sort algorithms in terms of time complexity and stability.

Ans: Here’s a comparison between Merge Sort and Heap Sort in terms of time complexity and stability:

Here’s a brief explanation of each property:

1. Time Complexity: Both Merge Sort and Heap Sort have a time complexity of O(n log n) in the average, best, and worst cases.
2. Space Complexity: Merge Sort typically requires O(n) additional space for temporary arrays used during the merge process. Heap Sort, if implemented using array representation of the heap, is in-place and requires only O(1) additional space.
3. Stability: Merge Sort is stable, meaning it preserves the relative order of equal elements. Heap Sort, however, is not stable. Equal elements may not necessarily retain their relative order after sorting.
4. In-place Sorting: Merge Sort is not an in-place sorting algorithm, as it requires additional space for temporary arrays. Heap Sort, on the other hand, can be implemented in-place, particularly when using array representation of the heap.