CS 61B Data Structures, Spring 2017
Instructor: Josh Hug
Lecture: MW 3-4 PM, Pauley Ballroom; F 3-4 PM, 320 Hertz Hall
First Week Only: Wednesday 1/18, Friday 1/20: 3-4 PM, Zellerbach Hall
Announcements [Past Announcements]
Date Announcement
7/27 Website testin.
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]
javac, java, git
Setting Up Your Computer
HW0: 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]
IDEs

IntelliJ Home Setup

Project 0: NBody (due TBA)
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 TBA ALists, Resizing, vs. SLists
[video] [slides] [code]
Linked Lists, Arrays
[Solution]
Testing, Debugging

JUnit Setup

Project 1A: Data Structures (due 2/6)
Wed 2/1 TBA Testing
[video] [slides] [code]
Fri 2/3 TBA Inheritance, Implements
[video] [slides] [code]
4 Mon 2/6 TBA Extends, Casting, Higher Order Functions
[video] [slides] [code]
Inheritance
[Solution]
Project 1 Code Reviews Project 1B: Testing and HoFs (due 2/10)
Wed 2/8 TBA Abstract Classes, More HoFs
[video] [slides] [code]
Fri 2/10 None Coding in the Real World
[video] [slides] [code]
5 Mon 2/13 TBA Packages, ADTs in Java, Java Libraries
[video] [slides] [code]
Selecting ADTs
[Solution]
Getting Started: Project 2 Midterm 1 (Date 2/14, 7-9PM)
Material up to 2/10
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 More Generics, Iterators, Iterable, Exceptions
[video] [slides] [code]
6 Mon 2/20 Academic Holiday
Wed 2/22 TBA Exceptions, Access Control, Objects
[video] [slides]
Immutability, Encapsulation Practices
[Solution]
Project 2 Design Review
Fri 2/24 TBA Encapsulation, Lists, Delegation vs. Extension
[video] [slides]
Project 2: X (due 3/6)
7 Mon 2/27 TBA Asymptotics I
[video] [slides] [guide]
Asymptotic analysis
[Solution]
Work on Project 2
Wed 3/1 TBA Asymptotics II
[video] [slides] [guide]
Fri 3/3 TBA Asymptotics III
[video] [slides] [guide]
8 Mon 3/6 TBA Disjoint Sets
[video] [slides] [guide]
Asymptotics
[Solution]
Tree Maps
Wed 3/8 TBA Trees, BSTs
[video] [slides] [guide]
HW 2: Percolation (due TBA)
Fri 3/10 TBA Balanced BSTs
[video] [slides] [guide]
9 Mon 3/13 TBA Hashing
[video] [slides] [guide]
Hashing
[Solution]
Hash Maps
Wed 3/15 TBA Heaps
[video] [slides] [guide]
Fri 3/17 None Advanced Trees, incl. Geometric
[video] [slides] [guide]
HW 3: Hashing (due TBA)
10 Mon 3/20 TBA Graphs
[video] [slides] [guide]
MT2 Prep
[Solution]
Heap MinPQ
Wed 3/22 None Midterm 2 Review
[video] [slides]
Midterm 2 (Date 3/22 (maybe), Time TBA)
Material up to ???
Fri 3/24 TBA Graph Traversals
[video] [slides] [guide]
HW 4: 8 Puzzle (due TBA)
Spring Break (March 27-31)
11 Mon 4/3 TBA Shortest Paths
[video] [slides] [guide]
Graphs
[Solution]
Graphs
Wed 4/5 TBA MSTs
[video] [slides] [guide]
Fri 4/7 TBA Dynamic Programming
[video] [slides] [guide]
Project 3: BearMaps (due TBA)
12 Mon 4/10 TBA Basic Sorting Algorithms
[video] [slides] [guide]
Graphs, Sorting
[Solutions]
Merge and Quick Sort
Wed 4/12 TBA Basic Sorts, Quick Sort
[video] [slides] [guide]
Fri 4/14 TBA More Quick Sort, Stability, Shuffling
[video] [slides] [guide]
13 Mon 4/17 TBA Sorting and Algorithmic Bounds
[video] [slides] [guide]
More Sorting
[Solution]
Radix Sort
Wed 4/19 TBA Radix Sorts
[video] [slides] [guide]
HW 5: Seam Carving (due TBA)
Fri 4/21 TBA Overview, Tries
[video] [slides] [guide]
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] [guide]
HW 6/7:Compression (dueTBA)
RRR Week (May 2-6) Makeup Lab: 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.