Algorithm Types
This strategy divides the problem into subproblems, solves them recursively, and merges the results.
Divide and Conquer
What is the time complexity of linear search?
O(n)
What algorithm would you use to find the shortest path in an unweighted graph?
Breadth-First Search
What does NP stand for in computational complexity?
Nondeterministic Polynomial time
Which sorting algorithm is best for nearly sorted data?
Insertion Sort
Give one example where the greedy method fails to produce an optimal solution.
0/1 Knapsack Problem
Why is merge sort preferred over quicksort for linked lists?
Because merge sort does not require random access, making it more efficient on linked lists.
Why does Dijkstra’s algorithm fail on graphs with negative weights?
It assumes once a node is visited, the shortest path to it is known — this fails with negative weights.
Define the difference between NP-complete and NP-hard problems.
NP-complete: in NP and as hard as any in NP; NP-hard: not necessarily in NP.
Why is merge sort considered stable while quicksort is not?
Merge sort preserves the relative order of equal elements, quicksort doesn't guarantee it.
Why is memoization preferred over plain recursion in dynamic programming?
Because it avoids redundant subproblem evaluations, improving time complexity.
Derive the recurrence relation for merge sort
T(n) = 2T(n/2) + O(n)
Explain the role of a priority queue in Dijkstra's algorithm.
It efficiently selects the next node with minimum distance.
Give a reduction from SAT to 3-SAT.
Split large clauses into 3-literal clauses by adding new variables (sketch acceptable).
Compare average vs. worst-case time complexity of quicksort.
Average: O(n log n), Worst: O(n²) if pivot is poorly chosen.
Describe a real-world scenario where backtracking is more efficient than brute-force.
Solving Sudoku or N-Queens, where constraints reduce the search space.
What does Big-O notation ignore and why? This is the best possible time complexity for comparison-based sorting algorithms.
It ignores constants and lower-order terms to focus on asymptotic growth. O(n log n)
In which scenario is Prim’s algorithm preferred over Kruskal’s for MST?
When the graph is dense and represented as an adjacency matrix.
Why is P ≠ NP still an unsolved problem?
Because no proof exists that P = NP or P ≠ NP — it's a millennium prize problem.
Write the recurrence for quicksort and solve using Master Theorem.
T(n) = T(k) + T(n-k-1) + O(n) → Average case: O(n log n)
Compare and contrast dynamic programming and greedy algorithms in terms of optimal substructure and decision making.
Both use optimal substructure, but greedy makes locally optimal decisions, while DP considers all possibilities and uses memoization to ensure a globally optimal solution. Backtracking
Given T(n) = T(n – 1) + O(1), derive the time complexity. This problem-solving strategy can sometimes reduce exponential complexity to polynomial.
It's a linear recurrence, so T(n) = O(n).
Prove that a tree with n vertices has exactly n-1 edges.
y induction: Base case holds; assume true for k, then for k+1 by adding a node and edge — still n-1.
Explain the significance of Cook’s theorem in complexity theory.
It showed that SAT is NP-complete, proving the existence of complete problems for NP.
How can radix sort achieve linear time complexity?
By sorting digits from LSB to MSB using a stable sort (like counting sort), total complexity: O(nk) where k is digit length.