|
Hour |
Date |
Topic and/or Event |
Readings (mostly from Sedgewick & Wayne) |
Code Examples, Homeworks, & Tests |
Notes |
|
0 |
Overview of Course & Course Policies |
Syllabus | Lab 0: Introduction to Dr. Java | ||
|
1 |
Motivational Lecture: Two algorithms for searching an array---algorithm, implementation, and analysis. | Section 1.1 if you need to review Java | ArraySearch, BinarySearch, BinarySearchRecursive | ||
|
2 |
Structure of Java Programs: packages, access modifiers, static vs dynamic instances of classes | Notes on Java Program Structure | HW 01 | ||
|
3 |
Abstract Data Types | 1.2 up to page 91 | |||
|
4 |
Bags, Stacks, and Queues (array implementations) | 1.2 up to p.133 | |||
|
5 |
Generic types | 1.3 up to p.141 | |||
|
6 |
Iterators | Rest of 1.3 | |||
|
7 |
Introduction to Linked Lists; | ||||
|
8 |
Iterative algorithms for Linked Lists | Handout: Linked List Algorithms | HW 02 | ||
|
9 |
Recursion and stacks | ||||
|
10 |
Recursive algorithms on LLs | Lab 2: File I/O and Comparable interface | |||
|
11 |
Analysis of Algorithms: Motivation and basic models | ||||
|
12 |
Analysis of Algorithms: O(), Theta(), and ~(); Growth Rate Classification and complexity theory | 1.4 up to p.188 | |||
|
13 |
Sorting: Basic notions, elementary sorts | ||||
|
14 |
Top-down Mergesort | Ch.2 up to p.2269 | |||
|
15 |
Quicksort | Ch. 2.2 | |||
16 |
Priority Queues and Heapsort | HW 03 | |||
17 |
Big-Omega notation and lower-bound for sorting problem | ||||
18 |
T 7/19 | Searching: Symbol Tables | Lab 3: Random numbers | ||
19 |
Binary Search Trees: Basic notions, search, insert | Ch.3 up to 423 | |||
20 |
W 7/20 | BSTs: Delete, Tree traversals | Handout on Binary Tree Algorithms | ||
21 |
Ch.3.3 | ||||
22 |
Review and Practice Midterm | ||||
23 |
Practice Midterm | ||||
24 |
Midterm Exam | HW 04 | |||
25 |
|||||
26 |
Balanced BSTs: basic notions about tree structure and balance, worst case, average case trees, 2-3 Trees | Ch. 3.3, pp.424-434 | Lab 4: Exceptions and inheritance | ||
27 |
B-trees, Red-Black Trees | ||||
30 |
Priority Qs, Heaps, heapsort | Ch. 2.4 | |||
31 |
Hashing: Basic notions, Perfect Hashing | ||||
32 |
Hash functions | Ch. 3.4 | |||
33 |
Hashing with Separate Chaining, Linear Probing | ||||
34 |
Variations on Linear Probing, performance of hashing | ||||
35 |
Graphs: Basic notions, applications, representations | Ch. 4.1, pp.5180529 | HW 05 -- Concordance | ||
36 |
Graphs: Depth-first search, connected components, breadth-first | pp.530-545, Handout on graph algorithms | Lab 5: Hashing | ||
37 |
Digraphs and DAGs: Topological sort and cycle detection | Ch. 4.2, pp.566-583 | |||
38 |
Digraphs: Minimum Spanning Trees | Ch. 4.3, pp.604-607 | |||
39 |
Digraphs: Shortest path algorithms, Dijkstra's Algorithm | Ch. 4.4, pp.638-654 | |||
40 |
Dijkstra's Algorithm concluded; State-space Graphs, state-space search, | ||||
41 |
Heuristic search, best-first search | ||||
42 |
Min-max Trees, game trees | ||||
43 |
Search in game trees | HW 06 -- Game | |||
44 |
Graphics Programming | Handout | Lab 6: Introduction to HW 6 | ||
45 |
|||||
46 |
Swing | ||||
47 |
|||||
48 |
Final Exam |