CS 15-251: Great Ideas |
||||||
Fall 2005 |
Lecture/Work Schedule |
|||||
| Week | Date | Day | Lecture | Topic | Available | Due |
| 1 | Aug 29 | M | Recitation 1 | |||
| Aug 30 | T | 1 | Pancakes with a Problem [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk1 [ps
| pdf ]
Course Document [ ps | pdf ] |
||
| Sep 1 | R | 2 | Induction I: One Step at a Time [ ppt
| ps | pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
|||
| 2 | Sep 5 | M | Labor Day - No Recitations! | |||
| Sep 6 | T | 3 | Induction II: Inductive Pictures [ ppt
| ps | pdf ]
Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk2 [ ps
| pdf
| LaTeX ] |
Hwk1 | |
| Sep 8 | R | 4 | Ancient Wisdom: Unary and Binary [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
|||
| 3 | Sep 12 | M | Recitation 2 [ ps | pdf ] Solutions: [ ps | pdf ] Slides: [ ppt ] |
|||
| Sep 13 | T | 5 | Ancient
Wisdom: On Raising a Number to a Power [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk3 [ ps | pdf | LaTeX ] | Hwk2 | |
| Sep 15 | R | 6 |
In-Class Quiz I (10 minutes)
[ Q1
sol ] Counting I: Choice Trees and Correspondences [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk1 Solutions [ps | pdf ] | ||
| 4 | Sep 19 | M | Recitation 3 [ ps | pdf ] Solutions [ ps | pdf ] Slides: [ ppt ] |
|||
| Sep 20 | T | 7 |
Counting II
[ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk4 [ ps | pdf | LaTeX ] | Hwk3 | |
| Sep 22 | R | 8 | Counting III [ ppt
| ps ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk2 Solutions [ps | pdf ] | ||
| 5 | Sep 26 | M | Recitation 4: TEST 1 Practice:[ ps | pdf ] Test (with solutions): [ps | pdf ] |
|||
| Sep 27 | T | 9 | Modular Arithmetic and the RSA Cryptosystem [ ppt
| ps
| pdf] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk5 [ ps | pdf | LaTeX ] | Hwk4 | |
| Sep 29 | R | 10 | One Minute To Learn Programming: Finite Automata [ ppt
| ps
| pdf] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk3 Solutions [ps | pdf ] | ||
| 6 | Oct 3 | M | Recitation 5 [ ps | pdf ] Solutions [ ps | pdf ] Slides: [ ppt ] |
|||
| Oct 4 | T | 11 | The Math
of 1950's Dating: Who Wins the Battle of the Sexes? [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk6 [ps
| pdf | LaTeX]
|
Hwk5 | |
| Oct 6 | R | 12 | In-Class Quiz II (10 minutes)
[ Q2
sol ] Ancient Wisdom: Primes, GCD, and Continued Fractions [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk4 Solutions [ps | pdf ] | ||
| 7 | Oct 10 | M | Recitation 6 [ ps | pdf ] Solutions [ ps | pdf ] |
|||
| Oct 11 | T | 13 | The Golden Ratio, Fibonacci, and Other Recurrences [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk7 [ ps | pdf | LaTeX ] | Hwk6 | |
| Oct 13 | R | 14 | Polynomials, Secret Sharing, and Error-Correction [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] Original File ppt, [ 6-per-pg ps | pdf ] |
Hwk5 Solutions [ps | pdf ] | ||
| 8 | Oct 17 | M | Recitation 7 Notes [ ps | pdf ] | |||
| Oct 18 | T | 15 | Graphs
[ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
Hwk8 [ ps | pdf | LaTeX ] | Hwk7 | |
| Oct 20 | R | 16 | In-Class Quiz III (10 minutes)
[ Q3
sol ] Problem Solving: Where Does The Aha Come From? [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] |
Hwk6 Solutions [ps | pdf ] | ||
| Mid Semester Break | ||||||
| 9 | Oct 24 | M | Recitation 8 [ ps | pdf ] | |||
| Oct 25 | T | 17 | On Time Versus Input Size [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
|||
| Oct 27 | R | 18 | Grade School Revisited: How To Add and Multiply [ ppt
| ps
| pdf] Printer-friendly: [ ps | pdf ] |
Hwk7 Solutions [ps | pdf ] | ||
| 10 | Oct 31 | M | Recitation 9: TEST 2 (with solutions) [ ps
| pdf ] Practice test (with solutions):[ ps | pdf ] |
|||
| Nov 1 | T | 19 | Probability
I: Counting in Terms of Proportions [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] |
Hwk9 [ ps | pdf | LaTeX ] | Hwk8 | |
| Nov 3 | R | 20 | Probability II: Random Variables and Great Expectations! [
ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
|||
| 11 | Nov 7 | M | Recitation 10 Notes [ ps | pdf ] | |||
| Nov 8 | T | 21 | Probability III: The Probabilistic Method [ ppt
| ps
| pdf] Printer-friendly: [ ps | pdf ] |
Hwk10 [ ps | pdf | LaTeX ] | Hwk9 | |
| Nov 10 | R | 22 | In-Class Quiz IV (10 minutes)
[ Q4
sol ] Probability IV: Randomized Primality and Fingerprinting [ ppt | ps | pdf] Printer-friendly: [ ps | pdf ] |
Hwk8 Solutions [ps | pdf | ||
| 12 | Nov 14 | M | Recitation 11 Notes [ ps | pdf ] | |||
| Nov 15 | T | 23 | Probability V: Random Walks
[ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
Hwk11 [ ps | pdf | LaTeX ] | Hwk10 | |
| Nov 17 | R | 24 | Counting, Naming, and Worst-Case Compression [
ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
Hwk9 Solutions [ ps
| pdf ]
Hwk10 Solutions [ ps | pdf ] |
||
| 13 | Nov 21 | M | Recitation 12: TEST 3 (with solutions) [ ps
| pdf ] Practice test [ ps | pdf ] (solutions [ ps | pdf ] ) | |||
| Nov 22 | T | 25 | Cantor's Legacy: Infinity And Diagonalization [ ppt
| ps
| pdf] Printer-friendly: [ ps | pdf ] |
Hwk12 [ ps
| pdf
] Reading |
Hwk11 | |
| Nov 24 | R | Thanksgiving Vacation | ||||
| 14 | Nov 28 | M | Recitation 13 Notes [ ps | pdf ] Solutions [ ps | pdf ] | |||
| Nov 29 | T | 26 | Turing's Legacy: The Limits Of Computation [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
|||
| Dec 1 | R | 27 | In-Class Quiz V (10 minutes) [ Q5 sol ] Thales' and Godel's Legacy: Proofs and their Limitations [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] |
|||
| 15 | Dec 5 | M | Recitation 14 Notes [ ps | pdf ] Solutions [ ps | pdf ] | |||
| Dec 6 | T | 28 | The Limits of Proofs: Ancient Paradoxes With an Incompressible Resolution [ ppt
| ps
| pdf ] Printer-friendly: [ ps | pdf ] |
Hwk12 | ||
| Dec 8 | R | 29 | P versus NP:
A Theory of Efficient Computation [ ppt | ps | pdf ] Printer-friendly: [ ps | pdf ] | Hwk11 Solutions [ps | pdf]
Hwk12 Solutions [ps | pdf] | ||
| Dec 15 | Thursday | Final: Thursday,
Dec 15 8:30a.m.-11:30a.m. BH 136A Practice Final :[ ps | pdf ] Practice Final Solutions : [pdf|ps] | ||||