| Date |
Lecture |
Topics |
Reading |
Comments |
| Jan 7, 9 |
Introduction
|
Introduction, Java Basics Primer |
Ch 1 |
| Jan 14, 16 |
Working with Files
OOP, Generics
|
Working with files
Object-Oriented Programming in Java, Abstract Classes, Interfaces, Generics
|
Ch 2 |
| Jan 21, 23 |
Arrays and Lists
Time Complexity
|
Arrays and Linked Lists, Doubly-Linked Lists
Analysis of Algorithms: Time Complexity |
Ch 3
Ch 4 |
Assignment 1 due |
| Jan 28, 30 |
Correctness and Loop Invariants
|
Analysis of Algorithms: Time Complexity (cont'd),
Correctness, Loop Invariants |
Ch 4
Broken Binary Search in Java (2006) |
Feb 4,
6 (canceled) |
Skip Lists (updated Feb 11)
Recursion
|
Skip lists
Recursion
Stacks and Queues
|
Skip List (Wikipedia)
"A skip list cookbook" by William Pugh
Ch 5
|
|
| Feb 11, 13 |
Stacks and Queues
|
Recursion, Stacks and Queues (from Feb 6 class)
|
Ch 6
Bags, Queues, and Stacks (Book chapter by R. Sedgewick)
|
Assignment 2 due Feb 18 |
| Feb 18, 20 |
Reading Week
Review Questions (Ch 1–6)
|
|
|
| Feb 25, 27 |
List and Interators
|
Lists, Iterators, Java Collections
|
Ch 7
|
Midterm exam Feb 25 |
| Mar 4, 6 |
Trees
Priority Queues
|
Trees
Priority Queues: Heaps, Sorting with Piority Queues
|
Ch 8
Ch 9
Binary Heap demo by R. S.
PQ slides by R. Sedgewick
Heapsort demo by R. S.
|
| Mar 11, 13 |
Binary Seach Trees, AVL trees, 2-4 trees, Red-Black trees (minor update March 18)
|
Search Trees (BSTs, AVL trees...)
|
Ch 11
Binary Search Trees by R. S.
BST demo by R. S.
Balanced BSTs by R. S.
2-3 Trees by R. S.
(LL)RB Trees demo by R. S.
|
|
| Mar 18, 20 |
Sorting and Selection
|
Sorting and Selection: MergeSort and Divide-&-Conquer, QuickSort, Sorting Lower-Bound, Special Linear-Time Sorting, Selection
|
Ch 12
Elementary Sorts by R. S.
MergeSort by R. S.
Merge demo by R. S.
QuickSort by R. S.
QuickSort demo by R. S.
|
| Mar 25, 27 |
Maps, Hash Tables, Sets
Graphs & Union-Find (complete)
|
Maps and Dictionaries: Hash Tables, Sets and Multisets
Graphs
|
Ch 10
Symbol Tables by R. S.
Hash Tables by R. S.
Demo of Linear-Probing Hash Table by R. S.
Ch 14
R. Sedgewick's notes and demos (Ch 4: Graphs)
|
Midterm solutions
|
| Apr 1, 3 |
|
Graphs (continued)
Text Processing: Pattern Matching, Tries
|
Ch 14 (continued)
Demos (continued)
Ch 13
|
Assignment 4 due Apr 3 |
| Apr 5 |
Final exam
|
Topics covered: up to Kruskal's MST (slide 116). Graphs: no code needs to be written; no Bellman-Ford or DAG shortest path algorithms.
No splay trees.
A calculator is allowed, but should not be necessary (one question involves adding two-digit natural numbers).
|
|
