Fall 2006, Carleton College

- Instructor: David Liben-Nowell
- Lecture: 2/3c (TR 10:10a--11:55a), CMC 209.
- Office Hours: Mondays 1--2p, Wednesdays 2--4p, and Thursdays 2--3:30p.

Always feel free to email for an appointment if the scheduled times aren't good for you.

(I'm typically unavailable for appointments on Fridays and before 12:00p on Mondays.) - 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!
- There are tentative topics listed for each week of the term. They are meant as a rough guide only, and they are subject to change based on schedule, weather, and whim.

There is a form for office-hours scheduling
available. Please fill it out by Tuesday, 5 September 2006, and I'll
schedule office hours soon thereafter. (Be sure to include your
email address!)

The background survey ("PS0") distributed in
class on Tuesday is due on Thursday.

Part I of Problem Set 1, distributed on Tuesday,
is due on Friday.

Part II of Problem Set 1, distributed last Tuesday,
is due on Tuesday.

Part I of Problem Set 2, distributed Tuesday,
is due on Friday.

Clarification on PS2#1: the
parameters to the size function are reversed in one spot, and you
should treat "OR" as inclusive throughout the question.

- 19 September 2006 (T): PS1, proofs, sets, credit cards. Reading: §1.6–1.8, §2.7, §3.2, Wikipedia on Ariane 5, credit card numbers.
- 21 September 2006 (R): error-correcting codes. Reading: Wikipedia on Hamming codes, Reed–Solomon codes.

Part II of Problem Set 2, distributed last Tuesday,
is due on Tuesday.

Part I of Problem Set 3, distributed Tuesday,
is due on Friday.

- 26 September 2006 (T): error-correcting codes concluded; problems, algorithms, and induction. Reading: §3.3–3.5.
- 28 September 2006 (R): more induction. Reading: §2.1.

Part II of Problem Set 3, distributed last Tuesday,
is due on Tuesday.

Part I of Problem Set 4, distributed Tuesday,
is due on Friday.

- 3 October 2006 (T): asymptotics and Netflix, analyzing algorithms, recurrence relations. Reading: §2.2–2.3, 6.1–6.3, NYT on Netflix.
- 5 October 2006 (R): recurrence relations.

The first midterm of the course is scheduled
for Thursday, in class. You may bring one 8.5"-by-11" sheet
of paper containing handwritten notes. You may write on both sides of
the paper, but don't staple/tape/superglue/attach anything to 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 2006 in class, and through Problem Set 4) is fair game.

Part II of Problem Set 4, distributed last Tuesday,
is due on Tuesday.

- 10 October 2006 (T): relations and Renoir. Reading: §7.1, 7.4–7.6; Wikipedia on Painter's Algorithm.
- 12 October 2006 (R):
**midterm!**

Problem Set 5, distributed last Tuesday,
is due on Tuesday.

Part I of Problem Set 6, distributed Tuesday, is
due ~~Friday~~ next Tuesday.

Recommended counting problems from Rosen:
4.1.5, 4.1.11, 4.1.17, 4.1.29; 4.2.3, 4.2.7, 4.2.15, 4.2.29; 4.3.11,
4.3.17, 4.3.30; 4.4.5, 4.4.9, 4.4.21; 4.5.5, 4.5.11, 4.5.27, and
4.5.43.

- 17 October 2006 (T): topological sort, a magic trick, counting begun. Reading: §4.1–4.5, 6.5, 6.6
- 19 October 2006 (R): more counting—pigeonhole principle, permutations, combinations.

Part I of Problem Set 6, distributed last
Tuesday, is due Tuesday (postponed from last Friday).

Part II of Problem Set 6, distributed last
Tuesday, is due ~~Tuesday~~ Thursday.

Starting on Sunday, 22 October, there will be
weekly review/problem-solving sessions from 1:00 to 5:00pm on Sunday
afternoons on the third floor of the CMC.

Recommended probability problems from Rosen: 5.1.14, 5.1.33, 5.1.40;
5.2.13, 5.2.23, 5.2.38; and 5.3.7, 5.3.11, 5.3.16.

- 24 October 2006 (T): even more counting—combinations, permutations, and the binomial theorem.
- 26 October 2006 (R): introduction to probability. Reading: §5.1–5.3, Iowa Electronic Markets, NYT on Monty Hall.

Problem Set 7, distributed last Thursday,
is due on Tuesday.

Part I of Problem Set 8, distributed Tuesday,
is due on Friday.

- 31 October 2006 (T): random variables, expectation. Reading: sunk costs wiki; articles on probabilistic reasoning [1, 2, 3, 4].
- 2 November 2006 (R): more on probability and expectation.

Part II of Problem Set 8, distributed last Tuesday,
is due on Tuesday.

Office hours for Wednesday 8 November are
cancelled. If you'd like to make an appointment for another time,
please email.

The final exam will be self-scheduled. It
will be comprehensive, but it will focus on more recent material more
heavily. You may use one 8.5"-by-11" sheet of paper
containing handwritten notes or notes typed by you. You may use on
both sides of the paper. It must be in my hands by 2:00p on Thursday,
16 November 2006, so that I can put it into the exam envelope.

- 7 November 2006 (T): graphs (definitions, connectivity, representation). Reading: §8.1–8.4, 8.8, 9.4; web as a bowtie.
- 9 November 2006 (R): BFS/DFS, trees, spanning trees. Reading: §9.1–2; 9.4–9.5.

Problem Set 9, distributed last Tuesday,
is due on Tuesday.

**Update**: Because I didn't get to graph coloring in class last
Thursday, question #3 on ps9 is officially optional. You may hand it
in (separately from the rest of your ps9) up until 5:00p on
Wednesday.

- 14 November 2006 (T): graph coloring, bipartite graphs, etc.

Our final is scheduled for Monday, 20 November
2006, from 3:30p to 6:00p.