Schedule for weeks 1 through 17

Wk	Day	Date	Topic	Resources	Events

1	Mon	Aug 25	Introduction to the Course

	Wed	Aug 27	Algorithms and Problem Solving	IDAA 1.1-1.3

	Fri	Aug 29	Fundamental Data Structures	IDAA 1.4 Data Structures Notes Graphs and Trees Notes Data Structures Examples

	Fri		Introduction to Recitation Discuss Pretest Questions

2	Mon	Sep 01	Labor Day		No Class

	Wed	Sep 03	Analysis of Algorithms Complexity Classes	IDAA 2.1-2.2 Algorithm Analysis Notes Asymptotic Notation Notes

	Fri	Sep 05	Complexity of Algorithms	IDAA 2.3 Proving Bounds Examples	Pretest Due

	Fri		Discuss Pretest Questions

3	Mon	Sep 08	Analysis of Recursive Algorithms Recurrence Relations	IDAA 2.4-2.5 IDAA Appendix B Algorithms and Recurrences Examples Recurrence Relations Notes

	Wed	Sep 10	Solving Recurrence Relations	IDAA Appendix B Solving Recurrence Relations Examples

	Fri	Sep 12	Wrap up Algorithm Analysis

	Fri				WS 1

4	Mon	Sep 15	Brute Force: Sorting (Selection and Bubble) Searching (Sequential)	IDAA 3.1-3.2

	Wed	Sep 17	Brute Force: Convex Hull, Closest Pair	IDAA 3.3	HW 1 due

	Fri	Sep 19	Brute Force: Exhaustive Search	IDAA 3.4

	Fri				Quiz 1

5	Mon	Sep 22	Divide-and-Conquer: Sorting (Quick and Merge) Searching (Binary)	IDAA 4.1-4.3 Sorting Notes

	Wed	Sep 24	Divide-and-Conquer: Binary Tree Traversal	IDAA 4.4

	Fri	Sep 26	Divide-and-Conquer: Strassen's algorithm and Closest Pair	IDAA 4.5-4.6

	Fri				WS 2

6	Mon	Sep 29	Decrease-and-Conquer: Sorting (Insertion) Searching (BFS)	IDAA 5.1-5.2 BFS and DFS Notes	HW 2 due

	Wed	Oct 01	Decrease-and-Conquer: Searching (DFS) Sorting (Topological)	IDAA 5.3

	Fri	Oct 03	Decrease-and-Conquer: Constant Factor	IDAA 5.5

	Fri				WS 3

7	Mon	Oct 06	Decrease-and-Conquer: Variable Size	IDAA 5.6

	Wed	Oct 08	Transform-and-Conquer: Sorting (pre sorting) Searching (Trees)	IDAA 6.1,6.3

	Fri	Oct 10	Transform-and-Conquer: Heaps and Heapsort	IDAA 6.4 Sorting Notes	HW 3 due

	Fri				Quiz 2

8	Mon	Oct 13	Transform-and-Conquer: Horner's Rule Binary Exponentiation	IDAA 6.5

	Wed	Oct 15	Transform-and-Conquer: Reductions	IDAA 6.6

	Fri	Oct 17	Everything		Review for Midterm

	Fri				WS 4

9	Mon	Oct 20	Fall Break		No Class

	Wed	Oct 22	Everything	IDAA 1-6	Midterm Exam

	Fri	Oct 24	Space-Time Tradeoffs: Counting Sort Radix Sort	IDAA 7.1 Sorting Notes

	Fri		Fall Break		No Class

10	Mon	Oct 27	Space and Time Tradeoffs: Hashing	IDAA 7.3 Hashing Notes

	Wed	Oct 29	Space and Time Tradeoffs: B-Trees	IDAA 7.4

	Fri	Oct 31

	Fri				WS 5

11	Mon	Nov 03	Dynamic Programming: Matrix Chain Multiplication Knapsack Problem	Dynamic Programming Notes IDAA 8.4	HW 4 due

	Wed	Nov 05	Dynamic Programming: Warshall's Algorithm	IDAA 8.2 Warshall's Algorithm Notes

	Fri	Nov 07	Dynamic Programming: Floyd's Algorithm	Floyd's Algorithm Animation

	Fri				WS 6

12	Mon	Nov 10	Greedy Technique: Fractional Knapsack Huffman Encoding	IDAA 9.4 Greedy Algorithms Notes

	Wed	Nov 12	Greedy Technique: Prim's Algorithm	IDAA 9.1 Minimum Spanning Trees Notes Spanning Tree Animations

	Fri	Nov 14	Greedy Technique: Kruskal's Algorithm	IDAA 9.2

	Fri				Quiz 3

13	Mon	Nov 17	P and NP	IDAA 10.3 P, NP, NP-Complete Notes

	Wed	Nov 19	NP-Complete	IDAA 10.3 P, NP, NP-Complete Notes	HW 5 due

	Fri	Nov 21	Languages Grammars Regular Expressions	Languages, Grammars, and Regular Expressions Notes

	Fri				WS 7

14	Mon	Nov 24	Finish Grammars Finite State Machines	Finite State Machines Notes

	Wed	Nov 26	Thanksgiving Break	Stuffing	No Class

	Fri	Nov 28	Thanksgiving Break	Turkey	No Class

	Fri		Skip Day		No Class

15	Mon	Dec 01	Finite State Automata	Finite State Machines Notes FDA Applet

	Wed	Dec 03	Halting problem	Halting Problem Notes

	Fri	Dec 05	Turing Machines Distributed Algorithms	Introduction to Turing Machines Turing Machine Simulator Sample Program SETI@home Distributed.net

	Fri				Quiz 4

16	Mon	Dec 08	Distributed/Parallel Algorithms		HW 6 due

	Wed	Dec 10	Review for final

	Fri	Dec 12	Review for final

	Fri				WS 8

Ex	Mon	Dec 15	Final Exam 7:30am		Final Exam