CS 202 (Math of Computer Science)
Spring 2014, Carleton College

Basic Information

• Instructor: David Liben-Nowell
• Lecture: 1a, Weitz 233.
• Office Hours: see my homepage. Always feel free to email for an appointment if the scheduled times aren't good for you.

• This webpage was originally stored in Moodle, which does not have an easy capacity to publish a version of an old webpage for a course. Major thanks to Dave Musicant, whose Moodle-scraping tool I used to generated this page, which is an approximation of the original.

Course Materials:

• the anonymous feedback form for CS 202.
• the Piazza site for CS 202.
• LaTeX materials:  installing LaTeX on your computer; a tutorial [MIT]; a reference guide [Cambridge]; the LaTeX Wikibook; a symbol finder; a table editor.
  

Week 1:

• Monday: course overview, propositional logic

  1. Reading: DLN §1,§3.1, §3.2; propositional logic in a page.
  2. Complete ps01 by Wednesday.
  3. Complete ps02 by Friday.
  4. Optional:  Champion at Checkers That Cannot Lose to People (K. Chang, NYT, 20 Jul 2007); Checkers is Solved (J. Schaeffer et al, Science, Sep 2007).

Wednesday:  truth tables, logical equivalence, some propositional logic challenges, Rowena.

1. Reading:  DLN §3.3.
2. Complete ps03 for Monday.
3. Think about the Sheffer stroke challenge problems for Friday.

Friday:  Sheffer stroke, making $1,000,000 with logic; predicates and quantifiers.

1. Reading:  DLN §3.4, §3.5; predicate logic in one page.
2. Complete ps04 for Wednesday.

Week 2:

Monday:  predicates and quantifiers; NLP; game trees, tic-tac, and Deep Blue; a hint of proofs?

1. Reading:  DLN §2.6, §4.1–§4.3; as you please, the notation summary below.
2. Complete ps05 for Friday.
3. Totally optional reading:  "Your Move" and "In the Bird Cage", from The New Yorker.

Wednesday:  game tree wrapup; proofs (why and how).

1. Reading: DLN §2.1, §2.3; skim §2.2 and read §2.2's CS Connections; datatypes in a page.
2. Complete ps06 for Monday.

Friday:  proofs strategies, broken proofs, basic datatypes.

1. Reading:  DLN §2.4–2.5.
2. Complete ps07 for Wednesday.

Week 3:

Monday:  proofs wrapup; error-correcting codes.

1. Reading: DLN §4.5 (and refer to Chapter 2 as necessary).
2. Complete ps08 for Friday.

Wednesday:  error-correcting codes (general properties and Hamming codes).

1. Reading:  review DLN §4.5.
2. Complete ps09 for Monday.
3. Come to class on Friday with messages corresponding to the (possibly corrupted) Hamming code codewords I gave you in class.

Friday:  Hamming codes, Reed–Solomon codes, and secret-sharing.

1. Reading:  DLN p. 728–729 and §5.1; start on DLN §5.2.
2. Complete ps10 for Wednesday.

Week 4:

Monday:  secret sharing, review.

1. Reading:  DLN §5.2.
2. No new problem set assigned; focus instead on preparing for prelim #1 on Friday. For the exam, you may bring one 8.5"-by-11" sheet of paper containing notes handwritten or typed by you. You may write on both sides of the paper. Any material up to and including secret sharing (so through class today, through Chapter 4, and through ps09) is fair game.
3. Extension: we're a day behind, so you're not ready for ps10 (which was scheduled to be due on Wednesday) yet.  You can do it anyway, but I'm officially granting you all an extra late pass that you can use to hand in ps10 on Monday.  I will probably also give you an extra half problem set for Monday, which will be assigned on Wednesday.

Wednesday:  proofs by mathematical induction.

1. Reading:  DLN §5.3 (for Monday).
2. Complete ps11 for Monday.
3. Reminder: prelim #1 on Friday!

Friday:  prelim #1!

Week 5:

Monday:  proofs by strong induction; the Fibonacci numbers.

1. Reading:  DLN §6.1–6.2.
2. Complete ps12 for Wednesday.
3. Complete ps13 for Friday.

Wednesday:  Fibonacci wrapup; "code review" of ps09; problems and algorithms.

1. Read DLN §6.3 and the Fibonacci handout.
2. Complete ps14 in your assigned group by next Wednesday.

Friday:  midterm evals; efficiency; O/Ω/Θ.

1. Reading:  DLN §6.1–6.3; start §6.4.
2. Complete ps15 for Friday.
3. Enjoy the "break" on Monday!

Week 6:

Wednesday:  asymptotics; recurrence relations.

1. Reading: §6.4.
2. Complete ps16 for Friday Monday.

Friday:  recurrence relations; the master method.

1. Reading:  recurrence relations in a page (see below); review DLN Chapter 6.
2. Complete ps17 in your assigned groups by next Friday.

Week 7:

Monday:  master method wrapup; counting.

1. Read DLN §9.1–9.2.

Wednesday:  more counting.

1. Reading:  DLN §9.3–9.4; counting in a page.
2. Complete ps18 for Monday.

Friday:  counting exercises, pigeonhole principle, combinatorial proofs, weekend magic.

1. Reading:  DLN §10.1–10.2.
2. Complete ps19 for Wednesday.

Week 8:

Monday:  probability introduction.

1. No new problem set assigned; focus instead on preparing for prelim #2 on Friday. For the exam, you may bring one 8.5"-by-11" sheet of paper containing notes handwritten or typed by you. You may write on both sides of the paper. Any material up to and including counting (so through class Friday/today, through Chapter 9, and through ps19) is fair game.
2. Reading:  DLN §10.3.

Wednesday:  quick-fire tour of probability.

1. Reading: DLN §10.4.
2. Complete ps20 for Monday.
3. Reminder: prelim #2 is on Friday.

Friday:  prelim #2!

Week 9:

Monday:  cryptography; modular arithmetic; greatest common divisors.

1. Reading: DLN §7.1–7.2.
2. Complete ps21 for Wednesday.
3. Complete ps22 for Friday.

Wednesday:  GCDs/Euclidean algorithm/the extended Euclidean algorithm; multiplicative inverses.

1. Reading: DLN §7.3 [up to top of p. 721] and §7.4.
2. No new assignment. (The last problem set will come out on Friday.)

Friday:  multiplicative inverses and Fermat's Little Theorem.

1. Reading: DLN §7.5.
2. Complete ps23 in your assigned partnerships by Wednesday (the last day of class).

Week 10:

Monday:  the RSA cryptosystem.

1. Finish ps23 for Wednesday.
2. Your crib sheets for the final (as before:  8.5"-by-11", two sides, ...) are due in the suite outside my office (Weitz 225) by the end of the day on Wednesday.

Wednesday:  RSA wrapup; course evals; ask me anything.