Session Details

Week 3, Session 10 — Tue Jun 19

Preparation

  1. L: 5.4, L: 5.5 Four very important divide-and-conquer examples:
    integer multiplication, matrix multiplication, closest pair, convex hull.
  2. Sections 5.3-5.4
  3. Wikipedia article on Miller-Rabin test

HW Due

Topics

  1. List some review topics from the textbook
  2. Fermat's Little Theorem: Proof
  3. More Primality testing

Outline

  1. [15 min] Student questions and textbook coverage list
  2. [10 min] Fermat's Little Theorem proof
  3. [20 min] Primality Testing

Resources

  1. Slides
  2. Summer: Instructor notes for Slides
  3. Summer: In-class Quiz
  4. Summer: ICQ Solution

HW Assigned