Algorithms Case Studies & Practical Application 5 ā Questions and Answers
Question 1: A compiler performs register allocation ā assigning variables to a limited number of CPU registers. This problem is equivalent to which graph algorithm problem?
- Minimum spanning tree
- Graph coloring with k colors (Correct answer)
- Maximum flow
- Topological sort
Correct answer: Graph coloring with k colors
Each variable is a node; edges connect variables that are live at the same time; coloring with k colors assigns them to k registers without conflict.
Question 2: An image compression algorithm encodes pixel values so common values use fewer bits and rare values use more bits. This is an application of:
- Quicksort
- Huffman coding (Correct answer)
- Floyd-Warshall
- Linear probing
Correct answer: Huffman coding
Huffman coding builds a greedy prefix-free binary tree that assigns shorter codes to more frequent symbols, minimizing average code length.
Question 3: A logistics company solves a 'vehicle routing problem' where multiple trucks deliver to many locations. The real-world approach typically uses:
- Exact brute-force enumeration
- Heuristics and metaheuristics (e.g., simulated annealing, genetic algorithms) (Correct answer)
- Bubble sort on distances
- Single-source BFS from depot
Correct answer: Heuristics and metaheuristics (e.g., simulated annealing, genetic algorithms)
VRP is NP-hard; practical solutions rely on metaheuristics that find near-optimal routes in acceptable time for large instances.
Question 4: A peer-to-peer file-sharing network uses a distributed hash table (DHT) to locate which peer holds a file. The average lookup cost in a Chord DHT of n nodes is:
- O(n)
- O(log n) (Correct answer)
- O(nĀ²)
- O(1)
Correct answer: O(log n)
Chord uses a finger table so each lookup hop halves the remaining search space, achieving O(log n) hops to locate any key.
Question 5: A machine learning pipeline needs to split a dataset into training and test sets while ensuring the class distribution is preserved. The correct technique is:
- Random permutation ignoring class labels
- Stratified sampling (Correct answer)
- Merge sort by label then split
- Reservoir sampling
Correct answer: Stratified sampling
Stratified sampling partitions by class first and samples proportionally from each partition, preserving the original class distribution.
Question 6: A web crawler must visit billions of URLs without revisiting any. Which data structure most efficiently tracks visited URLs with minimal memory?
- Array of all visited URLs
- Bloom filter (Correct answer)
- Balanced BST of URLs
- Max-heap of URL hashes
Correct answer: Bloom filter
A Bloom filter uses multiple hash functions and a compact bit array to answer membership queries in O(1) with minimal memory, accepting a small false-positive rate.
Question 7: A stock trading platform needs to match buy and sell orders (order book). Buy orders should match the highest bid first; sell orders should match the lowest ask first. The appropriate data structures are:
- Two queues (FIFO for buys, FIFO for sells)
- Max-heap for buy orders, min-heap for sell orders (Correct answer)
- Two sorted linked lists with O(n) lookup
- Hash maps keyed by price
Correct answer: Max-heap for buy orders, min-heap for sell orders
A max-heap gives O(log n) access to the highest buy bid, and a min-heap gives O(log n) access to the lowest sell ask, enabling efficient order matching.
Algorithms Case Studies & Practical Application 5
A compiler performs register allocation ā assigning variables to a limited number of CPU registers.
This problem is equivalent to which graph algorithm problem?