Background
To wrap up our study of basic data structures and algorithms this semester, you will each complete a final project for the course. This project has you focus on a specific problem where the right choice of algorithms / data structures helps us solve it efficiently. I have provided you a list of potential topics, information about what algorithms / data structures they use, and their relative difficulty.
Build the Bucket Tool from MS Paint
- Difficulty: Easy / Average
- Data Structures: Multidimensional Arrays, Queues
- Algorithms: Breadth-First Search, Depth-First Search, Flood Fill, Seed Fill
- Supporting Concepts: Matrices, Nearest Neighbors
- Resources:
Implement a First Generation Spell Checker
- Difficulty: Average
- Data Structures: Arrays, Graphs, Multidimensional Arrays
- Algorithms: Levenshtein Distance
- Supporting Concepts: Dynamic Programming
- Resources:
Construct a Least Recently Used (LRU) Cache
- Difficulty: Average
- Data Structures: Doubly Linked Lists, Hashmaps
- Algorithms: Cache Insertion, Retrieval, Replacement, etc.
- Supporting Concepts: Caching, Cache Hits, Cache Misses, Cache Eviction
- Resources:
Design Your Own Cryptocurrency
- Difficulty: Average / Hard (Nothing Here is Particularly Difficult, But There Are a Lot of New Concepts to Learn)
- Data Structures: Linked Lists, Blockchains
- Algorithms: Proof of Work, Consensus, Hashing Algorithms
- Supporting Concepts: Public Key Cryptography
- Resources:
Build Your Own Neural Network
- Difficulty: Average / Hard (The Graph Data Structure is Not That Bad, But the Training Algorithm Uses Multivariable Calculus)
- Data Structures: Graphs
- Algorithms: Backpropagation
- Supporting Concepts: Artificial Intelligence, Machine Learning, Neural Networks
- Resources:
Explore How Computers Know Where to Send Data on the Internet
- Difficulty: Average / Hard (Nothing Fundamentally New Here, But it is an Advanced Usage of Dynamic Programming)
- Data Structures: Graphs
- Algorithms: Djikstra’s Shortest Path Algorithm
- Supporting Concepts: Static Routing, Dynamic Routing, Dynamic Programming
- Resources:
Simulate Billions of Interacting Particles in a Galaxy
- Difficulty: Hard (You Need to Learn a New Data Structure and How it Applies to the Field of Physics)
- Data Structures: Octrees, Quadtrees
- Algorithms: Barnes-Hut Algorithm
- Supporting Concepts: Astrophysics, Particle Simulations, Visualization
- Resources:
Prove That You Solved a Puzzle Without Giving Away Your Solution
- Difficulty: Hard (No One Topic is Particularly Difficult Here, But You Combine Lots of Unique Concepts Together)
- Data Structures: Graphs
- Algorithms: Graph Coloring
- Supporting Concepts: Cryptography, Zero-Knowledge Proofs, Commitment Schemes, Reduction Problems
- Resources:
Explore the Fast Fourier Transform - “The Most Important Algorithm from the 20th Century”
- Difficulty: Challenging (This will Require Some Advanced Mathematics)
- Data Structures: Arrays. That’s right. Arrays are the final boss. Didn’t see that coming, did you?
- Algorithms: Cooley–Tukey Algorithm
- Supporting Concepts: Complex Analysis, Discrete Fourier Transform, Divide and Conquer Algorithms, Linear Algebra
- Resources: