Announcements
Your job from now until the final: Study a little each day.
¡ñ Final exam is comprehensive.
¡ñ Struggling students: DO EVERY C LEVEL PROBLEM. All of them.
¡ñ Work with other people!
¡ð Argue and discuss!
datastructur.es
CS61B
Lecture 40: Wrapping Things Up
¡ñ What We¡¯ve Done: 61B in 12 minutes or less.
¡ñ Moving Forwards.
datastructur.es
Where We Started
Just 14 weeks ago:
datastructur.es
What We¡¯ve Learned about Programming Languages
¡ñ Object based programming: Organize around objects.
¡ñ Object oriented programming:
¡ð Interface Inheritance.
¡ð Implementation inheritance.
Example: Programmer only needs to know List API, doesn¡¯t have to know that ArrayList secretly does array resizing.
¡ñ Dynamic vs. static typing.
¡ñ Generic Programming, e.g. ArrayList
¡ñ The model of memory as boxes containing bits.
¡ñ Bit representation of positive integers.
¡ñ Java.
¡ñ Some standard programming idioms/patterns:
Example: Array is a sequence of boxes. An array variable is a box containing address of sequences of boxes.
¡ð Objects as function containers (e.g. Comparators, IntUnaryFunctions).
¡ð Default method specification in interfaces (Link).
¡ð Iterators.
datastructur.es
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.
datastructur.es
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 (see midterm 2).
¡ð Multiplicative resizing results in ¦¨(1) add runtime for ArrayLists.
¡ð Additive resizing results in ¦¨(N) add runtime for ArrayLists.
datastructur.es
LinkedList
Resizing Array
Chaining HT
Heap
List
Set
LinkedList
PQ
Balanced Tree
Resizing Array
Map
Ordered Linked List
Quick Find Quick Union
BST (no balancing)
Red Black
B-Trees (2-3 / 2-3-4)
DisjointSets
WeightedQuickUnionUF
WQUPC
Trie and TST
Heap
Adjacency Matrix Edge List Adjacency Lists
Graph
Some Examples of Implementations for ADTs
datastructur.es
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 arrays vs. linked data structures.
datastructur.es
Tractable Graph Problems and Algorithms
vertex ordering
Topological Sort
Reachability
Cycle Detection
DFS Traversal
vertex markings
Bipartiteness
Discussed in section
Multiple Target Shortest Paths by # of Edges
shortest paths tree
Minimum Spanning Tree
Minimum Spanning Tree
Multiple Target Shortest Paths by Total Edge Weight
shortest paths tree
Single Target Shortest Paths by Total Edge Weight
shortest path
BFS Traversal
Prim¡¯s
Kruskal¡¯s Dijkstra¡¯s
DAGSPT A*
datastructur.es
Search-By-Key-Identity Data Structures:
2-3 Tree
RedBlack
Set
Map
External Chains
Linear Probing
Trie / TST
Searches using compareTo() Analogous to Comparison-Based
Searches using hashCode() and equals() Roughly Analogous to Integer Sorting
Searches by digit. Analogous to Radix Sorting
Comparison Based Sorting Algorithms: ¦¸(N log N) worst case If heapify first Heapsort
Selection
Merge
Partition
Insertion
If store in helper BST, eq. to
Radix Sorting Algorithms: ¦¨(NL) worst case: (require a sorting subroutine)
Counting
LSD
MSD
Small-Alphabet (Integer) Sorting Algorithms: ¦¨(N) worst case Counting
datastructur.es
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.
datastructur.es
The Practice of Programming
¡ñ Java syntax and idioms.
¡ñ JUnit 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, command line
¡ñ Data structure selection (and API Design)
¡ð Drive the performance and implementation of your entire program.
datastructur.es
The Future
datastructur.es
Your Life
Two interesting questions:
¡ñ What am I capable of achieving?
¡ñ What should I do with my life?
datastructur.es
Some Josh Hug History
datastructur.es
Midterm 1
datastructur.es
Poll
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.
a. Strongly disagree
b. Disagree
c. Neutral
d. Agree
e. Strongly agree
datastructur.es
Growth vs. Fixed Mindset
Students can be thought of as having either a ¡°growth¡± mindset or a ¡°fixed¡± mindset (based on research by Carol Dweck).
¡ñ ¡°In a fixed mindset students believe their basic abilities, their intelligence, their talents, are just fixed traits. They have a certain amount and that’s that, and then their goal becomes to look smart all the time and never look dumb.¡±
¡ð Perhaps most damningly, having to put in effort is a sign of weakness! ¡ñ ¡°In a growth mindset students understand that their talents and abilities
can be developed through effort, good teaching and persistence. They don’t necessarily think everyone’s the same or anyone can be Einstein, but they believe everyone can get smarter if they work at it.¡±
datastructur.es
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.
datastructur.es
A Supporting Experiment
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.
Possible 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.
datastructur.es
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.
datastructur.es
Choices (Yup)
How you use your skills is up to you.
datastructur.es
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!).
¡ñ …. but keep in mind that your work will profoundly affect the world.
(Wanna talk about this stuff more? Take CS195!)
datastructur.es
Questions About Anything?
datastructur.es
Questions About Anything?
datastructur.es
Course Reflections
datastructur.es
Reflection on the Course: New for Spring 2021
New 61B features since last time I taught 61B (Fall 2020):
¡ñ 6 slip days plus flexible policy for people who came to use with life crises.
¡ñ 2048 instead of NBody.
¡ñ Gitlet instead of Bearmaps.
¡ñ More widespread use of Snaps plugin including data analysis (see lec34).
¡ñ Two conceptual homeworks instead of 1.
¡ñ Asynchronous checkoff for project 3.
datastructur.es
On the Subject of Difficulty: 61B History (black line is Fa18 61A)
* is a josh semester
**
*
*
*
**
**
*
datastructur.es
Fall 2022: Things For Next Time
Major possibilities:
¡ñ Replace Gitlet with something that has significant data structures content but still features a significant design component (e.g. open-ended BearMaps, Sp15 Ngordnet project).
¡ð Could also maybe revise Gitlet, but I think it¡¯s too big.
¡ñ More proactively help students find community / study groups.
¡ñ Make sharing project 3 even easier online.
¡ñ Midterm 1 that allows students to execute code?
¡ñ Weekly theory homework that synchronizes with discussion?
¡ñ Make project 3 multiplayer?
¡ñ Lectures, discussions, and labs in person.
Let me know what else you might want to see on post-final exam survey.
datastructur.es
Any Questions About Course Structure?
datastructur.es
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.
datastructur.es
61B Needs You Next Fall
¡ñ Academic interning: Learn more, help others, get units, maybe become a GSI.
¡ñ Watch out for an announcement on the Spring 2021 61B Ed.
datastructur.es
Special Thanks to the Staff (who keep the wheels on the bus)
Full time GSIs: Ada Hu, Alex Schedel, Allyson Park, Anjali Kantharuban, Arjun Sahai, Boren Tsai, Claire Ko, Connor Lafferty, Eric Tang, Eric Zhu, Henry Maier, Itai Smith, Linda Deng, Neil Kulkarni, Omar Khan, Sohum Hulyalkar, Sumer Kohli
Part time GSIs: Ajay Singh, Anton Zabreyko, Aram Kazorian, Cindy Zhang, Crystal Wang, Ethan Mehta, Fatema Yasini, Grace Altree, Hannah Yan, Isha Srinivasan, Jack Wang, Joshua Blanchard, Joshua Yang, Luke Liu,
Naama Bareket, Richa Kotni, Robin Qiu, Romain Priour, Sara Reynolds, Sarah Liu, Sarina Sabouri, Sherry Fan, Shreyas Kompalli, SreeVidya Ganga, Tony Kam
Tutors: Abhishek Kumar, Ahmed Baqai, Angela Chen, Arushi Somani, Avyakth Challa, David Lee, Jesse Dai, Michael Sparre, Nandini Singh, Nikhil Mandava, Nishant Patwardhan, Saad Jamal, Saikumar Gantla, Sean Kim, Shreyans Sethi, Shriya Nandwani, Smruthi Balajee, Srinidhi Sankar, Todd Yu
Academic Interns: Justin Thein, Kyle Yu, De Zheng Zhao, Michael Huang, Rahul Mohankumar, Deepak Ragu, Tymon Thi, Devin Sze, YiTing Yan, David Chung, Viansa Schmulbach, Ritik Batra, Yash Gupta, Arda Demirci, Anik Gupta, Nitya Goyal, Paris Zhang, Stephanie Jue,
Dexter To, Sean Hayes, Olivia Huang, Genevieve Brooks, Noah Schwartz, Kush Garg, Reza Sajadiany, Michelle Cheung, Maryam Azmandian, Amanda Yao, Andrew Lee, Haroun Khaleel, Catherine Hwu, Stephen Yang, Jerry Sun, Aady Pillai, Emmett Dreyer, Kaci Gu, Richard Lee, Suhrid Saha, Sunay Dagli, Fakhri Widodo, Shefali Goel, Alina Trinh, Amritansh Saraf, Siddhant Sharma, Phoebe Troup-Galligan, Steven Chen, Abrar Rahman, Xinqi Yu, Sum Ying Celeste Wu, Brenda Huang, Zoe Parcells, Nathan Tran , Aditi Bamba, Jasper Emhoff, Amudha Sairam, Ananya Gupta, Samuel Stulman, Carolina Rios-Martinez, Ola Alsaedi , Shivani Ahuja, Tiffany Luu, Isha Arora, Lawrence Gan, Aditya Prasad, Daniel Detchev, Grace Chen, Austin Ho, Nicholas Cheng, Shannon Bonet , Jane Lee, Kaaviya Sasikumar, Ankita Janakiraman, Kevin Jin, Kuhu Sharma, Vivian Liu, Xinyu Fu, Sofia Roz, Walker Browning, Efsane Soyer, Christopher Seo, Grace Cen, Maggie Yi, Rohan Khandelwal
That¡¯s 17 full time GSIs, 25 part time GSIs, 19 tutors, 83 academic interns, 1 me, 1437 you.
datastructur.es