A comprehensive collection of algorithm implementations from Stanford CS161
Mac Huang - Algorithm implementations and educational materials for Stanford CS161 course.
- Introduction
- Data Structures
- Graph Algorithms
- Dynamic Programming
- Sorting Algorithms
- Hash Tables
- Greedy Algorithms
- Getting Started
- Contributing
This repository contains implementations of fundamental algorithms and data structures covered in Stanford's CS161 course. Each implementation includes both complete code and skeleton templates for learning purposes.
- π Comprehensive Coverage - Covers major topics in algorithms and data structures
- π― Educational Focus - Includes skeleton files for practice
- π» Multiple Languages - Implementations in C and Python
- π Learning Resources - Links to online tutorials and visualizations
| File | Description | Learning Resources |
|---|---|---|
avl.c |
AVL Tree implementation | BS Tree Viz β’ VisuAlgo β’ GeeksforGeeks |
optimized_avl.c |
Optimized AVL Tree | CS161 Lecture Notes |
23trees.c |
2-3 Tree implementation | B+ Tree Viz β’ 2-3 Tree Visualization |
splay.c |
Splay Tree implementation | Splay Tree Visualization |
bst_insert.c |
Binary Search Tree insertion | BS Tree Viz β’ BST Visualization |
decision_trees.py |
Decision Trees implementation | Visual Introduction |
Key Concepts:
- Self-balancing trees
- Tree rotations
- Search, insertion, deletion operations
- Time complexity: O(log n) for balanced trees
| File | Description | Learning Resources |
|---|---|---|
unionfind.c |
Union-Find (Disjoint Set) | VisuAlgo - UFDS β’ Princeton Slides |
Key Concepts:
- Path compression
- Union by rank
- Applications in Kruskal's algorithm
| File | Description | Learning Resources |
|---|---|---|
bfs_dfs_topo.c |
BFS, DFS, and Topological Sort | VisuAlgo - Graph Traversal β’ Topological Sort |
Key Concepts:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Topological ordering of DAGs
| File | Description | Learning Resources |
|---|---|---|
shortest_paths.c |
Dijkstra's and Bellman-Ford | Dijkstra Visualization β’ Bellman-Ford |
Key Concepts:
- Single-source shortest paths
- Negative weight edges handling
- Time complexity analysis
| File | Description | Learning Resources |
|---|---|---|
min_span_tree.c |
Kruskal's and Prim's algorithms | MST Visualization β’ Princeton MST |
Key Concepts:
- Greedy approach
- Edge selection strategies
- Forest connectivity
| File | Description | Learning Resources |
|---|---|---|
max_flow.c |
Maximum Flow algorithms | Max Flow Visualization β’ MIT OCW |
Key Concepts:
- Ford-Fulkerson method
- Residual graphs
- Min-cut max-flow theorem
| File | Description | Learning Resources |
|---|---|---|
fib.c |
Fibonacci with memoization | DP Introduction |
knapsack.c |
0/1 Knapsack problem | Knapsack Visualization |
lcs.c |
Longest Common Subsequence | LCS Visualization |
rod_cutting.c |
Rod Cutting problem | MIT OCW - DP |
Key Concepts:
- Optimal substructure
- Overlapping subproblems
- Memoization vs Tabulation
- State transition equations
| File | Description | Learning Resources |
|---|---|---|
sorting.c |
Various sorting algorithms | Sorting Viz β’ Toptal Viz β’ VisuAlgo |
rhs.c |
Radix/Heap sort implementations | Radix Sort β’ Heap Sort |
Key Concepts:
- Comparison-based sorting
- Linear-time sorting
- In-place vs stable sorting
- Time and space complexity
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(nΒ²) | O(log n) | No |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes |
| File | Description | Learning Resources |
|---|---|---|
linear_probing.c |
Linear probing hash table | Hashing Viz β’ Hash Table Visualization |
separate_chaining.c |
Separate chaining hash table | Hashing Viz β’ Chaining Visualization |
hash_check.c |
Hash function testing | Hashing Viz β’ Hash Functions |
Key Concepts:
- Collision resolution strategies
- Load factor analysis
- Hash function design
- Amortized analysis
| File | Description | Learning Resources |
|---|---|---|
activity_selection.c |
Activity Selection problem | Greedy Algorithms β’ MIT OCW |
Key Concepts:
- Greedy choice property
- Proof of correctness
- Exchange argument
- C Compiler (GCC or Clang)
- Python 3.x for Python implementations
- Make (optional) for building
For C files:
# Compile a single file
gcc -o program_name source_file.c
# Example
gcc -o avl avl.c
./avl
# With optimization
gcc -O2 -o program_name source_file.cFor Python files:
python filename.py
# Example
python decision_trees.pyThe skeleton/ directory contains template files for practice:
- Copy the skeleton file
- Implement the missing functions
- Compare with the complete implementation
# Example
cp skeleton/avl_skeleton.c my_avl.c
# Edit my_avl.c to complete the implementation
gcc -o my_avl my_avl.c
./my_avlalgorithms/
βββ README.md # This file
βββ README_zh.md # Chinese version
βββ data_structures/ # Data structure implementations
β βββ trees/ # Tree structures
β βββ hash_tables/ # Hash tables
β βββ union_find/ # Union-Find
βββ graph_algorithms/ # Graph algorithms
β βββ traversal/ # BFS, DFS, Topological sort
β βββ shortest_paths/ # Shortest path algorithms
β βββ mst/ # Minimum spanning tree
β βββ flow/ # Network flow
βββ dynamic_programming/ # DP problems
βββ sorting/ # Sorting algorithms
βββ greedy/ # Greedy algorithms
βββ skeleton/ # Template files for practice
- Introduction to Algorithms (CLRS)
- Algorithm Design by Kleinberg & Tardos
- The Algorithm Design Manual by Skiena
Contributions are welcome! Please feel free to submit pull requests with:
- Bug fixes
- New algorithm implementations
- Documentation improvements
- Test cases
This project is for educational purposes. Please refer to Stanford CS161 course policies for usage guidelines.
- Stanford University CS161 course instructors
- Matthew Sotoudeh for CS161 reference materials (https://masot.net/)
For questions or suggestions about this repository, please open an issue on GitHub.