Algorithms Case Studies & Practical Application 2 — Questions and Answers
Question 1: A GPS navigation app must find the shortest path between two cities on a weighted road network. Which algorithm is the most practical choice?
- Bellman-Ford
- Dijkstra's algorithm (Correct answer)
- BFS on unweighted graph
- Floyd-Warshall
Correct answer: Dijkstra's algorithm
Dijkstra's algorithm efficiently finds shortest paths in graphs with non-negative edge weights, making it the standard choice for road networks.
Question 2: An e-commerce platform needs to recommend products by finding items most similar to what a user viewed, using cosine similarity across millions of items. What algorithmic approach reduces lookup time?
- Linear scan of all items
- Locality-Sensitive Hashing (LSH) (Correct answer)
- Bubble sort followed by binary search
- DFS traversal of item graph
Correct answer: Locality-Sensitive Hashing (LSH)
LSH approximates nearest-neighbor search in high-dimensional spaces, dramatically reducing the number of comparisons needed.
Question 3: A hospital scheduling system assigns surgeries to operating rooms to minimize idle time. This is an instance of which classical problem?
- Traveling Salesman Problem
- Job Scheduling / Interval Scheduling (Correct answer)
- Knapsack Problem
- Graph Coloring
Correct answer: Job Scheduling / Interval Scheduling
Minimizing idle time in room assignments is a classic interval scheduling or job-shop scheduling problem.
Question 4: A compiler needs to detect circular dependencies among modules. Which algorithm is best suited for this?
- Prim's algorithm
- Topological sort with cycle detection (DFS) (Correct answer)
- Kruskal's algorithm
- Dijkstra's algorithm
Correct answer: Topological sort with cycle detection (DFS)
DFS-based topological sort detects back edges that indicate cycles, making it ideal for finding circular dependencies in a directed graph.
Question 5: A social network wants to find communities (clusters of highly connected users). Which algorithmic technique is commonly applied?
- Merge sort
- Dijkstra's shortest path
- Community detection via modularity optimization or Louvain algorithm (Correct answer)
- Binary search on adjacency list
Correct answer: Community detection via modularity optimization or Louvain algorithm
Community detection algorithms like Louvain partition graphs into clusters by maximizing modularity, capturing densely connected groups.
Question 6: A text editor implements undo/redo functionality. Which data structure and algorithm design underpins this feature?
- Hash map with collision chaining
- Two stacks — one for undo, one for redo (Correct answer)
- Min-heap priority queue
- Balanced BST ordered by timestamp
Correct answer: Two stacks — one for undo, one for redo
Undo/redo is classically implemented with two stacks: actions are popped from the undo stack and pushed onto the redo stack.
Question 7: A financial system must process millions of transactions and detect duplicates in real time with minimal memory. Which probabilistic data structure is appropriate?
- AVL tree
- Bloom filter (Correct answer)
- Segment tree
- Adjacency matrix
Correct answer: Bloom filter
A Bloom filter uses bit arrays and hash functions to test membership with very low memory, accepting a small false-positive rate but zero false negatives.
Algorithms Case Studies & Practical Application 2
A GPS navigation app must find the shortest path between two cities on a weighted road network.
Which algorithm is the most practical choice?