CS 61B Resources
By Allen Guo
Last Updated: 03/20/2017
Discussion attendance form: link.
- Email: [email protected]
- Office hours: Wednesdays 12-2pm @ 109 Morgan
- Anonymous feedback form: link.
- What I look like: link (1.2 MB).
- Pre-section playlist: link.
- CS 61B course website: link.
- Exams from past semesters: link.
- Algorithms textbook site: link.
- Java syntax practice problems: link.
- OpenJDK source, i.e., how Java built-in classes are implemented: link.
- For example, here's how Java's real HashMap is implemented: link.
- "Java is Pass-by-Value, Dammit!" by Scott Stanchfield.
- GitHub's Git tutorial: link.
- Git is the name of the version control software. It's free and open source. GitHub is a company that hosts Git repositories (repos). You can use it as a central Git server for your projects.
- How to fix common Git problems: link.
- Make your shell Git-friendly with autocompletion and prompt support.
- I have custom Bash aliases for Git commands, which you can see in the "Git" section here: link.
- "A Hacker's Guide to Git" by Joseph Wynn.
- The #1 confusing topic in asymptotics is best-case/worst-case and big-O/big-Theta.
- Common sums:
- Sum of numbers: 1 + 2 + 3 + 4 + ... + n = Theta(n^2).
- Sum of squares: 1 + 4 + 9 + 16 + ... + n^2 = Theta(n^3).
- Geometric sum: 1 + 2 + 4 + 8 + ... + n = Theta(n).
- Uncommon sums:
- Sum of logs: log(1) + log(2) + log(3) + log(4) + ... + log(n) = log(n!) = Theta(n log n).
- Sum of subarray lengths: (n)(1) + (n-1)(2) + ... + (2)(n-1) + (1)(n) = Theta(n^3).
- Write a method that, given a binary tree of integers, returns if the tree is a valid BST. (Solution: link.)
- Write a method that, given a BST and two nodes in that BST, returns the lowest common ancestor of those two nodes, i.e., the common ancestor of the nodes farthest from the root. (Solution: link.)
2-3 Trees (and LLRB Trees)
- Diagram with examples of insertion: link.
- Visualizer: link (use "Max. Degree = 3" for 2-3 tree).
- Visualizer: link.
- Proof that bottom-up heapify takes linear time: link (see the "BuildHeap Analysis" section).
- A-star search walkthroughs: link.
- CS 188 exam prep worksheet: link. Treat "Uniform Cost Search" as a synonym for Dijkstra's algorithm. Ignore problems about "Greedy Search". Solutions are here.
Dynamic Programming (DP)
- Intro tutorial: link. Focus on the first two sections—the knapsack problem is beyond the scope of this course. (If you're interested, take CS 170!)
- Another intro: link. Try to solve the problem yourself before looking at the answer.
Inspiration and Wisdom
Internships and Interviews
- General internships FAQ from r/cscareerquestions: link.
- For interview practice, I (like everyone else) recommend Cracking the Coding Interview.
- Tip: Keep a list of interesting technical questions that you've encountered, including the solutions.
- Review this list often. Add to it after every practice session.
- Before every real interview, go through the entire list and make sure you know everything on it.
- "Hacking the Coding Interview" by Philip Youssef.
- "A Brief Guide to Tech Internships" by Alexey Komissarouk.
- Coding interview tips from Interview Cake: link.
- A list of coding questions by Max Noy: link.
- An even bigger list by Program Creek: link.
What Courses Do I Take Next?
- Crowdsourced advice from the CS Facebook group: link.
- HKN's directed graph of EE/CS courses: link.
- Course advice for aspiring data scientists, by Khoa Tran: link.
- If you can't make up your mind, I recommend CS 61C plus either CS 170 (harder) or CS 188 (easier).
- This should help you identify your interests while preparing you for interviews and/or research.