Lecture: 1a (MW 8:30--9:40a, F 8:30--9:30a), CMC 319.
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.
Announcements:
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!
PS 1 was handed out today. It's due on Wednesday.
PS 2 was handed out today. It's due on Friday.
16 September 2009 (W): propositional logic and applications; predicate logic.
Reading: §1.3, 1.4.
PS 3 was handed out today. It's due on Monday.
18 September 2009 (F): predicates and quantifiers; natural
language processing; [game trees].
Reading: §4.5, 10.2
(game trees) 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.
23 September 2009 (W): math background; error-correcting codes.
Reading:
Wikipedia article on credit card
numbers, Hamming distance, and Hamming codes.
For the relevant mathematical background, please
refer as necessary to §2.1–2.3, 3.8, and A.2 or the
distributed handout.
PS 6 was handed out today. It's due on Monday.
25 September 2009 (F): Hamming codes; how CDs work.
28 September 2009 (M): secret sharing and Reed–Solomon code
conclusion; problems and algorithms.
Reading: §4.1, 2.4.
PS 8 was handed out today. It's due on Friday.
30 September 2009 (W): proofs by induction.
Reading: §4.2.
PS 9 was handed out today. It's due on Monday.
2 October 2009 (F): strong induction, Fibonacci numbers.
Reading: §4.3–4.4.
PS 10 was handed out today. It's due on Wednesday.
Week 4:analysis of algorithms; recurrence
relations
5 October 2009 (M): analysis of algorithms, recurrence relations,
and mergesort.
Reading: §3.1–3.3.
PS 11 was handed out today. It's due on Friday.
7 October 2009 (W): solving recurrences and the master method.
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 class on Friday, and including PS 13) is fair game.
PS 12 was handed out today. It's due on Monday.
9 October 2009 (F): more on the master method, computing the Fibonaccis (x 3), and a magic trick.
Reading: §5.1.
PS 13 was handed out today. It's due next Friday.
Week 5:counting; midterm!
12 October 2009 (M): counting introduction: counting unions,
counting sequences, using bijections, pigeonhole principle.
Reading: §5.2–5.3.
The expository exam (a.k.a. PS 14) was handed out today. It's due next Wednesday.
14 October 2009 (W): midterm!
16 October 2009 (F): more on counting.
Reading: §5.4–5.5.
Matthew
Sorell, "The Mathematics of Bell Ringing". (In the Courses directory
for CS 202; see home.its.carleton.edu.) And some samples!
PS 15 was handed out today. It's due next Friday.
Week 6:counting and probability
19 October 2009 (M): midterm break!
21 October 2009 (W): even more counting; comparison-based sorts,
and counting sort.
Reading: handout on sorting lower bounds
(§8.1 from Cormen, Leisersen, Rivest, and Stein).
PS 16 was handed out today. It's due on Monday.
23 October 2009 (F): sorting lower bounds; combinatorial proofs; the conclusion of counting.
Reading: §7.5–7.6.
PS 17 was handed out today. It's due on Wednesday.
30 October 2009 (F): random variables and expectation.
Reading: §6.4
PS 20 was handed out today. It's due on Wednesday.
If you're unsatisfied with your grade on the expository exam, you may submit a revision (on 6 November or sooner, say).
Week 8:number theory and cryptography
2 November 2009 (M): hash tables, pairwise independence.
Reading: §3.4–3.5
PS 21 was handed out today. It's due on Friday.
4 November 2009 (W): intro to crypto, Diehard with a Vengeance, and basics of modular arithmetic.
Reading: §3.4–3.6
PS 22 was handed out today. It's due on Monday.
6 November 2009 (F): modular arithmetic.
Reading: §3.6–3.7
PS 23 was handed out today. It's due next Friday.
Week 9:cryptography; graphs
9 November 2009 (M): the RSA cryptosystem.
Reading: §3.7
11 November 2009 (W): graph definitions, connectivity, and BFS and DFS.
Reading: §9.1–9.2.
PS 24 was handed out today. It's due on Monday.
13 November 2009 (F): trees, spanning trees
Reading: §8.5, 8.6.
PS 25 was handed out today. It's due on Wednesday.
Week 10:graphs; course wrapup
16 November 2009 (M): trees, spanning trees, graph coloring
(the Northeast)
Reading: §9.3, 9.4, 9.8.
18 November 2009 (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, deposited in my mailbox.
