Announcements

Your job from now until the final: Study a little each day.

• Final exam is comprehensive.
• Struggling students: Work through factual / conceptual / procedural questions from the textbook (e.g. https://cs61b-2.gitbook.io/cs61b-textbook/14.-disjoint-sets/14.6-exercises).
• Work with other people!
• Argue and discuss!�

Bonus lecture now requires 2 goodies and not 4.

• Form for the “Crab Claw” is now in the project 4 spec.
• Make a video demo-ing your project. You don’t have to have complete all the ambition points.
• (If you get all 4 then yeah, I’ll do you something special)�

Wrapping Things Up

2

Lecture 40

CS61B, Spring 2023 @ UC Berkeley

Josh Hug and Justin Yokota

61B in 12 Minutes or Less

Lecture 40, CS61B, Spring 2023

61B in 12 Minutes or Less

Your Future

AMA

Course Reflections

Where We Started

Just 14 weeks ago:�

What We’ve Learned about Programming Languages

• Object based programming: Organize around objects.
• Object oriented programming:
• Interface Inheritance.
• Implementation inheritance.
• Dynamic vs. static typing.
• Generic Programming, e.g. ArrayList<Integer>, etc.
• The model of memory as boxes containing bits.
• Bit representation of positive integers.
• Java.
• Some standard programming idioms/patterns:
• Objects as function containers (e.g. Comparators, IntUnaryFunctions).
• Default method specification in interfaces (Link).
• Iterators.

Example: Programmer only needs to know List API, doesn’t have to know that ArrayList secretly does array resizing.

Example: Array is a sequence of boxes. An array variable is a box containing address of sequences of boxes.

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.

PQ

List

Set

Map

DisjointSets

Chaining HT

LinkedList

Resizing Array

Heap

Red Black

BST (no balancing)

B-Trees (2-3 / 2-3-4)

Heap

Ordered Linked List

Balanced Tree

Resizing Array

LinkedList

Quick Find

Quick Union

WeightedQuickUnionUF

WQUPC

Some Examples of Implementations for ADTs

Trie

Graph

Adjacency Matrix

Edge List

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

Reachability

Topological Sort

Multiple Target

Shortest Paths by Total Edge Weight

Single Target Shortest Paths by Total Edge Weight

Multiple Target

Shortest Paths by # of Edges

BFS Traversal

DFS Traversal

Dijkstra’s

A*

Bipartiteness

Cycle Detection

Minimum Spanning Tree

Minimum Spanning Tree

shortest path

shortest paths tree

Prim’s

Kruskal’s

shortest paths tree

vertex markings

vertex ordering

Discussed in section

DAGSPT

Search-By-Key-Identity Data Structures:

Set

2-3 Tree

RedBlack

External Chains

Linear Probing

Map

Searches using compareTo()

Analogous to Comparison-Based

Searches using hashCode() and equals()

Roughly Analogous to Integer Sorting

Comparison Based Sorting Algorithms: Ω(N log N) worst case

Selection

Insertion

Merge

Partition

Counting

LSD

MSD

Counting

Radix Sorting Algorithms: Θ(NW) worst case:

Small-Alphabet (Integer) Sorting Algorithms: Θ(N) worst case

(require a sorting subroutine)

If store in helper BST, eq. to

If heapify first

Heapsort

Trie / TST

Searches by digit. Analogous to Radix Sorting

Fun/Weird Topics (This Week)

Compression:

• Huffman Coding, and selection of data structures for Huffman Coding.
• Other approaches: LZW and Run Length Encoding (extra slides).

​

Compression, Complexity, and P=NP:

• Optimal compression is impossible.
• Bounded space/time compression is possible if P=NP.
• Allows you to find arbitrarily short programs that produce a given output in a given runtime.
• Compression of a stream of bits might provide a useful model of that stream of bits (e.g. hugPlant.bmp -> hugPlant.java).
• If P = NP, we could also solve all kinds of other interesting problems.

The Practice of Programming

• Java syntax and idioms.
• Unit testing (and its more extreme form: Test-driven development).
• Mining the web 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.

​

Your Future

Lecture 40, CS61B, Spring 2023

61B in 12 Minutes or Less

Your Future

AMA

Course Reflections

Your Life

Two interesting questions:

• What am I capable of achieving?
• What should I do with my life?

Some Josh Hug History

Slacker/punk rock attitude result

Midterm 1

Poll: yellkey.com/unit

To what degree do you believe the following statement: Nearly anybody enrolled at Berkeley could achieve an A in CS61B.

• Assume they can spend the entire summer preparing beforehand, hire a tutor during the semester, etc.

​

1. Strongly disagree
2. Disagree
3. Neutral
4. Agree
5. Strongly agree

Bloom’s Two Sigma Problem

Bloom’s Two Sigma Problem: In one experiment, student randomly picked for 1-on-1 teaching performed similarly to the top 2% of a simultaneous lecture course.

Bloom’s Two Sigma Problem

Bloom’s Two Sigma Problem: In one experiment, student randomly picked for 1-on-1 teaching performed similarly to the top 2% of a simultaneous lecture course.

2σ

7661.43

Top 2%

7216.70

61A/88 Grade vs. 61B Grade

From “Analysis of Factors and Interventions Relating to Student Performance in CS1 and CS2” by my former grad student:

A Supporting Experiment for “Everyone Can Do Well”

In Sp16, I gave students the option to fail intentionally.

• 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: There exists some sort of preparation for 61B that helps students do much better.

​

Bottom line: You’re capable of achieving more than you might think possible.

Your Life

Two interesting questions:

• What am I capable of achieving?
• 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 you must work for relatively low wages to uplift the downtrodden (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!)

AMA

Lecture 40, CS61B, Spring 2023

61B in 12 Minutes or Less

Your Future

AMA

Course Reflections

Questions About Anything for Justin and Me?

Course Reflections

Lecture 40, CS61B, Spring 2023

61B in 12 Minutes or Less

Your Future

AMA

Course Reflections

Some Old 61B History (black line is Fa18 61A): Tuning 61B’s Difficulty and Quality

*

* is a josh semester

*

*

*

*

*

*

*

*

*

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.

​

I’m particularly curious about:

• Your opinions about our deadlines policy (stiff at first, flexible later).
• Your ability to find help when you really needed it.
• Experiences with the project 3 autograder.
• Overall difficulty and workload of the course. Was there time that you wasted? If you have ideas, how could we avoid that wasted time.

Things For Next Time

Major possibilities:

• Tone down hw0b and project 0.
• Retire the project 3 autograder.
• Formal study groups for textbook exercises / midterm studying.
• Exercises in “beautiful code”, writing least complex solutions to toy problems.
• More formal instruction in using LLMs for project 3.
• More directed support for students with non-traditional backgrounds.
• Lower division CS/DS student learning center.
• Figure out how to run 61B more cost efficiently.
• Systemwide contract: UGSIs cost department ~$67/hour ($46/hour in wages + $19/hour in tuition remission) vs. ~$23/hour for tutors.
• Current bargaining process will hopefully establish new job titles.
• LLM debugging tools?

​

Feel free to suggest other changes!

61B Would Love to Have You Next Fall

• Academic interning: Learn more, help others, get units.
• Watch out for an announcement on the Spring 2023 61B Ed.

Special Thanks to Our Academic Interns (who keep the wheels on the bus)

Academic Interns: Aditya Murali Iyer, Aditya Rao, Afreen Shah, Aidan Gregory Leung, Aim Poonsornsiri, Alexander Huizar, Anahit Hovsepyan, Andrew Caslow, Audrey Burnett, Avik Samanta, Basem Moustafa, Boen Fan, Buyankhuu Tsolmonkhuu, Caleb Y Ro, Cambridge Bui-Nguyen, Catherine Chu, Diego Alejandro Huezo, Dongho Tommy Kim, Dora Du, Dylan Love, Elise Estela Rodriquez, Ella Culleton, Emma Wu, Farzan Ahmad Hashmi, Felix Zhu, Fiona Wu, Garrett Moore, Grant Zhao, Hanqi Xiong, Hongbo Wei, Isaiah Ou, Jackie Dai, Jacob Taegon Kim, Jacqueline Thibault, Japinder Singh Narula, Jeremy Villanueva, John Teng, Josh Barua, Julian Bixler, Karson Du, Keshav Raj Singhal, Khankamol Chor Kongrukgreatiyos, Kunal Agrawal, Martin M Lacsamana, Mateus Mori Ikezaki, Melody Law, Mohammad Shahnawaz, Mukhamediyar Kudaikulov, Mustafa Omar Mirza, Naomi Liu, Naveen Nathan, Nithurhan Carthikeyan, Noah Yin, Owen Gozali, Peter Le, Ryan James Whitty, Ryan Yang, Sai Kolasani, Sara Tetsu, Shreya Gupta, Sophia Zheng, Srilakshmi Chavali, Srinidhi Raghavendran, Steffi Bing Lin, Stephen Hwang, Stone Wu, Sushanth Sathish Kumar, Vincent Lin, Zehan Ma

Special Thanks to the Staff (who keep the wheels on the bus)

20 Hour/wk GSIs: Allen Gu, Jedidiah Tsang, Shreyas Kompalli, Sreevidya Ganga, Alex Schedel, Angelina Songco, Anish Bajaj, Anton Zabreyko, Aram Kazorian, Crystal Wang, Dominic Conricode, Edward Park, Ergun Acikoz, Eric Che, Lucy Lu, Meshan Khosla, Noah Adhikari, Sherry Fan

​

8 Hour/wk GSIs: Adit Shah, Alexander Lew, Ali Khani, Austin George, Circle Chen, Dhruti Pandya, Dylan Hamuy, Elana Ho, Elisa Kim, Emily Su, Hailey Park, Jasmine Lin, Jennifer Prince, Kenneth Wang, Kyle Zhang, Laksith Prabu, Max Ye, Omar Yu, Royce Ren, Sahityasree Subramanian, Samuel Berkun, Shirley Chen, Shreyas Kallingal, Stella Kaval, Yaofu Zuo

​

8 Hour/wk tutors: Aarin Salot, Aleem Lakdawala, Alexander Ng, Allen Cao, Allison hong, Angel Aldaco, Ashley Kao, Ashley Ye, Ayati Sharma, Carl Ji, Claire Thibodeaux, David Yang, Deepak Ragu, Dhruv Ahuja, Erik Kizior, Erik Nelson, Eshaan Moorjani, Ethan Lo, Ian Li, Janani Sriram, Jay Chou, Julian Tuazon, Kevin Sheng, Kevin Xu, Lawrence Shieh, Teresa Luo, Michael Wu, Mihir Mirchandani, Nadia Latifi, Nathalys Pham, Nicholas Nguyen, Olivia Huang, Pradyun Kumar, Ronald Wang, Sophie Nazarian, Surbhi Jain, Tanya Mehta, Taylor Hodan, Thomas Lee, Vanessa Teo, Vika Stukalova, Vikram Kumar, William Lee, Xifeng Li

​

Closing Thoughts

It is a terrifying and awesome responsibility to decide how you should spend hundreds of your precious hours here at Berkeley.

​

I do this job because I want you to live more fulfilling lives.

​

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

​

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