CS202 (Math of Computer Science) Fall 2007, Carleton College

Week 1: logistics and logic

10 September 2007 (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 0 (the survey) was handed out in class on Monday, 10 September 2007. Bring it back at the beginning of class on Wednesday, 12 September 2007.

PS 1 was handed out in class on Monday, 10 September 2007. It is due in class on ~~Friday, 14 September 2007 and Monday, 17 September 2007~~ Friday, 14 September 2007 (2 questions); Monday, 17 September 2007 (2 questions); and Wednesday, 19 September 2007 (2 questions).
12 September 2007 (W): propositional logic and applications; predicate logic.
Reading: §1.3, 1.4.
14 September 2007 (F): predicates and quantifiers; natural language processing; game trees.
Reading: §4.5, ~~9.2~~ 10.2 (game trees); wikipedia on Deep Blue.
Optional:
T. Mueller, "Your Move" The New Yorker, 12 December 2005.
J. Schaeffer, N. Burch, Y. Björnsson, A. Kishimoto, M. Müller, R. Lake, P. Lu, S. Sutphen, Checkers Is Solved, Science, 14 September 2007.

Week 2: error-correcting codes

17 September 2007 (M): proofs (how and why).
Reading: §1.6–1.7; wikipedia on Ariane 5 and credit card numbers.
For the relevant mathematical background, please refer as necessary to §2.1–2.3, 3.8, and A.2 or the distributed handout.
19 September 2007 (W): math background; error-correcting codes.
Reading: Wikipedia on Hamming codes.

PS2 was handed out in class on Wednesday, 19 September 2007. It is due in class on Monday, 24 September 2007, and Wednesday, 26 September 2007.
21 September 2007 (F): Hamming codes; how CDs work.
Reading: Wikipedia on Reed–Solomon codes.
Optional: B. Chazelle, Coding and Computing Join Forces. Science, 21 September 2007.

Week 3: induction; analysis of algorithms

24 September 2007 (M): Reed–Solomon code conclusion; problems and algorithms.
Reading: §4.1–4.2, 2.1.
26 September 2007 (W): proofs by induction.
(Re)reading: §4.1–4.2, 2.4.

PS3 was handed out in class on Wednesday, 26 September 2007. It is due in class on Monday, 1 October 2007, and Wednesday, 3 October 2007.
28 September 2007 (F): strong induction, Fibonacci numbers.
Reading: §4.3–4.4.

Week 4: analysis of algorithms; recurrence relations

1 October 2007 (M): analysis of algorithms, recurrence relations, mergesort, and factorial.
Reading: §3.1–3.3.
3 October 2007 (W): computing the Fibonaccis (x 3); solving recurrences.
Reading: §7.1–7.3.

The midterm 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. You will be asked to hand in your crib sheet with your exam. Any material up to and including recurrence relations (so through 5 October 2007 in class, and through Problem Set 4) is fair game.

PS4 was handed out in class on Wednesday, 3 October 2007. It is due in class on Monday, 8 October 2007, and Wednesday, 10 October 2007.

If you want to have a copy of my solutions for PS4 before the midterm, please submit your problem set to me by 3:00p on Tuesday, 9 October 2007, and I will give you solutions (not to be shared with anyone else in the class).
5 October 2007 (F): the master method and a magic trick.
Reading: §5.1.

Week 5: counting; midterm!

8 October 2007 (M): counting introduction: counting unions, counting sequences, using bijections, and the pigeonhole principle.
Reading: §5.2–5.3.
10 October 2007 (W): midterm!
12 October 2007 (F): more on counting.
Reading: §5.4–5.5.

PS5 was handed out on Friday. It's due ~~Wednesday~~ Friday, 19 October 2007.

Week 6: counting

15 October 2007 (M): midterm break!
17 October 2007 (W): (Jeff.) comparison-based sorts, counting sort, and lower bounds.
Reading: handout on sorting lower bounds (§9.1 from Cormen, Leisersen, Rivest, and Stein).
19 October 2007 (F): combinatorial proofs; the conclusion of counting.
Reading: §7.5–7.6.

PS6 was handed out in class on Friday. It's due on Wednesday, 24 October 2007.

Week 7: probability

22 October 2007 (M): probability basics.
Reading: §6.1–6.2.
Optional:
four articles on probabilistic reasoning: Tversky–Kahneman, Tversky–Kahneman, Schwartz, Aaron–Spivey-Knowlton.
John Tierney, Behind Monty Hall's Doors: Puzzle, Debate and Answer?, New York Times, 21 July 1991.
24 October 2007 (W): conditional probability
Reading: §6.3

PS7 was handed out in class on Wednesday. It's due on Monday and Wednesday, 29 and 31 October 2007.
26 October 2007 (F): random variables and expectation.
Reading: §6.4

Week 8: number theory and cryptography

29 October 2007 (M): hash tables, intro to crypto, and Diehard with a Vengeance.
Reading: §3.4–3.5
31 October 2007 (W): basics of modular arithmetic.
Reading: §3.4–3.6

PS8 was handed out in class on Wednesday. It's due on Monday and Wednesday, 5 and 7 November 2007.
2 November 2007 (F): modular arithmetic and the RSA cryptosystem.
Reading: §3.6–3.7

Week 9: graphs

5 November 2007 (M): cryptography spillover, graph definitions.
Reading: §9.1–9.3.
7 November 2007 (W): graph definitions, connectivity, and BFS and DFS.
Reading: §9.4, 9.6.

PS9 was handed out in class on Wednesday. It's due Wednesday, 14 November 2007.
9 November 2007 (F): trees, spanning trees
Reading: §10.1, 10.4–10.5.

Week 10: graphs; course wrapup

12 November 2007 (M): graph coloring (the Northeast)
Reading: §9.8.
14 November 2007 (W): course wrapup.

Finals Period:

Our final is a take-home distributed on the last day of classes. It is due at 5:00p on Monday, 19 November 2007, deposited in my mailbox.

Resources/clarifications for the final:

If you'd like to use LaTeX to type your solutions, you should take a look at this tutorial. LaTeX is installed on the CS machines, and you can use it by typing latex exam.tex (or whatever).
In 4(d), a clarification: "that are adjacent to X in the graph G" would be better written as "that are adjacent to some element of X in the graph G".
For all questions, don't forget to prove your answers.

CS202 (Math of Computer Science)
Fall 2007, Carleton College

[Jump to current week]

Basic information:

Announcements:

Course Materials: