Schedule

This class meets every Monday, Wednesday, and Friday from 12:00-12:50 PM, except on University holidays or if I cancel class. All dates in the following schedule are tentative, except those fixed by the University. I expect you to have read the reading assignments before the lecture that deals with that topic; this way I can concentrate my time on answering questions and clarifying subtle or difficult points in the textbook, rather than on reading the textbook to you, which will bore both of us. Please read ahead!

Date	Assignment	Reading	Subject
Jan. 22			Administrivia, syllabus, what's an algorithm, what's efficiency?
Jan. 24		BP ch. 1	History of algorithms, recursion, problem reduction
Jan. 26	HW1	BP ch. 2	Review of basic data structures
Jan. 29		BP ch. 2	Review of basic data structures
Jan. 31		BP ch. 2	Review of basic data structures
Feb. 2	Last day to add courses
Feb. 2		BP ch. 2	Review of basic data structures (linked lists)
Feb. 5	HW1 due	BP ch. 2	Review of basic data structures (linked lists)
Feb. 7	HW2	BP ch. 2	Review of basic data structures (linked lists)
Feb. 9		BP ch. 2 STILL!	Miscellaneous; tail-recursion
Feb. 12		BP ch. 3-3.4	Analyzing algorithms
Feb. 14		BP ch. 3.5-3.8	Lower bounds, asymptotic growth rates
Feb. 16	Last day to drop courses
Feb. 16		BP ch. 4-4.4	Lower bounds for sorting; Shell sort
Feb. 19		BP ch. 4-4.4	Discuss homework 1; Merge sort
Feb. 21	HW1a assigned	BP ch. 4-4.4	Quicksort and Treesort
Feb. 23	HW2 due; HW3	BP ch. 4-4.4	Quicksort and Treesort, cont'd.
Feb. 26		BP ch. 4.5	Heap sorting
Feb. 28		BP ch. 4.6-4.9	More sorting algorithms
Mar. 2		BP ch. 5-5.2	Parallel algorithms
Mar. 5	Snow closing
Mar. 7	HW3 due	BP ch. 5.3-5.5	Examples and pseudocode for parallel algorithms
Mar. 9	HW1a due	BP ch. 5.6-5.8	Parallel algorithms and efficiency
Mar. 12-17	Spring Break
Mar. 19	I may be out of town
Mar. 21		BP ch. 6-6.4	Sorting in parallel
Mar. 23	Last day to withdraw from courses
Mar. 23	I have a doctor's appointment
Mar. 26		BP ch. 6-6.4	Sorting in parallel
Mar. 28			Proof techniques
Mar. 30		BP ch. 7-7.3	Mathematical induction proofs
Apr. 2	HW4	BP ch. 7.4-7.5	Converting recurrence relations to closed form
Apr. 4			Converting recurrence relations to closed form
Apr. 6			Converting recurrence relations to closed form
Apr. 9	Passover; no classes
Apr. 10	Make-up day; you're not required to be there, but I will, talking about recurrence relations.
Apr. 11		BP ch. 8-8.1	Graphs and digraphs
Apr. 16	HW4 due	BP ch. 8-8.1	Graphs and digraphs
Apr. 18		BP ch. 8.2-8.3	Searching and traversing graphs
Apr. 20		BP ch. 8.4-8.5	More common graph algorithms
Apr. 23		BP ch. 12-12.2	Greedy algorithms
Apr. 25	HW5	BP ch. 12.3-12.4	More examples of greedy algorithms
Apr. 27		BP ch. 12.5-12.6	Greedy graph algorithms
Apr. 30		BP ch. 13-13.5	Divide-and-conquer algorithms
May 2		BP ch. 14-14.3	Memoization and dynamic programming
May 4		BP ch. 14.4-14.7	Examples of dynamic programming
May 7		BP ch. 15	Backtracking algorithms
May 9	HW6 due	BP ch. 20-20.8	P and NP, approximation, and parallel complexity
May 11			catch up and review for final exam
May 16	10:30 AM-12:30 PM, final exam

Last modification: