CS4104 Spring, 2007: Calendar and Course Notes
This page will show what we cover each day, including the course notes
covered in class. The full course notes covered during the semester so
far can always be found here.
Reading assignments are also posted for each week. The intention is
that you will have finished the reading for that week by the end of
the week (that is, typically you would be expected to read material
after the associated lecture). However, some folks like to read it
before the lecture, so I will try to get it up by the beginning of the
week if I can. Note that reading for the week will often be relevent
to the homework due the following Tuesday.

Wednesday, January 17: Course intro and intro to problem solving.
Handouts: Syllabus, prereq forms, force add forms (as needed), problem
solving chapter from Whimbey & Lochhead.
Homework and reading assignments:
Read these notes on problem solving and also
the chapter from Whimbey & Lochhead that I provided in class on
problem solving.
Find your partner for Homework 1, and start working on it.
Class notes.

Monday, January 22: Course overview (1): Algorithm efficiency, cost
models, catagories of hard problems, TOH.
Class notes.

Tuesday, January 23: Homework 1 due at 11:00pm

Wednesday, January 24: Course overview (2): Algorithm upper bounds,
analysis of TOH, recurrences and proof by induction, growth rates,
lower bounds of problems, the "problem solving algorithm".
Reading assignment: Material on lower bounds.
Class notes.

Monday, January 29: Recurrences and Summations
Reading assignment: Material on
recurrences and summations.
Class notes.

Tuesday, January 30: Homework 2 due at 11:00pm

Wednesday, January 31: Recurrences and Summations (cont)
Class notes.

Monday, February 5: Searching unsorted lists
Reading assignment: Material on
recurrences and summations.
Reading assignment:
Material on search:
Intro and Section 9.1 (unsorted lists).
Class notes.

Tuesday, February 6: Homework 3 due at 11:00pm

Wednesday, February 7: Searching sorted lists
Material on search:
Section 9.1 (sorted lists).
Class notes.

Monday, February 12: More on searching
Material on search:
Section 9.1 (quadratic search) and Section 9.4
(hashing  read the part on analysis).
Also, Skiplists (Section 16.3.1)
Class notes.

Tuesday, February 13: Homework 4 due at 11:00pm

Wednesday, February 14: Selection, findmax
Material on selection and findmax:
Section 15.3.
Class notes.

Monday, February 19: Midterm 1

Tuesday, February 20: Homework 5 due at 11:00pm

Wednesday, February 21: Second biggest, adversary arguments
Material on relations: Section 2.1.
Material on second biggest and adversary arguments:
Section 15.4.
Class notes.

Monday, February 26: Find min and max, state space lower bound argument
Material on min/max and state space arguments:
Section 15.5.
Class notes.

Tuesday, February 27: Homework 6 due at 11:00pm

Wednesday, February 28: Find the median
Material on finding the median:
Section 15.6.
Class notes.

Monday, March 12: Probabilisitic algorithms, some sortingrelated
analysis topics
Quicksort analysis: Section 14.2.4
Class notes.

Tuesday, March 13: Homework 7 due at 11pm

Wednesday, March 14: Optimal sorting; Number problems
Material on optimal sorting:
Section 15.7.
Class notes.

Monday, March 19: Number problems: exponentiation, LCF, Strassen's algorithm
Material on number problems (Section 16.4)
Class notes.

Tuesday, March 20: Homework 8 due at 11pm

Wednesday, March 21: Number problems: master equation, primes, random numbers
Material on Random numbers (Section 16.4.4)
Material on the master equation (Section 14.2.3)
Class notes.

Monday, March 26: The midterm that wasn't
Material to be covered:
Search algorithms.
Selection problems
Related lower bounds proof techniques (adversary arguments, state
space arguments).
Techniques for solving recurrences.

Tuesday, March 27: Homework 9 due at 11pm

Wednesday, March 28: Midterm 2

Monday, April 2: Number problems: Multiplication/FFT
Material on FFT (Section 16.4.5)
Class notes.

Tuesday, April 3: Homework 10 due at 11pm

Wednesday, April 4: Dynamic Programming
Material on Dynamic Programming (Section 16.2)
Class notes.

Monday, April 9: Reductions
Material on Reductions (Section 17.1)
Class notes.

Tuesday, April 10: Homework 11 due at 11pm

Wednesday, April 11: NPcompleteness concepts
Material on NPcompleteness (Section 17.2)
Class notes.

April 1620: Classes for this week are cancelled.

Monday, April 23: NPcompleteness proofs
Material on NPcompleteness (Section 17.2)
Class notes.

Tuesday, April 24: Homework 12 due at 11pm

Monday, April 23: Coping with NPcompleteness
Material on NPcompleteness (Section 17.2)
Class notes.

Monday, April 30: The halting problem
Material on the halting problem (Section 17.3)
Class notes.

Tuesday, May 1: Homework 13 due at 11pm

Wednesday, May 2: Turing Machines
Class notes.

Tuesday, May 8: Final exam, 3:255:25pm.
Go to the CS4104 Homepage.