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 1-13).
-
Thursday, August 26: Analysis Overview
Today's Class notes (Slides 14-30).
-
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 31-42)
Reading Assignment: Chapter 15 intro and Section 15.1 (pages 505-508) -
Wednesday, September 1: Homework 1 due
-
Thursday, September 2: Factorial growth and solving sums
Today's Class notes (Slides 43-62)
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 63-72)
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 73-87)
-
Tuesday, September 7: Fibonacci Analysis; the Search problem
- Week 4: Search (continued)
-
Tuesday, September 14: Binary search
Today's Class notes (Slides 88-100)
Reading Assignment: Section 9.1 -
Wednesday, September 15: Homework 3 due
-
Thursday, September 16: QBS, hashing, skip lists
Today's Class notes (Slides 101-115)
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 116-135)
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 136-152)
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 153-164)
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 165-183)
Reading Assignment: Section 16.3
-
Wednesday, October 6: Homework 6 due
-
Thursday, October 7: Optimal sorts; number problems: exponentiation
Today's Class notes (Slides 184-195)
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 196-211)
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 212-227)
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 228-238)
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 239-251)
Reading Assignment: Section 17.1
Homework 9 due
-
Tuesday, October 26: Midterm 2
- Week 11: NP-completness
-
Tuesday, November 2: NP-completness
Today's Class notes (Slides 242-260)
- Wednesday, November 3:
Homework 10 due
-
Thursday, November 4: NP-completness
Today's Class notes (Slides 261-272)
-
Tuesday, November 2: NP-completness
- Week 12: Coping with NP-complete problems; Computability
-
Tuesday, November 9: Coping with NP-complete problems
Today's Class notes (Slides 273-289)
Reading Assignment: Section 17.2
- Wednesday, November 10:
Homework 11 due
-
Thursday, November 11: Computability
Today's Class notes (Slides 290-299)
Reading Assignment: Section 17.3
- All lecture slides to this point, with side notes
-
Tuesday, November 9: Coping with NP-complete problems
- Week 13: Parallel Programming
-
Tuesday, November 16: Parallel Programming
Today's Class notes (Slides 300-317)
- Wednesday, November 17:
Homework 12 due
-
Thursday, November 18: Parallel Programming
Today's Class notes (Slides 318-335)
-
Tuesday, November 16: Parallel Programming
- Week 14: Turing Machines
-
Tuesday, November 30: Turing Machines
Today's Class notes (Slides 336-349)
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 349-350)
- 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:05-12:05pm in the regular classroom.
Go to the CS4104 Homepage.