Advanced Algorithms and Complexity

1. What is the Master Theorem used for?

• A. Sorting algorithms
• B. Analyzing the time complexity of divide-and-conquer recurrences ✓
• C. Graph algorithms
• D. Database indexing

💡 The Master Theorem provides a method to determine the time complexity of divide-and-conquer algorithms given their recurrence relation.

2. What is the time complexity of heap sort?

• A. O(n)
• B. O(n²)
• C. O(n log n) ✓
• D. O(log n)

💡 Heap sort builds a max-heap in O(n) then extracts elements in O(log n) each, giving O(n log n) overall.

3. What is the Floyd-Warshall algorithm used for?

• A. Minimum spanning tree
• B. Finding shortest paths between all pairs of vertices ✓
• C. Sorting
• D. Graph traversal

💡 Floyd-Warshall finds shortest paths between all pairs of vertices in a weighted graph, running in O(V³) time.

4. What is a "red-black tree"?

• A. A type of graph
• B. A self-balancing BST with color properties ensuring O(log n) operations ✓
• C. A type of heap
• D. A sorted linked list

💡 A red-black tree is a self-balancing binary search tree with color rules that guarantee O(log n) time for insert, delete, and search.

5. What is the difference between a tree and a graph?

• A. No difference
• B. Trees are directed; graphs are undirected
• C. A tree is an acyclic connected graph; a graph can have cycles ✓
• D. Graphs have more nodes

💡 A tree is a special type of graph that is connected and acyclic (no cycles). A graph can have cycles and disconnected components.

6. What is "memoization" vs "tabulation" in dynamic programming?

• A. They are the same
• B. Memoization is bottom-up; tabulation is top-down
• C. Memoization is top-down with caching; tabulation is bottom-up iterative ✓
• D. Tabulation uses recursion; memoization does not

💡 Memoization (top-down) uses recursion with caching. Tabulation (bottom-up) builds the solution iteratively from smaller subproblems.

7. What is a "minimum spanning tree"?

• A. The smallest tree in a forest
• B. A tree connecting all vertices with minimum total edge weight ✓
• C. A tree with minimum height
• D. A balanced binary tree

💡 An MST connects all vertices of a weighted graph with the minimum possible total edge weight, with no cycles.

8. What is the time complexity of accessing an element in a hash table in the worst case?

• A. O(1)
• B. O(log n)
• C. O(n log n)
• D. O(n) ✓

💡 In the worst case (all keys hash to the same bucket), hash table lookup degrades to O(n) linear search.

9. What is a "segment tree"?

• A. A type of linked list
• B. A tree used for range queries and updates on arrays ✓
• C. A self-balancing BST
• D. A type of heap

💡 A segment tree allows efficient range queries (sum, min, max) and point updates on arrays in O(log n) time.

10. What is the difference between Prim's and Kruskal's algorithm?

• A. No difference
• B. Both find minimum spanning trees but Prim's grows from a vertex; Kruskal's adds edges by weight ✓
• C. Prim's sorts edges; Kruskal's grows from a vertex
• D. Kruskal's uses BFS; Prim's uses DFS

💡 Both find MSTs. Prim's grows the tree from a starting vertex. Kruskal's sorts all edges and adds them if they don't form a cycle.

11. What is "topological sorting"?

• A. Sorting numbers in ascending order
• B. Ordering vertices of a DAG such that for every edge u→v, u comes before v ✓
• C. A type of binary search
• D. Sorting strings alphabetically

💡 Topological sort linearly orders vertices of a Directed Acyclic Graph (DAG) respecting edge directions — used in task scheduling.

12. What does NP-complete mean?

• A. A problem solvable in polynomial time
• B. A problem that cannot be solved
• C. A problem in NP to which all NP problems can be reduced in polynomial time ✓
• D. A non-polynomial algorithm

💡 NP-complete problems are the hardest in NP — if any one can be solved in polynomial time, all NP problems can be.

13. What is Dijkstra's algorithm used for?

• A. Sorting an array
• B. Finding the shortest path in a weighted graph ✓
• C. Searching a binary tree
• D. Hashing keys

💡 Dijkstra's algorithm finds the shortest path from a source node to all other nodes in a weighted graph with non-negative weights.

14. What is Bellman-Ford algorithm used for?

• A. Sorting
• B. Finding shortest paths with negative weight edges ✓
• C. String searching
• D. Graph coloring

💡 Bellman-Ford finds shortest paths from a source, and unlike Dijkstra, handles graphs with negative weight edges.

15. What does "P vs NP" mean in computer science?

• A. Parallel vs Non-Parallel computing
• B. Whether every problem whose solution can be verified quickly can also be solved quickly ✓
• C. Programming vs Nonprogramming
• D. Polynomial vs Non-polynomial space

💡 P vs NP asks whether every problem whose solution can be verified in polynomial time (NP) can also be solved in polynomial time (P).

16. What is Knuth-Morris-Pratt (KMP) algorithm used for?

• A. Graph shortest path
• B. Sorting strings
• C. Efficient string pattern matching in O(n+m) time ✓
• D. Hashing strings

💡 KMP finds occurrences of a pattern in a text in O(n+m) time by using a failure function to avoid redundant comparisons.

17. What is a "skip list"?

• A. A linked list with skipped nodes
• B. A probabilistic data structure with multiple layers of linked lists for fast search ✓
• C. A type of binary tree
• D. A sorted array

💡 A skip list uses multiple layers of sorted linked lists with express lanes, achieving O(log n) average search time.

18. What is the time complexity of merge sort?

• A. O(n)
• B. O(n²)
• C. O(n log n) ✓
• D. O(log n)

💡 Merge sort always divides the array in half and merges, giving O(n log n) in all cases (best, average, worst).

19. What is a "trie" data structure?

• A. A type of binary tree
• B. A balanced BST
• C. A tree used for storing strings with shared prefixes ✓
• D. A type of heap

💡 A trie (prefix tree) stores strings character by character, sharing common prefixes — efficient for autocomplete and dictionary lookups.

20. What is "amortized analysis" in algorithms?

• A. Worst-case analysis
• B. Analyzing average performance per operation over a sequence of operations ✓
• C. Best-case analysis
• D. Space complexity analysis

💡 Amortized analysis calculates the average time per operation over a sequence, smoothing out occasional expensive operations.