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 sorting-related 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: NP-completeness concepts
  Material on NP-completeness (Section 17.2)
  Class notes.

• April 16-20: Classes for this week are cancelled.

• Monday, April 23: NP-completeness proofs
  Material on NP-completeness (Section 17.2)
  Class notes.
• Tuesday, April 24: Homework 12 due at 11pm
• Monday, April 23: Coping with NP-completeness
  Material on NP-completeness (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:25-5:25pm.

Go to the CS4104 Homepage.