Fall 2007, Carleton College

- Instructor: David Liben-Nowell
- Lecture: 4a (MW 12:30--1:40p, F 1:10--2:10p),
~~CMC 319~~CMC 328. - 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.*

- 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 Carleton Sentinel is the mailing list of the CS community here at Carleton. We'll use it to send occasional updates on things that might be of interest. Sign up here!

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

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

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

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

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

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

- 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.3PS7 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

- 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.6PS8 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

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

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

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.