CS202 (Math of Computer Science) Winter 2011, Carleton College

Basic information:

• Instructor: David Liben-Nowell
• Lecture: 2a (MW 9:50--11:00a, F 9:40--10:40a), Laird 206.
• Office Hours: see my homepage.
Always feel free to email for an appointment if the scheduled times aren't good for you.

• Official catalogue description: An introduction to some of the mathematical tools crucial to computer science. Topics include logic and proofs; sets, relations, and functions; elementary complexity theory and recurrence relations; basic probability; counting techniques; and graphs. These mathematical tools will be discussed through their application to various topics in computer science, including error-correcting codes, hashing, cryptography, computer graphics, games, and the structure of the Internet and the web.

Course Materials:

• There is an anonymous feedback form available for any comments that you have about the course. If you have any suggestions or comments on the class (style, content, workload, etc.), please feel free to use this form to let me know.
• The CS department has an email newsletter, the Carleton Sentinel, that we use for occasional updates on things that might be of interest. Sign up here!
Week 1: logistics and logic
• 3 January 2011 (M): checkers, course overview, and propositional logic.
Reading: §1.1, 1.2, 1.5, and Champion at Checkers That Cannot Lose to People (by K. Chang, New York Times, 20 July 2007).
PS 1 was handed out today. It's due on Wednesday.
PS 2 was handed out today. It's due on Friday.
• 5 January 2011 (W): propositional logic and applications.
PS 3 was handed out today. It's due on Monday.
• 7 January 2011 (F): propositional logic wrapup; predicates and quantifiers; natural language processing.
PS 4 was handed out today. It's due on Wednesday.
Week 2: error-correcting codes
• 10 January 2011 (M): game trees; binary search; proofs (why).
Optional: wikipedia on Deep Blue.
Optional: T. Mueller, "Your Move" The New Yorker, 12 December 2005.
Optional: J. Schaeffer et al., Checkers Is Solved, Science, 14 Sept 2007.
Reading: §1.6–1.7; History's Worst Software Bugs (Simson Garfinkel, Wired, November 2005); Wikipedia on Ariane 5 and Therac 25.
PS 5 was handed out today. It's due on Friday.
• 12 January 2011 (W): proofs and sets.
PS 6 was handed out today. It's due on Monday.
• 14 January 2011 (F): more sets and sequences; error-correcting codes.
Reading: Posted notes on error-correcting codes, §0,1,2.
Wikipedia article on credit card numbers, Hamming distance.
PS 7 was handed out today. It's due on Wednesday.
Week 3: error-correcting codes
• 17 January 2011 (M): error-correcting codes, a bit more formally; Hamming codes.
Reading: Posted notes on error-correcting codes, §3.
PS 8 was handed out today. It's due on Friday.
• 19 January 2011 (W): Hamming codes, polynomials, and secret sharing.
Reading: Posted notes on error-correcting codes, §4; Rosen §4.1, 2.4; wikipedia on the Shamir secret-sharing scheme.
PS 9 was handed out today. It's due on Monday.
• 21 January 2011 (F): polynomials, Reed–Solomon codes, and secret sharing.
Wikipedia on Reed–Solomon codes.
Optionally, Coding and Computing Join Forces (by Bernard Chazelle, Science, 21 September 2007)
PS 10 was handed out today. It's due on Wednesday.
Because we're slightly behind in class relative to problem sets, I'm giving you all another free late pass to use as you please throughout the term. Enjoy!
Week 4: induction, analysis of algorithms; recurrence relations
• 24 January 2011 (M): proofs by induction.
PS 11 was handed out today. It's due on Friday.
• 26 January 2011 (W): problems and algorithms; Fibonacci numbers.
PS 12 was handed out today. It's due on Monday.
Our first preliminary exam is scheduled for next Wednesday, in class. 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 induction (so through class on Friday, and including PS 12) is fair game.
• 28 January 2011 (F): Fibonacci numbers, computing mods, and I'm Thinking of a Number.
Week 5: analysis of algorithms; midterm!
• 31 January 2011 (M): analysis of algorithms, recurrence relations, and mergesort.
PS 13 was handed out today. It's due on Friday.
The expository exam was handed out today. It's due next Wednesday (9 February).
• 2 February 2011 (W): prelim #1!
• 4 February 2011 (F): solving recurrences and the master method.
PS 14 was handed out today. It's due on Friday.
Week 6: counting
• 7 February 2011 (M): midterm break!
• 9 February 2011 (W): master method; counting introduction.
PS 15 was handed out today. It's due Monday.
• 11 February 2011 (F): counting practice and some weekend magic.
PS 16 was handed out today. It's due Wednesday. (Note that question #2 is optional.)
Week 7: counting and probability
• 14 February 2011 (M): counting rules, variant chess, and combinatorial proofs.
Reading: §5.2, 5.4; the handout from Cormen/Leiserson/Rivest/Stein.
PS 17 was handed out today. It's due Friday (despite what it says on the sheet). (Note that question #3 is optional.)
• 16 February 2011 (W): sorting lower bounds; probability basics.
PS 18 was handed out today. It's due on Monday.
• 18 February 2011 (F): probability, independence, and conditional probability.
Optional: four articles on probabilistic reasoning: Tversky–Kahneman, Tversky–Kahneman, Schwartz, Aaron–Spivey-Knowlton.
PS 19 was handed out today. It's due on Wednesday.
Week 8: number theory and cryptography
• 21 February 2011 (M): random variables and expectation.
PS 20 was handed out today. It's due on Friday.
• 23 February 2011 (W): ESP and an introduction to cryptography.
PS 21 was handed out today. It's due on Monday.
• 25 February 2011 (F): modular arithmetic and Diehard with a Vengeance.
PS 22 was handed out today. It's due on Wednesday.
Week 9: cryptography
• 28 February 2011 (M): multiplicative inverses and Fermat's Little Theorem.