# 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:

Week 1:

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

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.

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).

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.

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.

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.

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.

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.

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.

Wednesday:  quick-fire tour of probability.

2. Complete ps20 for Monday.
3. Reminder: prelim #2 is on Friday.
Friday:  prelim #2!
Week 9:

Monday:  cryptography; modular arithmetic; greatest common divisors.

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.