CS4104 Data and Algorithm Analysis
Calendar and Coursenotes: Fall 2010
This page will show what we cover each day, including the course notes covered in class as they are presented on the screen. Look here to see all coursenotes in a more condensed form (along with my supplemental comments) up to this point.
Reading assignments are also posted for each week. You can find the textbook here. 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.
 Week 1: Introduction

Tuesday, August 24: Course intro and intro to problem solving.
Handouts: Syllabus, prereq forms, force add forms (as needed)
Reading Assignment: Notes on problem solving.
Reading Assignment: Read the article How Pair Programming Really Works
Homework: Find your partner for Homework 1, and start working on it.
Today's Class notes (Slides 113).

Thursday, August 26: Analysis Overview
Today's Class notes (Slides 1430).

Tuesday, August 24: Course intro and intro to problem solving.
 Week 2: Analysis overview

Tuesday, August 31: Analysis Overview continued
Today's Class notes (Slides 3142)
Reading Assignment: Chapter 15 intro and Section 15.1 (pages 505508) 
Wednesday, September 1: Homework 1 due

Thursday, September 2: Factorial growth and solving sums
Today's Class notes (Slides 4362)
Reading Assignment: Section 14.1

Tuesday, August 31: Analysis Overview continued
 Week 3: Search

Tuesday, September 7: Fibonacci Analysis; the Search problem
Today's Class notes (Slides 6372)
Reading Assignment: Section 14.2 
Wednesday, September 8: Homework 2 due

Thursday, September 9: Linear search; unsorted search lower bound;
jump seach
Today's Class notes (Slides 7387)

Tuesday, September 7: Fibonacci Analysis; the Search problem
 Week 4: Search (continued)

Tuesday, September 14: Binary search
Today's Class notes (Slides 88100)
Reading Assignment: Section 9.1 
Wednesday, September 15: Homework 3 due

Thursday, September 16: QBS, hashing, skip lists
Today's Class notes (Slides 101115)
Reading Assignment: Section 9.9.4, Section 16.3.1.

Tuesday, September 14: Binary search
 Week 5: Selection problems

Tuesday, September 21: Finding the maximum, finding the second best
Today's Class notes (Slides 116135)
Reading Assignment: Sections 15.3  15.4 
Wednesday, September 22: Homework 4 due

Thursday, September 23: Adversary proofs; finding min and max; state
space lower bounds proof
Today's Class notes (Slides 136152)
Reading Assignment: Section 15.5

Tuesday, September 21: Finding the maximum, finding the second best
 Week 6: Selection problems (continued)
 Tuesday, September 28: Midterm I

Thursday, September 30: Go over midterm; Finding the median
Today's Class notes (Slides 153164)
Reading Assignment: Section 15.6
Homework 5 due
 Week 7: Probabilistic algorithms; sorting

Tuesday, October 5: Probabilistic Algorithms; analysis for some
sorting algorithms
Today's Class notes (Slides 165183)
Reading Assignment: Section 16.3

Wednesday, October 6: Homework 6 due

Thursday, October 7: Optimal sorts; number problems: exponentiation
Today's Class notes (Slides 184195)
Reading Assignment: Sections 15.7, 16.4 intro and 16.4.1

Tuesday, October 5: Probabilistic Algorithms; analysis for some
sorting algorithms
 Week 8: Number problems

Tuesday, October 12: Number problems: LCF, matrix multiply, master theorem
Today's Class notes (Slides 196211)
Reading Assignment: Sections 16.4.2, 16.4.3, 14.2.3 
Wednesday, October 13: Homework 7 due

Thursday, October 14: Number problems: Random number generators, DFT algorithm
Today's Class notes (Slides 212227)
Reading Assignment: Sections 16.4.5

Tuesday, October 12: Number problems: LCF, matrix multiply, master theorem
 Week 9: Dynamic Programming; Reductions

Tuesday, October 19: Dynamic Programming
Today's Class notes (Slides 228238)
Reading Assignment: Section 16.2  Wednesday, October 20:
Homework 8 due

Thursday, October 21: Midterm Review

Tuesday, October 19: Dynamic Programming
 Week 10: Midterm 2; Reductions

Tuesday, October 26: Midterm 2

Thursday, October 28: Discuss midterm results; Reductions
Today's Class notes (Slides 239251)
Reading Assignment: Section 17.1
Homework 9 due

Tuesday, October 26: Midterm 2
 Week 11: NPcompletness

Tuesday, November 2: NPcompletness
Today's Class notes (Slides 242260)
 Wednesday, November 3:
Homework 10 due

Thursday, November 4: NPcompletness
Today's Class notes (Slides 261272)

Tuesday, November 2: NPcompletness
 Week 12: Coping with NPcomplete problems; Computability

Tuesday, November 9: Coping with NPcomplete problems
Today's Class notes (Slides 273289)
Reading Assignment: Section 17.2
 Wednesday, November 10:
Homework 11 due

Thursday, November 11: Computability
Today's Class notes (Slides 290299)
Reading Assignment: Section 17.3
 All lecture slides to this point, with side notes

Tuesday, November 9: Coping with NPcomplete problems
 Week 13: Parallel Programming

Tuesday, November 16: Parallel Programming
Today's Class notes (Slides 300317)
 Wednesday, November 17:
Homework 12 due

Thursday, November 18: Parallel Programming
Today's Class notes (Slides 318335)

Tuesday, November 16: Parallel Programming
 Week 14: Turing Machines

Tuesday, November 30: Turing Machines
Today's Class notes (Slides 336349)
If you would like to try out a Turing machine simulator, I recommend the JFLAP software. 
Thursday, December 2: Turing Machines (Last day of class)
Today's Class notes (Slides 349350)
 All lecture slides for the semester, with side notes

Tuesday, November 30: Turing Machines
 Week 15:

Tuesday, December 7: CLASS CANCELLED
Homework 13 due
 Tuesday, December 14: Final exam, 10:0512:05pm in the regular classroom.
Go to the CS4104 Homepage.