Solution

• Topological Sort → Can be done using DFS (by finishing times). ✅

• Strongly Connected Components (SCCs) → Kosaraju’s and Tarjan’s algorithms use DFS. ✅

• Solving Maze Problem → DFS is a valid approach to explore paths in a maze. ✅

• Finding minimum distance in an unweighted graph → This requires Breadth First Search (BFS), not DFS, because BFS ensures the shortest path in an unweighted graph. ❌

Solution

Solution

Solution

Solution

Solution

The difference between Quicksort and Randomized Quicksort lies mainly in the way the pivot element is chosen. Let’s analyze each option:

1. Selection of Pivot element ✅

   • Quicksort: Pivot is chosen deterministically (e.g., always first element, last element, or middle element).

   • Randomized Quicksort: Pivot is chosen randomly (uniformly among available elements).
     → This is the key difference.

2. Worst case time complexity ❌

   • For both, the worst case is still O(n²).

   • Randomization only reduces the chance of hitting the worst case often, but it does not eliminate it.

3. Best case time Complexity ❌

   • Both have the same best case: O(n log n) (when pivot splits the array evenly).

   • Randomization doesn’t change the best case.

4. Final Output ❌

   • Both produce the same sorted output.

   • Randomization only affects the process, not the final result.

Solution

Solution

Match the pairs:

• (A) BFS → Queue (IV)

• (B) DFS → Stack (I)

• (C) Heap Sort → Priority Queue (III)

• (D) Storage on secondary storage devices → B-Trees (II)

Solution

Solution

Solution

Solution

Solution

When implementing a database, the most appropriate data structure depends on what part of the database you’re focusing on. Among common options, the standard and most suitable choice is:

B-Tree (or B+ Tree)

• Used by almost all modern databases (MySQL, PostgreSQL, Oracle, etc.) to implement indexes.

• Provides efficient search, insert, delete, and range queries in O(log n) time.

• Optimized for disk storage and block reads, making it ideal for large datasets.

Other data structures used in databases:

1. Hash Tables

   • Used for hash indexes and quick equality lookups (e.g., WHERE id = 100).

   • Very fast for exact matches but not good for range queries.

2. Heaps

   • Used to store unsorted table data.

   • Simple structure but inefficient for searches without indexes.

3. Linked Lists

   • Used internally for things like transaction logs and some in-memory structures.

4. Trie / Radix Trees

   • Sometimes used for full-text search or prefix matching.

Solution

Each node is having a successor node in a Linked List.

• In a linked list, every node contains data and a pointer (or reference) to its successor node (the next node in the sequence).

• The last node points to NULL (in a singly linked list) or back to the head (in a circular linked list).

Solution

Solution

// Structure of node
struct Node {
    int data;
    struct Node* link;
};

// Function to get last node
struct Node* getLastNode(struct Node* head) {
    struct Node* temp = head;

    // Traverse until last node
    while (temp -> link != NULL) {
        temp = temp -> link;
    }

    return temp;  // Now temp points to last node
}
  

Solution

Solution

Solution

Solution

Solution

Solution