Announcements

Project 3 showcase next Sunday [May 11] 12-3 in the Wozniak Lounge (430 Soda).
● Sign-ups: https://forms.gle/UmAH8YkNBqm8YBa8A
● Pizza available for your mouth.
Lecture 40

Wrapping Things Up
CS61B, Spring 2025 @ UC Berkeley
Slide Credit: Josh Hug
2
 61B in 12 Minutes or Less
Your Future
AMA

61B in 12 Minutes Course Reflections

or Less
Lecture 40, CS61B, Spring 2025
Where We Started

Just 14 weeks ago:

What We’ve Learned about Programming Languages

● Object based programming: Organize around objects.

● Object oriented programming: Example: Programmer only needs to know List
API, doesn’t have to know that ArrayList secretly
○ Interface Inheritance. does array resizing.
○ Implementation inheritance.
● Dynamic vs. static typing.
● Generic Programming, e.g. ArrayList<Integer>, etc.
Example: Array is a
● The model of memory as boxes containing bits. sequence of boxes. An
● Bit representation of positive integers (hashing lecture). array variable is a box
● Java. containing address of
sequences of boxes.
● Some standard programming idioms/patterns:
○ Objects as function containers (e.g. Comparators, IntUnaryFunctions).
○ Default method specification in interfaces (Link).
○ Iterators.
Important Data Structures in Java

Important data structure interfaces:

● java.util.Collection (and its subtypes).
○ With a special emphasis on Map (and its subtypes).
● Our own Collections (e.g. Map61B, Deque): Didn’t actually extend Collection.

Concrete implementations of these abstract implementations:

● Examples: ArrayDeque implements Deque.
Mathematical Analysis of Data Structure/Algorithm Performance

● Asymptotic analysis.
● O(·), Ω(·), Θ(·), and tilde notation.
● Worst case vs. average case vs. best case.
○ Exemplar of usefulness of average case: Quicksort
● Determining the runtime of code through inspection (often requires deep
thought).
● Multiplicative resizing is much better than additive resizing.
○ Multiplicative resizing results in Θ(1) add runtime for ArrayLists.
○ Additive resizing results in Θ(N) add runtime for ArrayLists.
Some Examples of Implementations for ADTs

LinkedList
Chaining HT
List
Resizing Array
Heap
Set LinkedList
PQ Balanced Tree
Resizing Array
Map Ordered Linked List
Quick Find
BST (no balancing)
Quick Union
DisjointSets
Red Black
WeightedQuickUnionUF
B-Trees (2-3 / 2-3-4)
WQUPC
Adjacency Matrix
Trie
Graph Edge List
Heap
Adjacency Lists
Arrays vs. Linked Data Structures

Array-Based Data Structures:

● ArrayLists and ArrayDeque
● HashSets, HashMaps, MyHashMap: Arrays of ‘buckets’
● ArrayHeap (tree represented as an array)

Linked Data Structures

● Linked Lists
○ LinkedList, IntList, LinkedListDeque, SLList, DLList
● Trees: Hierarchical generalization of a linked list. Aim for bushiness.
○ TreeSet, TreeMap, BSTMap, Tries (trie links often stored as arrays)
● Graphs: Generalization of a tree (including many algorithms).

Tradeoffs of array-based vs. linked data structures.

Tractable Graph Problems and Algorithms
vertex
Topological Sort
ordering
Reachability DFS Traversal
vertex
Bipartiteness
Discussed markings
in section
Cycle Detection
BFS Traversal
Multiple Target shortest
Shortest Paths by # paths tree
of Edges
Prim’s
Minimum Spanning Minimum Spanning
Tree Tree
Kruskal’s
Multiple Target
shortest Dijkstra’s
Shortest Paths by
Total Edge Weight paths tree
DAGSPT
Single Target
Shortest Paths by shortest path A*
Total Edge Weight
Search-By-Key-Identity Data Structures:
2-3 Tree
Searches using compareTo()
Set
RedBlack Analogous to Comparison-Based

Map External Chains

Searches using hashCode() and equals()
Linear Probing Roughly Analogous to Integer Sorting

Trie / TST Searches by digit. Analogous to Radix Sorting

Comparison Based Sorting Algorithms: Ω(N log N) worst case Radix Sorting Algorithms: Θ(NW) worst case:
(require a sorting subroutine)
Selection If heapify first Heapsort

Merge
LSD
Partition Counting
MSD
Insertion If store in helper BST, eq. to
Small-Alphabet (Integer) Sorting Algorithms: Θ(N) worst case
Counting
The Practice of Programming

● Java syntax and idioms.

● Unit testing (and its more extreme form: Test-driven development).
● Mining the web (and LLMs?) for code.
● Debugging:
○ Identify the simplest case affected by the bug.
○ Hunt it down, giving it no place to hide.
○ With the right methodology, can find bugs even when finding bug through
manual code inspection is impossible.
● Tactical vs. Strategic Programming.
○ Avoid information leakage. Build deep modules. Minimize dependencies.
Minimize obscurity.
● Real tools: IntelliJ, git, Truth, command line.
● Data structure selection (and API Design)
○ Drive the performance and implementation of your entire program.
 61B in 12 Minutes or Less
Your Future
AMA
Course Reflections

Your Future
Lecture 40, CS61B, Spring 2025
Your Life

Two immediate questions:

● What classes should I take next semester?
● How should I prepare for the final?
Two long-term questions:
● What am I capable of achieving?
● What should I do with my life?
Class Poll (Your Answer)

How many students are happy with the grade they are on track to receive?
Class Poll (Your Answer)

What does a good grade in this class mean? How will a good grade in this class
affect you?
● TAing
● Grad School
● Happy
● Ego
● Not putting Fries in the bag (better career?)
● Gauging work ethic
● Knowledge
● Parents
● Preparation for future courses
Class Poll (My Answer)

What does a good grade in this class mean? How will a good grade in this class
affect you?
A grade in this course is not a measure of your worth/intelligence.
Several ways your grade could affect your future:
● Future job prospects/grad school?
○ While GPA is a factor, it's often not a very important one. Once you get
into industry, job experience matters much more than college GPA.
What does your grade mean?

I would argue that the most important thing your grade tells you is how hard your
next semester will be.

Most of the time, you don't truly master a concept until you're forced to use it to
solve something new. A lot of the concepts we've covered in the last half of the
course will only solidify when you start taking 61C, 170, or any other "next step"
class.

The grade you get in this course is my message to you saying how difficult I
predict it will be to develop that mastery in your next class.
What does your grade mean?

An A in this class is a signifier of mastery. If you take a sequel course, you will
likely do well even with other work on your plate. So you can take more/harder
courses.
A B in this class is a signifier of comprehension. If you take a sequel course, you
will likely do well if you dedicate sufficient time to the class.
A C in this class is a signifier of competence. If you take a sequel course, you will
likely need to devote more time than usual to do well. So try to avoid taking too
many courses at the same time
Anything below a C is a signifier that you will struggle in a sequel course. Going
directly to a sequel course will likely not be worthwhile. It may be good to retake
the course so you get more time to digest concepts.
● Like surfing: Once you're behind a wave, it's difficult to catch it
○ But if you're ahead of the wave, it pushes you forward
○ If you're behind the wave, it may be best to wait for the next wave
A Supporting Experiment for “Everyone Can Do Well”

In Sp16, Josh gave students the option to fail intentionally to retake the course.
● On average, students were 2.5 letter grades higher the second time, e.g.
someone in the middle of the B range got an A the second time.

My interpretation: Even if you're not on pace for the grade you want, you have
learned a lot from this course. That foundation will make it much easier to relearn
the course material at a later time.

Bottom line: You’re capable of achieving more than you might think possible.
The core "goal" of 61B

Ultimately, 61A's main goal was to teach you how to program:

● Go from problem description to a code solution
61B's goal is to teach you why you program:
● You have a problem, and you need to decide that code is the best way to solve
that problem
61C and 170 mainly focus on making the code you write efficient (170 by focusing
on the theoretical algorithm design, and 61C by focusing on the reality of how a
physical computer works).
After that, most classes in the CS major focus on one tiny facet of CS
(specialization)
At this point, you have everything you need to build whatever you want from code.
The best way to learn CS from now is to make something by yourself, and to play
with code.
How to have fun with CS: Competitive Programming and CTFs (Links in Speaker Notes)
How to have fun with CS: Programming Video Games
How to have fun with CS: Hackathons (https://www.calhacks.io/)
Your Life

Two long-term questions:

● What am I capable of achieving?
○ Almost anything given time and motivation
● What should I do with my life?
○ You will be in high demand by everyone.
○ Your skills will enable you to affect the world, possibly profoundly.

Technology will continually to radically reshape the way we live our lives.
Choices (Yup)

How you use your skills is up to you.

Choices (Yup)

How you use your skills is up to you.

Using Your Powers for Good

My request: Use your superpowers in a way that is a net positive for the lives of
your fellow humans.
● I’m not saying that working for big companies is evil or anything, or that you
have a moral obligation to work for relatively low wages for the public good
(though that’d be great, of course).
● …. but keep in mind that your work will profoundly affect the world.

(Wanna talk about this stuff more? Take CS195!)

 61B in 12 Minutes or Less
Your Future
AMA
Course Reflections

AMA
Lecture 40, CS61B, Spring 2025
Questions About Anything for Josh and Justin?

Studying:
● Do a little over a long period of time. Don’t rewatch videos. Solve problems
and have other people critique how you do them (work with people you trust).
● Cramming can work in limited circumstances, not good for us. Justin doesn’t
like you to hae looked at lectures if you can figure things out on your own –
simulate exam environment.
● Josh, most excited: LLMs and other generative techniques are massive
impact.
● Justin most excited: Love that you can experiment and build anything. Love
that access to electricity and computer, these are cheap, and can learn the
key techniques from the internet (including LLMs, which are great for learning
new things). Field that builds on itself.
● Justin, regret from college: No hackathon. COVID was no good.
● Josh, regret from college: None college was great.
● Justin: Math 191 was my first class (Putnam prep) and most fun. Learned
LaTeX, proof writing, best freshman year. Because average is 1/120, it was a
Questions About Anything for Josh and Justin?

Studying:
● Justin: Math 191 was my first class (Putnam prep) and most fun. Learned
LaTeX, proof writing, best freshman year. Because average is 1/120, it was a
guaranteed A. 4 units fit well. Joined Berkeley math tournament, introduced
him to skills and people that carried him forward. Scores: 13, slept through it
because of a 170 project, 37 (one point below top 5 at Berkeley), cancelled in
senior year.
 61B in 12 Minutes or Less
Your Future
AMA

Course Course Reflections

Reflections
Lecture 40, CS61B, Spring 2025
Feedback Request

We read all of your feedback, especially on the end of course evaluations.

● There is an official form from the university, and an internal survey for 61B
that we’ll send out ourselves.
61B Would Love to Have You Next Fall

● Teaching interns: Learn more, help others, get units.

● Watch out for an announcement on the Spring 2025 61B Ed.
Special Thanks to the Staff (who keep the wheels on the bus)

20 Hour/wk TAs: Vanessa Teo, Manke Luo, Daniel Wang, Erik Kizior

15/12/10 Hour TAs: Chenkun Sheng, Mihir Mirchandani, Anniyat Karymsak, Elaine Shu,
David Yang, Kanav Mittal, Stacey Lei, Elana Ho, Dylan Hamuy, Anirudh Sreerama, Aditya
Hariharan, Natalia Grondin, Tiffany Li, Stella Kaval, Anirudh Kotamraju, Ashley Kao

8 Hour/wk TAs: Ritika Joshi, Iris Zhou, Sahityasree Subramanian, Wilson Fung, Jeffrey
Yum, Elisa Kim, AJ DeMarinis, Alyssa Smith

Tutors: Diego Huezo, Julian Tuazon, Ryan Yang, Philip Ye, Ethan Tam, Fiona Chang,
Shrithan Sandadi, Terrianne Zhang, Lawrence Wu, Ridge Huang, Sophie Nazarian,
Marcus Koh, Dawn Schumacher, Andrew Schoenen, Amy Wang, Isabel Dong, Ayush
Gupta, Yinqi Yi, Rushil Saraf, Dennis Koh, Karen Meng, Jonathan Martin
Gasser-Brennan, Sarveshan Saravanan, Arjun Damerla
Closing Thoughts (Josh)

It is a terrifying and awesome responsibility to decide how you should spend

hundreds of your precious hours here at Berkeley.

I hope I’ve done a good job. I know it wasn’t perfect (and sadly never will be).
● (but I’ve got Ideas™)

… and thanks for all the kind words, feedback, and understanding when things are
not as good as they could be.
Closing Thoughts (Justin)

Don't worry about how others are doing, or focus on perfectly optimizing your
college experience. Chances are, the choices you make now will lead to a good
outcome. All you need to do is to be better than the person you were a year ago.

Personally, I teach because I believe that I am doing the most good for the world in
this position. Please, prove me right.