Algorithms Case Studies & Practical Application 5

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?

Accepted Answer

Graph coloring with k colors

Answer

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:

Accepted Answer

Huffman coding

Answer

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:

Accepted Answer

Heuristics and metaheuristics (e.g., simulated annealing, genetic algorithms)

Answer

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:

Accepted Answer

O(log n)

Answer

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:

Accepted Answer

Stratified sampling

Answer

Stratified sampling partitions by class first and samples proportionally from each partition, preserving the original class distribution.

Algorithms Practice Test

Algorithms Practice Test

Algorithms Case Studies & Practical Application 5