Session Details

Week 1, Session 2 — Tue Jun 5

Preparation

  1. L: Chapter 1; Sections 2.1 2.2;
    Most of this should be review.
    For rmore background on Analaysis of Algorithms, W: 5.1-5.7
  2. L: Appendix A.
    You do not need to memorize these formulas, but you should be aware of the kinds of formulas in this list, so that you will know when to look at the list.
  3. D: Chapter 0, (on ANGEL). A good treatise on the importance of algorithms.
  4. W: Continue reviewing 230 material as needed.
  5. Slides: If you are not very confidnet about hoe to prove that (ordinary and strong) mathematical induction is a valid proof technique and how to use it to do proofs about numbers and about binary trees, be sure to see the slides that are linked in this day's Resources column.

HW Due

  1. Background Survey on ANGEL. (0) It is important that you do this one early

Topics

  1. Master Theorem review
  2. What is an Algorithm?
  3. Fibonacci Algorithms and their analysis
  4. Integer arithmetic

Outline

  1. [5 min] Student questions
  2. [5 min] Master Theorem Review
  3. [5 min] Brainstorm definition of Algorithm in groups of 3.
  4. [5 min] Collect results
  5. [5 min] Session --> Day of week algorithm
  6. [25 min] Fibonacci Algorithms
  7. [10 min] didn't get to it

Resources

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

  6. If you are not comfortable with why mathematical induction works and how to use it:

  7. VIDEO: How (Not) to Do an Induction Proof

Quiz Solution

  1. In-class quiz

HW Assigned

  1. HW 1