Further Reading & Deep Dives

Week 6: Greedy Algorithms & MST

Textbooks & Papers

Online Resources

• Kruskal's Algorithm - Wikipedia - Visualizations and pseudocode
• Prim's Algorithm - Wikipedia - Detailed explanation with complexity analysis
• Princeton Algorithms Course - Robert Sedgewick - Video lectures on MST

Implementation Resources

• Union-Find data structure: Critical for Kruskal's. Practice path compression and union by rank.
• Priority queue implementation: Essential for Prim's algorithm with O(E log V) complexity.

Week 6: Network Flow

Foundational Papers

Advanced Topics

• Edmonds-Karp Algorithm: O(VE^2) implementation using BFS for augmenting paths
• Dinic's Algorithm: O(V^2 E) using level graphs and blocking flows
• Push-Relabel Algorithm: O(V^3) or O(V^2 sqrt(E)) with heuristics

Applications

• Bipartite matching (reduce to max flow)
• Project selection problems
• Airline scheduling and resource allocation
• Image segmentation in computer vision

Week 8: Linear Programming

Core References

Key Concepts

• Standard form and canonical form transformations
• Basis, basic feasible solutions, vertices of feasible region
• Pivot operations and entering/leaving variables
• Unbounded and infeasible cases detection
• Two-phase simplex method

Extensions

• Interior Point Methods (polynomial time, practical)
• Integer Linear Programming (NP-hard in general)
• Network simplex for specialized problems

Week 8: String Matching

Algorithms Overview

• Naive Algorithm: O(mn) - baseline comparison
• KMP (Knuth-Morris-Pratt): O(m + n) - avoid rescanning text
• Boyer-Moore: O(m + n), often faster in practice for large alphabets
• Rabin-Karp: O(m + n) average, uses hashing for pattern matching

Advanced Topics

Applications

• DNA sequence matching in bioinformatics
• Plagiarism detection
• Text search in editors (Ctrl+F)
• Network intrusion detection systems

Week 9: Data Compression

Compression Theory

Lossless Compression Techniques

• Statistical Methods: Huffman, Arithmetic coding - exploit symbol frequencies
• Dictionary Methods: LZ77, LZ78, LZSS - build dictionaries dynamically
• Hybrid: DEFLATE (ZIP) combines LZ77 + Huffman

Codec Standards

• ZIP/DEFLATE: LZ77 + Huffman, universal file compression
• GZIP: DEFLATE with headers, common in web
• BZIP2: Burrows-Wheeler + Huffman, better compression ratio
• LZMA: Advanced dictionary coder, used in 7-Zip

Lossy Compression

• JPEG: Discrete Cosine Transform + quantization + Huffman
• MPEG: Motion estimation + transform coding
• MP3: Psychoacoustic modeling + Huffman

Week 9: Huffman Coding Deep Dive

Optimality Proof

Huffman's algorithm produces optimal prefix code because:

1. Optimal substructure: subtrees are optimal for their subtask
2. Greedy choice: combining two smallest frequencies is locally optimal
3. Exchange argument: any other tree has worse cost

Variants & Extensions

• Canonical Huffman: Encode just code lengths, reconstruct tree decoder-side
• Adaptive Huffman: Update frequencies and tree as data streams
• n-ary Huffman: Generalize to n-ary trees (tradeoff: code length vs alphabet size)

Limitations

• Requires known frequency distribution or need two passes
• Symbol-by-symbol: doesn't exploit longer patterns (why LZ/LZMA better for some data)
• Overhead: need to transmit code table or tree structure

Week 10: Streaming Algorithms

Key Problem Classes

Sampling Techniques

• Uniform Sampling: Reservoir sampling for arbitrary stream
• Stratified Sampling: Sample proportionally from groups
• Weighted Sampling: A-Res algorithm for sampling by weight

Frequency Estimation

• Count-Min Sketch: O(1/epsilon * log n) space for approximate counts
• Frequent Items (Heavy Hitters): Find items with frequency > threshold
• Space-Saving Algorithm: Deterministic frequent items with guaranteed bounds

Advanced Topics

• Distinct element counting (HyperLogLog for cardinality)
• Quantile estimation
• Approximate median and percentiles

Week 10: Bloom Filters & Variants

Analysis

Variants

• Counting Bloom Filter: Replace bits with counters, allows deletion
• Scalable Bloom Filter: Add new filters dynamically as load increases
• Spectral Bloom Filter: Track approximate counts not just membership
• Cuckoo Filters: Better space efficiency, supports deletion

Real-World Use Cases

• Google Chrome: Check URLs against known malware sites
• Cassandra/HBase: Check if key exists before disk lookup
• Medium: Avoid recommending previously read articles
• Bitcoin: Bloom filters in SPV (Simplified Payment Verification)

Week 11: Randomized & Probabilistic Algorithms

Fundamental References

Classification

Type	Running Time	Correctness	Example
Las Vegas	Probabilistic	Always correct	Randomized Quicksort
Monte Carlo	Deterministic	Probably correct	Miller-Rabin primality test

Key Algorithms

Concentration Inequalities

• Markov Inequality: P(X >= a) <= E[X]/a - loose but model-free
• Chebyshev Inequality: Bounds deviation from mean using variance
• Chernoff Bounds: Exponential tails for independent events, very tight
• Hoeffding Inequality: Works for bounded random variables

Advanced Topics

• Derandomization: convert randomized algorithms to deterministic
• Probabilistic method: prove existence without explicit construction
• Hashing: universal hashing with collision probability bounds

Cross-Week Connections & Synthesis

Greedy vs Dynamic Programming

• Both have optimal substructure
• Greedy: one decision path, optimal subproblem choice is forced
• DP: explore multiple subproblem solutions, combine optimally
• Greedy faster when applicable (O(n log n) vs O(n^2) or worse for DP)

Complexity Throughout the Course

• Polynomial: MST (O(E log E)), LP Simplex (average), KMP (O(m+n))
• Exponential: Exact TSP, Integer LP (NP-hard in general)
• Approximate: Streaming sketches (approximate with high probability)
• Probabilistic: Randomized quicksort (expected polynomial, always correct)

Data Structure Choices

• Greedy algorithms: heaps for priority queue (MST, Huffman)
• Network flow: adjacency lists for graphs, queues for BFS
• Streaming: fixed-size arrays/counters, hash tables for Count-Min
• Compression: trees (Huffman), tries (dictionary methods)

Exam Preparation Tips

Time Management

• Know the high-level ideas before diving into proofs
• Practice algorithm trace-throughs by hand (graph examples)
• Understand complexity analysis deeply, not just memorized formulas

Common Question Patterns

• "Show the algorithm runs in O(...) time" - use amortized analysis or properties of data structures
• "Prove this is optimal" - exchange argument, greedy proof structure
• "Design an algorithm for..." - recognize problem type, apply known technique
• "What happens if..." - trace through edge cases, understand when properties break

Study Schedule

• Review: Start with easy problems (sorting review from Week 4)
• Core: Focus on MST, Greedy proofs, LP formulations, Huffman optimality
• Extensions: Streaming approximations, randomized analysis
• Mock: Timed practice exams, identify weak areas

Online References & Tools

Visualization Tools

• Data Structure Visualizations - USFCA
• Algorithm Visualizer
• HackerEarth Algorithm Problems

Implementation References

• TheAlgorithms GitHub - Multiple language implementations
• CP-Algorithms - Competitive programming algorithms

Academic Resources

• arXiv.org - Preprints of research papers
• Google Scholar - Search academic papers

Related Courses (Same Level)

• MIT 6.046J Design of Computer Algorithms
• Stanford CS161 Algorithms
• Carnegie Mellon 15-451 Algorithm Design