CS61B Data Structures, Spring 2019

Instructor: Josh Hug

• Intro, Hello World Java
• Defining and Using Classes
• References, Recursion, and Lists
• SLLists, Nested Classes, Sentinel Nodes
• DLLists, Arrays
• ALists, Resizing, vs. SLists
• Testing
• Inheritance, Implements
• Extends, Casting, Higher Order Functions
• Subtype Polymorphism vs. HoFs
• Exceptions, Iterators, Object Methods
• Coding in the Real World, Review
• Asymptotics I
• Disjoint Sets
• Asymptotics II
• ADTs, Sets, Maps, BSTs
• B-Trees (2-3. 2-3-4 Trees)
• Red Black Trees
• Hashing
• Heaps and PQs
• Prefix Operation and Tries
• Range Searching and Multi-Dimensional Data
• Tree and Graph Traversals
• Graph Traversals and Implementations
• Shortest Paths
• Minimum Spanning Trees
• Reductions and Decomposition
• Basic Sorts
• Quick Sort
• More Quick Sort, Sorting Summary
• Sorting and Algorithmic Bounds
• Radix Sorts
• Sorting and Data Structure Conclusion
• Compression
• Compression, Complexity, and P=NP?

• Lab 01: javac, java, git
• Lab 02 Setup: Setting Up IntelliJ
• Lab 02: Unit Testing with JUnit and IntLists
• Lab 03: Unit Testing with JUnit, Debugging
• Lab 04: Peer Code Review
• Lab 05: HugLife
• Lab 06: Disjoint Sets
• Lab 07: TreeMap
• Lab 08: HashMap
• Lab 09: Tries
• Lab 11: Merge Sort and Quick Sort
• Lab 12: Getting Started on Project 3
• Lab 13: Getting Started on Project 3, Phase 2
• Challenge Lab 06: Falling Bubbles
• Challenge Lab 07: Binary Search Tree Performance
• Challenge Lab 08: Heaps and Hashes
• Challenge Lab 09: Graphs

• Homework 0: Basic Java Programs
• Homework 1: Java Syntax and Sound Synthesis
• Homework 2: Percolation
• Homework 3: Hashing
• Homework 4: Puzzle Solver

• Project 0: NBody
• Project 1A: Data Structures
• Project 1B: Testing and HoFs
• Project 2AB: HeapPQ/KD-Tree
• Project 2C: Bear Maps
• Project 3A: BYOW Phase 1
• Project 3B: BYOW Phase 2