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.
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.
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.
PS 9 was handed out today. It's due on Monday.
2 October 2009 (F): strong induction, Fibonacci numbers.
PS 10 was handed out today. It's due on Wednesday.
Week 4:analysis of algorithms; recurrence
5 October 2009 (M): analysis of algorithms, recurrence relations,
PS 11 was handed out today. It's due on Friday.
7 October 2009 (W): solving recurrences and the master method.
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.
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.
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.
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.
PS 17 was handed out today. It's due on Wednesday.