MCQ

Bellman-Ford Algorithm

  • Purpose: Find the shortest paths from a single source vertex in a weighted graph.

  • Key Feature:

    • Can detect negative weight cycles.

    • Incorrect Statements:

      • Can only handle graphs with positive edge weights (False)

      • Has a time complexity of O(V log V) (False)

      • Uses a priority queue (False)

  • Time Complexity: O(V * E)

  • Iterations Required:

    • V - 1 iterations to find the shortest paths.

Negative Weight Cycles

  • Detection Indication:

    • Indicates that the shortest paths are undefined due to the cycle.

Application Scenarios

  • Best suited for graphs with negative edge weights or the possibility of negative weight cycles.

Breadth-First Search (BFS)

  • Data Structure Used: Queue.

  • Visitation Order: Level-by-level.

  • Time Complexity: O(V + E) when represented as adjacency list.

  • Disconnected Graph Behavior:

    • BFS will only visit nodes in the connected component of the starting node.

  • Common Application: Finding the shortest path in an unweighted graph.

Binomial Heap

  • Basis Data Structure: Binomial Trees.

  • Time Complexity of extractMin(): O(log n).

  • Existence of Binomial Trees: At most one binomial tree of a specific degree can exist.

  • Combining Two Heaps: Use operation called Union.

Binary Tree Boundary Traversal

  • Components: Root, left boundary, leaf nodes, right boundary.

  • Order for Right Boundary Printing: Bottom to top.

  • Excluded Nodes: Leaf nodes are excluded from left and right boundary.

  • Time Complexity: O(n).

  • Special Case for Left Boundary: If a left subtree is missing but a right subtree exists, the right child node is included in the left boundary.

Depth-First Search (DFS)

  • Implicit Data Structure: Stack (through call stack structure).

  • Visitation Order: Depth-first.

  • Time Complexity: O(V + E) when represented as an adjacency list.

  • Cycle Behavior During DFS: It might enter an infinite loop if not handled properly.

  • Common Applications: Detecting cycles in a directed graph.

Dial's Algorithm

  • Efficiency Suitability: Best for positive integer edge weights within a limited range.

  • Primary Data Structure: Buckets (an array of queues).

  • Variation of Which Algorithm: Dijkstra's Algorithm.

  • Time Complexity Dependency: The maximum edge weight and the number of vertices.

  • Useful When: The edge weights are small integers and the graph is dense.

Heap Sort

  • Time Complexity: O(n log n).

  • Basis Data Structure: Heap.

  • Stability: Unstable sorting algorithm.

  • Initial Array Conversion in Heap Sort: Converted into a Max-heap.

  • Space Complexity: O(1) (in-place).

K-ary Heap

  • Children per Non-leaf Node: K children.

  • Time Complexity of extractMin(): O(k log n).

  • Parent Calculation Formula: (i - 1) / K.

  • Advantages Over Binary Heap: Better cache locality for larger K.

Recover Binary Search Tree Problem

  • Primary Goal: To correct the positions of two swapped nodes in a BST.

  • Traversal Method for Detection: Inorder traversal.

  • Inorder Result Identification: If it produces a sequence showing two nodes swapped (e.g., [1, 5, 3, 4, 2, 6] indicates nodes 5 and 2).

  • Time Complexity of Efficient Solution: O(n).

  • Indication of Swapped Nodes: A node's value is less than the previous node's value.

Topological Sort

  • Applicable Graph Type: Directed acyclic graphs (DAGs).

  • Primary Purpose: To order vertices with the condition that for every directed edge (u, v), vertex u comes before vertex v.

  • Data Structure in Kahn's Algorithm: Queue.

  • Cycle Detection: If a cycle exists, the algorithm will detect it and return an error or null.

  • Time Complexity of Kahn's Algorithm: O(V + E).

Vertical Order Traversal

  • Data Structure for HD: TreeMap to maintain sorted order.

  • Traversal Method Basis: Level order traversal (BFS).

  • HD Representation: Position of the node relative to the root in the horizontal direction.

  • Time Complexity: O(n log n).

  • Order of Nodes with Same HD: By their level (top to bottom).

Tree View Algorithms

  • Traversal Method for Tree View: Level order traversal (BFS).

  • Primary Data Structure for BFS: Queue.

  • Data Structure for Maintaining Horizontal Distances: TreeMap.

  • Left View Output Addition: The first node in the level is added.

  • Pair Class Purpose in Top View algorithm: Stores the node's value and its horizontal distance.

Winner Tree

  • Primary Purpose: Merging sorted lists efficiently.

  • Type: Complete Binary Tree.

  • Root Node Content: The smallest element of the input.

  • Height: Approximately O(log n).

  • Update Method When Input Changes: The path from the updated leaf node to the root is updated.