CS 61B Spring 2024

Instructors: Justin Yokota, Peyrin Kao /Lecture: 1-2PM MWF, Dwinelle 155, Zoom

Weekly Schedule

Wk.	Date	Lecture (Zoom)	Readings	Discussion	Lab	Homework	Project
1 Survey	Wed Jan 17	1. Intro [Intro Video 2D Reflections on Java ] [1a Welcome to 61B Spring 2023] [1b 61B Logistics] [1C Phase 1 Overview] [2A Hello World] [2B Static Typing] [2C Declaring Functions] [Recording] [Pacing 3a Compilation] [3b IntelliJ Demo] [3c HW0A Due Friday] [Pacing Points- Lecture 1] [Slides-Lecture 1]	[Ch 1.1] [Ch 1.2] [Ch 1.3] [Ch 1.4]	No Discussion	[Lab 1: Setup ] [lab01-tip-Terminal] [lab01-tip-windows] [Pacing Points-Lecture 2 - Defining and Using Classes] (due 1/19) Slides-Lecture 2 - Defining and Using Classes [pdf] [pptx] [[Spring 2024] Lab 1.pdf] [[Spring 2024] Lab 1.pptx]	Homework 0A (due 1/19)
	Fri Jan 19	2. Defining and Using Classes [Video] [2a Defining and Instantiating Classes] [2b Defining and Instantianing Classes] [2c Terminology] [2d Arrays of Objects] [3a Static vs Instance Methods] [3b Exercise] [3c Exercise Solution] [4a Managing Complexity LargerThanFourNeighbors] [4b LargerThanFourNeighbors With No Helper Methods] [4c LargerThanFourNeighbors With Helper Methods]	[Ch 2]			Homework 0B (due 1/22)	Project 0: 2048 (due 1/29)
2 Survey	Mon Jan 22	3. Lists I: References, Recursion, and Lists [Video] [ 2023 Welcome] [1 The Mystery of the Walrus] [2 Primitive Types] [3 Reference Types] [4 Parameter Passing] [5 Test Your Understanding of the GRoE] [6 Instantiating Arrays] [7 Introducing IntLists] [8 IntList size] [9 IntList iterativeSize] [Pacing] [Slides]	[Ch 3]	1. Introduction to Java	[Lab 2: Debugging I[Spring 2024] Lab 2.pdf] [[Spring 2024] Lab 2.pptx] (due 1/26) Slides [pdf] [pptx]
	Wed Jan 24	4. Lists II: SLLists [Video] [1A Introducing the SLList] [1B Introducing the SLList Bureaucracy] [1C Introducing the SLList SLList Methods] [2 Access Control and Nested Classes] [3 addLast and size] [4 Caching] [5 The Empty List] [6 Sentinel Nodes] [7 Invariants] [ Pacing]	[Ch 4]			Homework 1 (due 1/26)
	Fri Jan 26	5. Lists III: DLLists and Arrays [Video] [1 Summary of SLLists So Far] [2 Why a Last Pointer Isnt Enough] [3 Doubly Linked Lists] [4 Generic Lists] [5 Array Overview] [6 Basic Array Syntax] [7 2D Arrays] [8 Arrays vs Classes] [Pacing]	[Ch 5] [Ch 6]
3 Survey	Mon Jan 29	6. Testing [Video] [01Lecture 6 Spring 2023 Testing] [02Testing Bonus Video on Testing Philosohpy] [Pacing] [Slides-Lecture 6 - Testing.pdf] [Slides-Lecture 6 - Testing.pptx]	[Ch 7]	2. Scope, Static, Linked Lists, Arrays	[Lab 3: Debugging II] [[Spring 2024] Lab 3.pdf] [[Spring 2024] Lab 3.pptx] (due 2/2)
	Wed Jan 31	7. Lists IV: Arrays and Lists [Video] [1 Why Array Lists] [2 The Naive AList] [3 The Allegory of the Cave] [4 removeLast] [5 Resizing Arrays] [6 Resizing Implementation] [7 Basic Resizing Analysis] [8 Harder Resizing Analysis] [9 Making AList Fast ] [Pacing] [Slides-Lecture 7 - Lists 4_ Arrays and Lists.pdf] [Slides-Lists 4_ Arrays and Lists.pptx]	[Ch 8]				Project 1A: LinkedListDeque61B (due 2/5)
	Fri Feb 02	8. Inheritance I: Interface and Implementation Inheritance [Video] [1 The Desire for Generality ] [2 Hypernyms and Hyponyms ] [3 The Interface and Implements Keywords ] [4 Overriding vs Overloading ] [5 Interface Inheritance] [6 Implementation Inheritance and Default Methods] [ 7 Overriding Default Methods] [8 Dynamic Method Selection] [9 Warning About Changes to Dynamic Method Selection in 61B] [Conclusion Is a vs Has a Interface vs Implementation Inheritances] [Pacing] [Slides-Lecture 8 - Inheritance 1_ Interface and Implementation Inheritance.pdf] [Slides-Lecture 8 - Inheritance 1_ Interface and Implementation Inheritance.pptx]	[Ch 9]
4 Survey	Mon Feb 05	9. Inheritance II: Extends, Casting, Higher Order Functions [Video] [1 Basic Use of Extends ] [2 Extends with Overriding] [3 A Boring Constructor Gotcha /4A The Object Class] [4b javautilStack /5 Encapsulation] [6 How Inheritance Breaks Encapsulation] [7 Type Checking and Casting] [8 Higher Order Functions in Java] [Pacing] [Slides-Lecture 9 - Inheritance 2_ Extends, Casting, Higher Order Functions.pdf] [Slides-Lecture 9 - Inheritance 2_ Extends, Casting, Higher Order Functions.pptx]	[ch10.1] [ch10.2] [ch10.3] [ch10.4] [ch10.5] [Ch 10]	3. Inheritance	Project 1 Workday
	Wed Feb 07	10. Inheritance III: Subtype Polymorphism, Comparators, Comparable [Video] [0 Dynamic Method Selection Puzzle optional ] [1 Subtype Polymorphism] [2 The Max Function] [3 OurComparable Example] [4 Compilation Quiz] [5 Comparables] [6 Comparator] [Pacing] [Slides-Lecture 10 - Inheritance 3_ Subtype Polymorphism, Comparators, Comparable.pdf] [Slides-Lecture 10 - Inheritance 3_ Subtype Polymorphism, Comparators, Comparable.pptx]	[Ch 11.1] [Ch 11.2] [Ch 11.3] [Ch 11.4] [Ch 11.5] [Ch 11.6] [Ch 11]				Project 1B: ArrayDeque61B (due 2/12)
	Fri Feb 09	11. Inheritance IV: Iterators, Object Methods [Video] [01CS61B 2023 Lec 12 ArraySet and Setting the Stage] [Part 3 exceptions] [Part 4 Iterable] [Part 5 toString] [Part 6 this equals] [Part 7 Summary /Part 8 EXTRA fancier to String and the of static method ] [Pacing] [Slides-Lecture 11 - Inheritance 4_ Iterators, Object Methods.pdf] [Slides-Lecture 11 - Inheritance 4_ Iterators, Object Methods.pptx]	[Ch 12.1] [Ch 12.2] [Ch 12.3] [Ch 12.4] [Ch 12.5] [Ch 12.6]
5 Survey	Mon Feb 12	12. Asymptotics I [Video] [1 Welcome to the Second Half of 61B] [2 Characterization 1 Clock Time] [3 Technique 2 Operation Counting] [4 Technique 2 Operation Counting Exercise] [5 Why Scaling Matters] [6 Worst Case Orders of Growth] [7 Simplified Analysis] [8 Big Theta] [9 Big O] [10 Big Omega] [Pacing] [Slides-Lecture 12 - Asymptotics 1.pdf] [Slides-Lecture 12 - Asymptotics 1.pptx]	[Ch 13.1] [Ch 13.2] [Ch 13.3] [Ch 13.4] [Ch 13.6] [Ch 13.7] [Ch 13.8] [Ch 13.9] [Ch 13.10]	4. Comparators, Iterators	[Lab 4: Git] [[Spring 2024] Lab 4.pdf] [[Spring 2024] Lab 4.pptx] (due 2/20) Slides
	Wed Feb 14	13. Ask Anything: Midterm 1 [Slides-Lecture 13 - Midterm 1 Q&A.pdf] [Slides-Lecture 13 - Midterm 1 Q&A.pptx]					Project 1C: Deque61B Enhancements (due 2/20)
	Thu Feb 15	Midterm 1 (7-9PM)
	Fri Feb 16	14. Disjoint Sets [Video] [1 Intro to Disjoint Sets] [2 Quick Find] [3 Quick Union] [4 Weighted Quick Union] [5 Weighted Quick Union with Path Compression and Summary] [Pacing] [Slides-Lecture 14 - Data Structures 1_ Disjoint Sets.pdf] [Slides-Lecture 14 - Data Structures 1_ Disjoint Sets.pptx]	[Ch 14.1] [Ch 14.2] [Ch 14.3] [Ch 14.4] [Ch 14.5] [Ch 14.6]			Homework 2 (due 2/26)
6 Survey	Mon Feb 19	No Lecture (Academic Holiday)		5. Asymptotics, Disjoint Sets	[Lab 5: Disjoint Sets] [[Spring 2024] Lab 5.pdf] [[Spring 2024] Lab 5.pptx] (due 2/26)
	Wed Feb 21	15. Asymptotics II [Vidio] [1 Simple Nested Loops in Big Theta] [2 Nested For Loops with Geometric Outer Loop] [3 There is No Magic Shortcut for these Problems] [4 Tree Recursion] [5 Binary Search Intuitive] [6 Binary Search Exact] [7 Merge Sort Prelude] [8 Merge Sort] [9 Summary] [Pacing] [Slides-Lecture 15 - Asymptotics 2.pdf] [Slides-Lecture 15 - Asymptotics 2.pptx]	[Ch 15.1] [Ch 15.2] [Ch 15.3] [Ch 15.4] [Ch 15.5] [Ch 15.6]				Project 2A: NGrams (due 3/6)
	Fri Feb 23	16. ADTs, Sets, Maps, BSTs [Vidio] [1 ADTs and Maps] [2 Inventing the BST] [3 BST Definitions] [4 BST Search] [5 BST Insert] [6 BST Deletion] [7 Sets vs Maps Summary Tips for Lab] [Pacing] [Slides-Lecture 16 - Data Structures 2_ ADTs, BSTs.pdf] [Slides-Lecture 16 - Data Structures 2_ ADTs, BSTs.pptx]	[Ch 16.1] [Ch 16.2] [Ch 16.3] [Ch 16.4] [Ch 16.5] [Ch 16.6] [Ch 16.7]
7 Survey	Mon Feb 26	17. B-Trees (2-3, 2-3-4 Trees) [Vidio] [1 Tree Height Big O vs Worst Case] [2 BST Performance] [3 B Tree Basic Insertion] [4 Splitting Non Leaf nodes Terminolgoy] [5 Bushiness Invariants for B Trees] [6 Runtime Analysis Summary] [Pacing] [Slides-Lecture 17 - Data Structures 3_ B-Trees.pdf] [Slides-Lecture 17 - Data Structures 3_ B-Trees.pptx]	[Ch 17.1] [Ch 17.2] [Ch 17.3] [Ch 17.4] [Ch 17.5] [Ch 17.6] [Ch 17.7]	6. ADTs, Asymptotics II, BSTs	[Lab 6: BSTMap] [[Spring 2024] Lab 6.pdf] [[Spring 2024] Lab 6.pptx] (due 3/01)
	Wed Feb 28	18. Red Black Trees [Vidio] [1 Intro Rotation] [2 Balancing with Rotation] [3 Red Black Tree Definition] [4 Red Black Tree Properties] [5 Red Black Tree Insertion] [6 Red Black Tree Exercise Optional] [7 Red Black Tree Exercise Solution Optional] [8 Red Black Tree Performance and SummaryPacing] [Slides-Lecture 18 - Data Structures 4_ Tree Rotation and Red-Black Trees.pdf ] [Slides-Lecture 18 - Data Structures 4_ Tree Rotation and Red-Black Trees.pptx]	[Ch 18.1] [Ch 18.2] [Ch 18.3] [Ch 18.4] [Ch 18.5] [Ch 18.6]
	Fri Mar 01	19. Hashing [Vidio] [Pacing] [Slides-Lecture 19_ Hashing.pdf ] [Slides-Lecture 19_ Hashing.pptx]	[Ch 19.1.1] [Ch 19.1.2] [Ch 19.1.3] [Ch 19.1] [Ch 19.2] [Ch 19.3] [Ch 19.4] [Ch 19.5] [Ch 19.6] [Ch 19.7]
8 Survey	Mon Mar 04	20. Hashing II [Vidio] [1 Hash Table Recap Default Hash Function] [2 Distribution by Other Hash Functions and ChatGPT] [3 Why Bother With Custom Hash Functions] [4 HashSet Contains] [5 Duplicate Items equals and hashcode] [7 Dont Mutate Objects in a HashSet] [8 A Peek Inside the Java HashSet] [Pacing]	[Ch 20.1] [Ch 20.2] [Ch 20.3] [Ch 20.4]	7. B-Trees, LLRBs, Hashing [Slides-Lecture 20 - Hashing II.pdf] [Slides-Lecture 20 - Hashing II.pptx]	[Lab 7: LLRBs] [[Spring 2024] Lab 7.pdf] [[Spring 2024] Lab 7.pptx] (due 3/08)
	Wed Mar 06	21. Heaps and Priority Queues</br> [Vidio] [1 Introducing the Priority Queue] [2 Basic Use and Naive Implementations of the PQ] [3 Introducing the Heap] [4 Heap Operations] [5 Tree Representations] [6 PQ Implementation Considerations] [7 Data Structures Summary] [Pacing] [Slides-Lecture 21 - Data Structures 5_ Priority Queues and Heaps.pdf] [Slides-Lecture 21 - Data Structures 5_ Priority Queues and Heaps.pptx]	[Ch21.1] [Ch21.2] [Ch21.3] [Ch21.4] [Ch21.5]
	Fri Mar 08	22. Tree and Graph Traversals [Vidio] [1 Tree Traversals] [2 Graph Definition] [3 Graph Problems] [4 s t Connectivity] [5 DepthFirstPaths] [6 Tree vs Graph Traversals] [Pacing] [Slides-Lecture 22 - Graphs 1_ Graphs and Traversals.pdf] [Slides-Lecture 22 - Graphs 1_ Graphs and Traversals.pptx]	[Ch22.1] [Ch22.2] [Ch22.3] [Ch22.4]				Project 2B/2C Checkpoint and Design Doc (due 3/15)
9 Survey	Mon Mar 11	23. Graph Traversals and Implementations [Vidio] [Pacing] [Slides-Lecture 23 - Graphs 2_ DFS, BFS, Implementations.pdf ] [Slides-Lecture 23 - Graphs 2_ DFS, BFS, Implementations.pptx]	[Ch23.1] [Ch23.2] [Ch23.3] [Ch23.4]	8. Graphs, Heaps	[Lab 8: HashMaps] [[Spring 2024] Lab 8.pdf] [[Spring 2024] Lab 8.pptx] (due 3/15)	Homework 3 (due 3/18)
	Wed Mar 13	24. Shortest Paths [Vidio ] [Pacing] [Slides-Lecture 24 - Graphs 3_ Shortest Paths.pdf ] [Slides-Lecture 24 - Graphs 3_ Shortest Paths.pptx]	[Ch24.1] [Ch24.2] [Ch24.3] [Ch24.4] [Ch24.5]
	Fri Mar 15	25. Minimum Spanning Trees [Vidio] [Pacing] [Slides-Lecture 25 - Graphs 4_ Minimum Spanning Trees.pdf] [Slides-Lecture 25 - Graphs 4_ Minimum Spanning Trees.pptx]	[Ch25.1] [ch25.2] [ch25.3] [ch25.4] [ch25.5]
10 Survey	Mon Mar 18	26. Directed Acyclic Graphs [Vidio] [Pacing] [Slides-Lecture 26 - Graphs 5_ Directed Acyclic Graphs.pdf] [Slides-Lecture 26 - Graphs 5_ Directed Acyclic Graphs.pptx]	[Ch28.1] [Ch28.2] [Ch28.3] [Ch28.4] [Ch28.5]	9. Shortest Paths, MSTs	Project 2 Workday		Project 2B: Wordnet Project 2C: Enhancements (due 4/1)
	Wed Mar 20	27. Software Engineering I [Vidio] [Slides-Lecture 27 - Software Engineering I.pdf] [Slides-Lecture 27 - Software Engineering I.pptx]	[Ch27.1] [Ch27.2] [Ch27.3] [Ch27.4] [Ch27.5]
	Thu Mar 21	Midterm 2 (7-9PM)
	Fri Mar 22	28. Prefix Operations and Tries [Vidio] [Pacing] [Slides-Lecture 28 - Tries.pdf] [Slides-Lecture 28 - Tries.pptx]	[Ch26.1] [Ch26.2] [Ch26.3] [Ch26.4] [Ch26.5]
11	Mon Mar 25	No Lecture (Spring Break)		No Discussion	No Lab
	Wed Mar 27
	Fri Mar 29
12 Survey	Mon Apr 01	29. Sorting I: Selection Sort, Heapsort [Vidio] [Pacing] [Slides- Lecture 29 - Sorting 1_ Basic Sorts.pdf ] [Slides- Lecture 29 - Sorting 1_ Basic Sorts.pptx]	[Ch 29.1] [Ch 29.2] [Ch 29.3] [Ch 29.4] [Ch 29.5] [Ch 29.6]	10. Graphs II, Tries	[Lab 9: Getting Started on Project 3] [[Spring 2024] Lab 9.pdf] [[Spring 2024] Lab 9.pptx] (due 4/05)
	Wed Apr 03	30. Sorting II: Mergesort and Insertion Sort [Vidio] [Pacing] [Slides- Lecture 30 - Sorting 2_ Mergesort, Insertion Sort, and Quicksort.pdf] [Slides- Lecture 30 - Sorting 2_ Mergesort, Insertion Sort, and Quicksort.pptx]	[Ch 30.1] [Ch 30.2] [Ch 30.3] [Ch 30.4] [Ch 30.5]				Project 3A: World Generation (due 4/15)
	Fri Apr 05	31. Software Engineering II [Slides-Lecture 31 - Software Engineering II.pdf ] [Slides-Lecture 31 - Software Engineering II.pptx]	[Ch 31.1] [Ch 31.2] [Ch 31.3] [Ch 31.4] [Ch 31.5]
13 Survey	Mon Apr 08	32. Sorting III: Quicksort [Vidio] [Pacing] [Slides-Lecture 32 - Sorting 3_ More Quicksort, Quick Select, Stability.pdf] [Slides-Lecture 32 - Sorting 3_ More Quicksort, Quick Select, Stability.pptx]	[Ch 32.1] [Ch 32.2 /Ch 32.3] [Ch 32.4] [Ch 32.5]	11. Sorting	[Lab 10: Tetris] [[Spring 2024] Lab 10.pdf] [[Spring 2024] Lab 10.pptx] (due 4/12)
	Wed Apr 10	33. Sorting IV: Sorting and Algorithmic Bounds [Vidio] [1 Math Warmup] [2 Simple Bounds for TUCS] [3 Puppy Cat Dog] [4 Puppy Cat Dog] [Pacing] [Slides-Lecture 34 - Sorting 4_ Theoretical Bounds on Sorting.pdf] [Slides-Lecture 34 - Sorting 4_ Theoretical Bounds on Sorting.pptx]	[Ch 34.1] [Ch 34.2] [Ch 34.3] [Ch 34.4] [Ch 34.5]
	Fri Apr 12	34. Software Engineering III [61B SP24] Lecture 34 - Software Engineering III.pdf [61B SP24] Lecture 34 - Software Engineering III.pptx	[Ch 33.1] [Ch 33.2] [Ch 33.3] [Ch 33.4] [Ch 33.5]
14 Survey	Mon Apr 15	35. Sorting V: More Quicksort, Radix Sorts [Vidio] [Pacing] [Slides-Lecture 35 - Sorting 5_ Radix Sorts.pdf] [Slides-Lecture 35 - Sorting 5_ Radix Sorts.pptx]	[Ch 35.1] [Ch 35.2] [Ch 35.3] [Ch 35.4] [Ch 35.5]	12. More Sorting	Project 3 Workday
	Wed Apr 17	36. Sorting VI: Radix vs. Comparison Sorting [Vidio] [1 Intuitive Analysis of Radix Sort vs Comparison Sort] [2 Cost Model Analysis of Radix Sort vs Comparison Sort] [3 Hypothesis that Merge Sort will be Slower] [4 Running Our Empirical Analysis] [5 The Just In Time Compiler] [6 Rerunning Our Experiment with the JIT Disabled] [7 Radix Sorting Integers] [8 Sorting Summary] [Pacing] [Slides-Lecture 36 - Sorting 6_ Radix vs. Comparison Sorting.pdf] [Slides-Lecture 36 - Sorting 6_ Radix vs. Comparison Sorting.pptx]	[Ch 36.1] [Ch 36.2] [Ch 36.3] [Ch 36.4] [Ch 36.5]				Project 3B/C: Interactivity + Ambition (due 4/22)
	Fri Apr 19	37. Software Engineering IV [Slides-Lecture 37 - Software Engineering IV.pdf ] [Slides-Lecture 37 - Software Engineering IV.pptx]	[Ch 37.1]
15 Survey	Mon Apr 22	38. Compression [Vidio] [1] [2 codes morse code] [3 prefix free codes] [4 shannon fano codes] [5 huffman coding] [6 data structures for huffman coding] [7 huffman encoding demo] [8 huffman encoding demo] [9 proof that universal compression is impossible an alternate model for compression] [10 HugPlant] [Slides- Lecture 38 - Compression.pdf] [Slides- Lecture 38 - Compression.pptx ] [Pacing]	[Ch 38.1] [Ch 38.2] [Ch 38.3] [Ch 38.4] [Ch 38.5] [Ch 38.6] [Ch 38.7] [Ch 38.8]	13. Goodbye, Fun	Project 3 Checkoffs
	Wed Apr 24	39. Complexity and P=NP? [Vidio] [1 model 2 compression re explained] [2 compressing the hugplant] [3 kolmogorov complexity] [4 space and time bounded compression] [5 does P NP] [6 almost like gods] [7 short but not comprehensible fractal sound] [Slides- Lecture 39 - Computability.pdf] [Slides- Lecture 39 - Computability.pptx]	[Ch 39.1] [Ch 39.2] [Ch 39.3] [Ch 39.4] [Ch 39.5]			Homework 4 (due 4/28, extendable to 5/3)
	Fri Apr 26	40. Summary, Fun
16	Mon Apr 29	No Lecture (RRR Week)		No Discussion	No Lab
	Wed May 01
	Fri May 03
17	Tue May 07	Final Exam (May 7th, 8-11AM)