Session Details

Week 1, Session 3 — Thu Jun 7

Preparation

  1. D: Sections 1.1 and 1.2, basic numerical algorithms.
  2. L: 2.3 This is a review of using summations in algorithm analysis. If you are not confident about this after 230, read this section very carefully.
  3. L: Appendix B (solution techniques for recurrence relations). Most should be review of 230/375.
  4. W 7.5.3 (not optional) This proof of the Master Theorem is a little bit simpler than Levitin's; knowing Weiss's level of detail of the proof is sufficient for this course (under "Reading Materials" on ANGEL)
  5. L: 2.4 Review of analysis of recursive algorithms.
  6. Dasgupta Chapter 1, under "Reading Materials" on ANGEL, pages 1-15
  7. W 7.4-7.4.3 A slightly different approach to some of the matrerial that Dasgupta discusses. (on ANGEL)
  8. L: 2.5-2.7 Only 2.7 should be new, and it is not technical. W: 7.3.4, 5.7, 5.8 have similar material.
  9. CACM interview with Donald Knuth, the most famous (and perhaps most quirky) person in the field of Algorithms.
    (July-August 2008)

HW Due

  1. <Summer:Number in parentheses is the number of grace days allowed for this assignment.
    Details of how grace days work are in the syllabus.
  2. HW 1 (7)
  3. In case you don't have the book yet,
    HW01 textbook problems and hints

Topics

  1. Quick review of big-Oh and its cousins
  2. Fibonacci numbers via Matrix multiplication
  3. Analyzing Addition
  4. Algorithms for multiplication

Outline

  1. [ 3 min] Announcements
  2. [20 min] Asymptotics review (big of, etc)
  3. [ 7 min] Fibonacci summary
  4. [ 5 min] Analyzing Addition
  5. [ 5 min] Multiplication the usual way
  6. [ 5 min] Multiplication a la France
  7. [ 5 min] Divide and Conquer
  8. [ 5 min] Multiplication a la Gauss

Resources

  1. Slides
  2. Summer: Instructor notes for Slides
  3. In-class code
  4. Summer: In-class Quiz 03
  5. Summer: ICQ solution

HW Assigned