| Wk |
Day |
Date |
Topic | Resources | Events |
|
| 1 | Tue | Aug 26 | Introduction to the Course
Algorithm Analysis |
IDAA 1.1-1.2
JEU Ch 34 (Compiling C++)
JEU Appendix G (Make)
JEU 13-17 (editors--pick one) | |
|
|
| Thu | Aug 28 | Algorithms and Problem Solving Fundamental Data Structures | IDAA 1.3-1.4 Data Structures Notes
Data Structures Examples | |
|
| 2 | Tue | Sep 02 | Graphs and Trees
Induction Proofs | Graphs and Trees Notes
Induction Proofs
Induction
Tutorial | |
|
|
| Thu | Sep 04 | Induction Proofs
Analysis of Algorithms
Complexity Classes | IDAA 2.1-2.2
Algorithm Analysis Notes
Asymptotic Notation Notes
| Pretest Due |
|
| 3 | Tue | Sep 09 | Asymptotic Notation Proofs
Complexity of Algorithms | Proving Bounds Examples
IDAA 2.3-2.4
| |
|
|
| Thu | Sep 11 | Analysis of Recursive Algorithms
Recurrence Relations
|
IDAA 2.5
IDAA Appendix B
Algorithms and Recurrences Examples
Recurrence Relations Notes
Solving Recurrence Relations Examples | |
|
| 4 | Tue | Sep 16 | Recurrence Relations
Brute Force:
Sorting (Selection and Bubble)
Searching (Sequential) |
IDAA 3.1-3.2 | |
|
|
| Thu | Sep 18 | Brute Force:
String Matching
Closest Pair
Convex Hull
Exhaustive Search |
IDAA 3.3-3.4 | HW 1 due
Quiz 1 |
|
| 5 | Tue | Sep 23 | Divide-and-Conquer:
Sorting (Quick and Merge)
Searching (Binary)
Strassen's Algorithm
|
IDAA 4.1-4.3, 4.5
Sorting Notes
| |
|
|
| Thu | Sep 25 | Divide-and-Conquer:
Binary Tree Traversal
Closest Pair
Convex Hull |
IDAA 4.4, 4.6
A RPN Calculator | |
|
| 6 | Tue | Sep 30 | Decrease-and-Conquer:
Sorting (Insertion, Topological)
Searching (BFS, DFS) |
IDAA 5.1-5.3
BFS and DFS Notes | HW 2 due |
|
|
| Thu | Oct 02 | Decrease-and-Conquer:
Constant Factor
Variable Size |
IDAA 5.5-5.6 | Quiz 2 |
|
| 7 | Tue | Oct 07 | Transform-and-Conquer:
Sorting (pre sorting)
Searching (Trees)
|
IDAA 6.1,6.3
| |
|
|
| Thu | Oct 09 | Transform-and-Conquer:
Heaps and Heapsort
Horner's Rule
Binary Exponentiation
|
IDAA 6.4-6.5
Sorting Notes | |
|
| 8 | Tue | Oct 14 | Space and Time Tradeoffs
Sorting (Counting)
Hashing |
IDAA 7.1,7.3
Hashing Notes | HW 3 due |
|
|
| Thu | Oct 16 | Transform-and-Conquer
Binary Exponentiation
Reductions
|
IDAA 6.5-6.6 | |
|
| 9 | Tue | Oct 21 | Fall Break | | No Class |
|
|
| Thu | Oct 23 | Space and Time Tradeoffs
B- Trees
Summary |
IDAA 7.4 | Quiz 3 |
|
| 10 | Tue | Oct 28 | Dynamic Programming:
Matrix Chain Multiplication
Knapsack Problem
|
Dynamic Programming Notes
IDAA 8.4 | |
|
|
| Thu | Oct 30 | Dynamic Programming:
Warshall's Algorithm
Floyd's Algorithm
|
IDAA 8.2
Warshall's Algorithm Notes
Floyd's Algorithm Animation | HW 4 due |
|
| 11 | Tue | Nov 04 | Greedy Technique:
Fractional Knapsack
Huffman Encoding |
IDAA 9.4
Greedy Algorithms Notes
| |
|
|
| Thu | Nov 06 | Greedy Technique:
Prim's Algorithm
Kruskal's Algorithm |
IDAA 9.1-9.2
Minimum Spanning Trees Notes
Spanning Tree Animations | |
|
| 12 | Tue | Nov 11 | P, NP, NP-Complete |
IDAA 10.3
P, NP, NP-Complete Notes | |
|
|
| Thu | Nov 13 | Approximation Algorithms for NP-Hard Problems |
IDAA 11.3 | Quiz 4 |
|
| 13 | Tue | Nov 18 | Communications | Ask Mary Garbacz | Communications |
|
|
| Thu | Nov 20 | Languages
Grammars
Regular Expressions
Finite State Machines | Languages, Grammars, and Regular Expressions Notes
Finite State Machines Notes | HW 5 due |
|
| 14 | Tue | Nov 25 | Skip Day | None | No Class |
|
|
| Thu | Nov 27 | Thanksgiving Break | Turkey
Stuffing | No Class |
|
| 15 | Tue | Dec 02 | Finite State Machines
Finite State Automata
| Finite State Machines Notes
FDA Applet
| |
|
|
| Thu | Dec 04 | Halting Problem
Turing Machines
Distributed Algorithms
| Halting Problem Notes
Turing Machine Simulator
Introduction to Turing Machines
Sample Program
SETI@home
Distributed.net | HW 6 due |
|
| 16 | Tue | Dec 09 | Review | | |
|
|
| Thu | Dec 11 | Review | | Project Due |
|
| Ex | Mon | Dec 15 | | | Final Exam
3:30-5:30pm
Ferguson 217 |