In fall quarter, we are piloting a new CS106M as an enrichment companion course for CS106B students who are up for exploring additional topics and deepening their study of the course material in a small discussion setting.
CS106M is open to students who are co-registered for CS106B. Enrollment is limited to 30 students.
This one-unit, CR/NC course will be run as a seminar. We meet weekly on Thursday afternoon 2:30-3:50 PM Pacific time. Our meetings will mostly consist of group discussions and collaborative coding activities. There may be some light prep work (e.g. short readings or videos to preview before discussion) or follow-up exercises to help deepen your understanding after the discussion.
Students must attend the weekly sessions and participate in discussions and activities to receive credit. Note that participating in the live meetings is required; we are not able to support students who have schedule conflicts or incompatibilities.
CS106B "Programming Abstractions" is the study and application of powerfulu data structures and algorithms to computational problem solving. CS106M will follow along with the CS106B topic progression and dig into supplemental material that aligns with those topics.
For the inaugural offering of CS106M I proposed the thematic focus of Algorithms, those inner recipes that guide the systems powering our modern world. Here are some algorithmic techniques that build on the CS106B material that we could look into:
- Search engines, Google Page Rank
- Binary search, divide-and-conquer
- Hashing, checksums, fingerprints
- Error correction, parity, hamming/Gray codes, erasure codes
- Data compression, run-length encoding, Burroughs-Wheeler, LZW
- Pattern recognition, nearest neighbors
- Encryption, public key cryptography
- Regular expressions, string matching, Boyer-Moore, Knuth-Morris-Pratt
- Simulation, Monte Carlo, Markov chains
- Sorting (any and all kinds)
- Relational databases, queries, transaction processing
- Recursion (tail call elimination, memoization, dynamic programming)
- Fast Fourier transform
- Generating and solving mazes
- Newton's method for finding root
- A* search
- Bitwise tricks
- Knuth's Dancing Links
- Skip lists
- Balanced trees (AVL, red-black, splay)
- Tries and dawgs
- Suffix arrays and suffix trees
- Graph algorithms (shortest path, minimum spanning tree)
- John Carmack's fast inverse square root
Here are some other topics that are less algorithmic, but would made good discussion fodder around code and computer science:
- Code reading, code reviews, best practices
- Efficiency, profilers, performance tuning
- Ethics of algorithms, hidden bias, privacy
- Open-source software, community ethos, Cathedral and Bazaar
My plans are flexible to allow tailoring topics to fit the interests of the cohort. Your input on choosing topics is welcomed! Any topic that connects to CS106B is fair game. Be sure to come to the first week's meeting so you can weigh in with your input.