CS 61B Data Structures, Spring 2017
Instructor: Josh Hug
Lecture: MW 3-4 PM, Pauley Ballroom; F 3-4 PM, 320 Hertz Hall
Announcements [Past Announcements]
Date Announcement
Calendar
Week Date Reading Lecture Discussion Lab Assignments/Exams
1 Wed 1/18 1.1 Intro, Hello World Java
[video] [slides] [code]
Intro to Java
[Solution]
Setting Up Your Computer

javac, java, git
(due 1/27)
HW 0: Basic Java Programs (optional)
Fri 1/20 1.2 Defining and Using Classes
[video] [slides] [code]
2 Mon 1/23 2.1 References, Recursion, and Lists
[video] [slides] [code]
Scope, Pass-by-Value, Static
[Solution]
IntelliJ Home Setup

IDEs
(due 1/27)
Project 0: NBody (due 1/27 @ 11:59PM)
Wed 1/25 2.2 SLLists, Nested Classes, Sentinel Nodes
[video] [slides] [code]
Fri 1/27 2.3, 2.4 DLLists, Arrays
[video] [slides] [code]
3 Mon 1/30 2.5 ALists, Resizing, vs. SLists
[video] [slides] [code]
Linked Lists, Arrays
[Solution]
Testing, Debugging
(due 2/3)
Project 1A: Data Structures (due 2/3 @ 11:59 PM)
Wed 2/1 Optional: TDD is dead, Unit Tests Are Waste, Response Testing
[video] [slides] [code]
Fri 2/3 (Still TBA) Inheritance, Implements
[video] [slides] [code]
4 Mon 2/6 (Still TBA) Extends, Casting, Higher Order Functions
[video] [slides] [code]
Inheritance
[Solution]
Inheritance Exam Prep
[Solution] [Video]
Peer Code Review
(due 2/10)
Project 1B: Testing and HoFs (due 2/10 @ 11:59 PM)
Wed 2/8 TBA Subtype Polymorphism vs. HoFs
[video] [slides] [code]
Fri 2/10 None Libraries, Abstract Classes, Packages
[video] [slides] [code]
5 Mon 2/13 TBA Coding in the Real World, Review
[video] [slides]
Midterm Review Getting Started: Project 2 Midterm 1 (Date 2/14, 7-9PM)
Material up to 2/8
Wed 2/15 TBA Generics, Autoboxing
[video] [slides] [code]
HW 1: Java Syntax and Sound Synthesis (due 2/22)
Fri 2/17
Drop Deadline
TBA Exceptions, Iterators, Iterables
[video] [slides] [code]
6 Mon 2/20 Academic Holiday
Wed 2/22 TBA Packages, Access Control, Objects
[video] [slides]
Selecting ADTs
[Solution]
Selecting ADTs Exam Prep
[Solution] [Video]
Project 2 Design Review
Fri 2/24 TBA Encapsulation, Lists, Delegation vs. Extension
[video] [slides]
Project 2: Database (due 3/6)
7 Mon 2/27 Algs 170-198 (top paragraph) Asymptotics I
[video] [slides] [guide]
Asymptotic Analysis I
[Solution]
Asymptotic Analysis Exam Prep
[Solution] [Video]
Work on Project 2
Wed 3/1 Algs 170-198 Asymptotics II
[video] [slides] [guide]
Fri 3/3 Algs 170-198 Asymptotics III
[video] [slides] [guide]
8 Mon 3/6 Algs 216-233 Disjoint Sets
[video] [slides] [guide]
Asymptotic Analysis II
[Solution]

Asymptotic Analysis II Exam Prep
[Solution] [Video]
Tree Maps
(due 3/10)
Wed 3/8 Algs 396-406 Trees, BSTs
[video] [slides] [guide]
HW 2: Percolation (due 3/15)
Fri 3/10 Algs 424-431, 432-448 (extra) Balanced BSTs
[video] [slides] [guide]
9 Mon 3/13 Algs 458-468, 478-479, 468-475 (extra) Hashing
[video] [slides] [guide]
Hashing
[Solution] [Video]
Hashing Exam Prep
[Solution] [Video]
Hash Maps
(due 3/17)
Wed 3/15 Algs 308-320 Heaps
[video] [slides] [guide]
Fri 3/17 None Advanced Trees, incl. Geometric
[video] [slides] [guide]
HW 3: Puzzle Solver (due 3/23)
10 Mon 3/20 Algs 515-537 Graphs
[video] [slides] [guide]
Heaps and Graphs
[Solution]
Heaps and Graphs Exam Prep
[Solution] [Video]
Heap Min PQ
(due 3/24)
Wed 3/22 Algs 538-542, 566-583 Graph Traversals
[video] [slides] [guide]
Fri 3/24 None Regular Expressions
[video] [slides] [code]
HW 4: Hashing
(due 4/6)
Spring Break (March 27-31)
11 Mon 4/3 Algs 638-657 Shortest Paths
[video] [slides] [guide]
Graphs
[Solution]
Graphs Exam Prep
[Solution] [Video]
Midterm 2 Review
Wed 4/5 Algs 604-630 MSTs
[video] [slides] [guide]
Fri 4/7 N/A Midterm 2 Review
[slides]
Midterm 2 (Date 4/7, Time 4-6 PM)
Material up to 3/24
12 Mon 4/10 Algs 244-275, 323-327 Basic Sorting Algorithms
[video] [slides] [guide]
Graphs, Sorting
[Solution]
MST/SP Exam Prep
[Solution]
Merge and Quick Sort
(due 4/14)
Project 3: BearMaps (due 4/19)
Wed 4/12 Algs 288-296, 302 Basic Sorts, Quick Sort
[video] [slides] [guide]
Fri 4/14 Algs 341-347 More Quick Sort, Stability, Shuffling
[video] [slides] [guide]
13 Mon 4/17 Algs 279-282 Sorting and Algorithmic Bounds
[video] [slides] [guide]
More Sorting
[Solution]
Sorting Exam Prep
[Solution]
Radix Sort
(due 4/21)
Wed 4/19 Algs 702-718 Radix Sorts
[video] [slides] [guide]
Fri 4/21 Algs 730-752 Overview, Tries
[video] [slides] [guide]
HW 5: Seam Carving (due 4/26)
14 Mon 4/24 None Compression
[video] [slides] [guide]
Goodbye, Fun Fractal Sound
Wed 4/26 None Reductions, Algorithmic Bounds, NP Completeness
[video] [slides] [guide]
Fri 4/28 None Summary, Fun
[slides]
HW 6: Boggle (due 5/6) HW 7: Compression (due 5/6)
RRR Week (May 2-6) Lab 15: HugLife
Finals Week (May 9-13)
Lab/Discussion Schedule
Office Hour Schedule
Note: Office hours are located in 109 Morgan Hall (map here). On Thursdays and Fridays, feel free to come to lab with your questions.