CS 61B Resources

By Allen Guo

Last Updated: 04/25/2018

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.
A quick guide to method selection: link.
How to use comments effectively: link.

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 single most confusing topic in asymptotics is the difference between best-case/worst-case and big-O/Theta/Omega.
- Big-O/Theta/Omega describes the runtime of an algorithm in one or multiple cases. Best-case/worst-case describes a particular input case for an algorithm.
- Here's an example: "The worst-case runtime for quicksort is Theta(n^2)."
  - Notice how "worst-case" describes the input. For example, for quicksort where the first element is chosen as the pivot, the worst-case input is an already-sorted list.
- What's confusing is that I could also say, "The runtime for quicksort is O(n^2)."
  - This is a more general statement: I'm implying that this statement is true for all cases/inputs.
  - Notice that this does not imply that the worst-case runtime of quicksort is Theta(n^2) (why not?).
You can't perform asymptotic analysis just by blindly following rules like "multiply for nested loops".
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).

Some problems:
- 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.)

Students tend to confuse heaps and BSTs. Do you know what the differences are?
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.

DP isn't a specific algorithm, but rather a general problem-solving technique.
- So learning DP is less like learning Dijkstra's and more like learning recursion.
Don't worry if the definition of DP is confusing at first.
- Do practice problems. Then think about what those problems had in common. Then go back to the definition.
Intro tutorial: link.
Another intro: link.
- Try to solve the problem yourself before looking at the answer.

"The Magician's Code" from The Codeless Code.
"Advice for Computer Science College Students" from Joel Spolsky, blogger extraordinaire and cofounder of Stack Overflow (among other things).
"The Curse of the Gifted" by Eric S. Raymond, in an email to Linus Torvalds, creator of Linux and Git.
"How To Be Effective" by Philip J. Guo (no relation), professor at UCSD and creator of Python Tutor.
"Productivity" by Sam Altman, president of YC. Also read this.
John DeNero talks about freedom, power, and self-worth: link (requires UC Berkeley sign-in).
Some random guy asking a question (in 1996) about his Java web crawler, which would eventually become kind of a big deal. Don't be afraid to ask questions!

If you have any interest at all in working in software development in the future, I highly recommend you apply for internships this cycle, even if you don't feel ready.
- At the very least, you'll get a feel for what the process is like and what employers are looking for.
"A Brief Guide to Tech Internships" by Alexey Komissarouk.
- Except don't wait until winter break to start applying. Lots of positions at popular companies fill up by the end of fall semester.
What your resume should look like: link.
For interview practice, I (like everyone else) recommend Cracking the Coding Interview.
- Find a buddy, reserve a library room with a whiteboard, and take turns interviewing each other.
- Study the problem-solving flowchart from the book: link.
Tip: Keep a list of interesting technical questions that you've encountered, including the solutions.
- Review the list often and add to it after every practice session.
- Before every real interview, go through the entire list and make sure you know everything on it.
Coding interview tips from Interview Cake: link.
A list of coding questions by Max Noy: link.
An even bigger list by Program Creek: link.
A still bigger list by Vivek Srivastava: link.

CS 188 logo

CS draft schedule (i.e., who's teaching what): link.
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.

Don't hesitate to email me (allenguo@berkeley.edu).