| Date |
Lecture |
Topics |
Reading |
Comments |
| May 1 |
Introduction
|
Introduction, Java Basics Primer |
Ch 1 |
| May 8 |
OOP
|
Object-Oriented Programming in Java, Abstract Classes, Interfaces, Generics |
Ch 2 |
| May 15 |
Arrays & Linked Lists
|
Arrays and Linked Lists, Doubly-Linked Lists, Circular Lists |
Ch 3 |
| May 22 |
|
|
| May 29 |
Analysis of Algorithms
|
Analysis of Algorithms: Time Complexity, Correctness, Loop Invariants |
Ch 4
Broken Binary Search in Java (2006) |
| June 5 |
Recursion (minor updates June 12)
|
Recursion
|
Ch 5 |
Assignment 1 is posted |
| June 12 |
Stacks and Queues
Stacks and Queues 2 Slides by R. Sedgewick
|
Stacks and Queues.
|
Ch 6
Bags, Queues, and Stacks (Book chapter by R. Sedgewick) |
| June 19 |
Lists
|
Lists, Iterators, Java Collections
|
Ch 7 |
Midterm exam
Assignment 1 due |
| June 26 |
Trees
Priority Queues
|
Intro to 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.
|
Assignment 1 model solution sketch (ListTester2 is to aid grading) |
| July 3 (no class) |
|
|
| July 10 |
Binary Search Trees
Maps (minor updates July 31)
|
Search Trees (BSTs, AVL trees...)
Maps and Dictionaries: Hash Tables, Skip Lists, Sets and Multisets
|
Ch 11
Ch 10
Symbol Tables by R. S.
Binary Search Trees by R. S.
BST demo by R. S.
Balanced BSTs by R. S.
2-3 Trees by R. S.
RB Trees demo by R. S.
Hash Tables by R. S.
|
| July 17, 24 |
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.
|
Assignment 2 due Thursday, July 20 |
| July 24, 31 |
Graphs
|
Graphs
|
Ch 14
R. Sedgewick's notes and demos (Ch 4) |
Assignment 3 posted, due July 31.
Midterm solutions |
| Extra (not on the final) |
Text processing
|
Text Processing: Pattern Matching, Tries
|
Ch 13 |
