CS 61BL Summer 2017
Data Structures & Programming Methodology
Instructors: Daniel Nguyen & Daniel Sochor
Wednesday, 3-5 PM, 2050 Valley Life Sciences Building
Office Hours: 779 Soda, Monday/Thursday 10-11AM, Tuesday/Friday 4-5PM
Quick Navigation
Labs
Labs are due the next day two hours before your lab's start time. For example, if your lab begins at 3 PM, Tuesday's lab will be due on Wednesday at 1 PM. This deadline is meant to be fair for those in labs that occur later in the day. Both students in a partnership must submit the files.
Number Title Concepts
1 Git & Intro to Java Git, Basic Java Syntax, Compilation
2 Primitives & References Primitives, Objects, Box & Pointer Diagrams, Java Stack & Heap
3 Conditionals, Loops, Arrays If/Else Suits, While/For Loops, Arrays
4 OOP & Scope OOP, Inheritance, Dynamic vs Static Type, Polymorphism, Scope
5 Linked Lists I Singly Linked Lists
6 Linked Lists II Encapsulation, Doubly Linked Lists, Sentinel Linked Lists
7 Asymptotic Analysis Asymptotics, Big-O, Big-Omega, Big-Theta, Runtime Analysis
8 Exceptions, Invariants, Testing Exceptions, Invariants, JUnit, TDD
9 Collections, Interfaces, Abstract Classes Collections, Interfaces, Abstract Classes, Lists, ArrayLists
10 Iterators, Generics Iterators, Generics,
11 Equality, Comparison, and Java 8 Equality, Comparables, Comparators, Streams, HOF
12 Trees I General Trees, Binary Trees
13 Trees II Tree Iteration
14 Binary Search Trees Binary Search Trees
15 Hashing I Hash Tables/Maps, External Chaining
16 Hashing II Hash Map Applications
17 Balanced Search Trees Splay Trees, 2-3-4 Trees, Red-Black Trees
18 Heaps, Priority Queues Heaps, Binary Heaps, Priority Queues
19 Graphs Graphs, Graph Representations, Graph Traversals, Topological Sorting
20 Graph Algorithms Dijkstra's Algorithm, Graph Applications
21 Comparison-Based Sorts Insertion Sort, Selection Sort, Heap Sort, Merge Sort, Quick Sort
22 Counting-Based Sorts Quickselect, Stability, Counting Sort, Radix Sort (MSD/LSD)
23 Disjoint Sets & Kruskal's Algorithm Disjoint Sets, Kruskal's Algorithm, Minimum Spanning Trees
24 Regex Regex
Projects
Number Title Concepts Due Date
1 Cube Puzzle Java, Arrays, MVC Architecture Sat 7/1, 11:59PM
2 Gitlet Software Engineering, Design, Git Sat 7/22, 11:59PM
3 TBA TBA Sat 8/5, 11:59PM
Exams
Exam Concepts Solutions
Midterm 1 Java syntax, Array, Linked list, OOP, Inheritance, Dynamic method lookup Solution
Midterm 2 Balanced Search Trees, Data Structure Selection and Design, Hashing, Asymptotics, Streams, Iterators, Tree Traversals Solution