# 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
• 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)
• Week 3: Search
• Tuesday, September 7: Fibonacci Analysis; the Search problem
Today's Class notes (Slides 63-72)
• Wednesday, September 8: Homework 2 due
• Thursday, September 9: Linear search; unsorted search lower bound; jump seach
Today's Class notes (Slides 73-87)
• Week 4: Search (continued)
• Tuesday, September 14: Binary search
Today's Class notes (Slides 88-100)
• 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.
• 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)
• 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)
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)
• 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
• 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)
• Week 9: Dynamic Programming; Reductions
• Tuesday, October 19: Dynamic Programming
Today's Class notes (Slides 228-238)
• Wednesday, October 20:
Homework 8 due
• Thursday, October 21: Midterm Review
• Week 10: Midterm 2; Reductions
• Tuesday, October 26: Midterm 2
• Thursday, October 28: Discuss midterm results; Reductions
Today's Class notes (Slides 239-251)