Lecture: 2a (MW 9:50--11:00a, F 9:40--10:40a), Laird 206.
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.
Course Materials:
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.
5 January 2011 (W):
propositional logic and applications.
Reading: §1.3, 1.4.
PS 3 was handed out today. It's due on Monday.
7 January 2011 (F):
propositional logic wrapup; predicates and quantifiers;
natural language processing.
Reading: §4.5, 10.2 (game trees)
PS 4 was handed out today. It's due on Wednesday.
Week 2:error-correcting codes
10 January 2011 (M):
game trees; binary search; proofs (why).
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. Reading: §1.6–1.7;
History's Worst Software Bugs (Simson Garfinkel, Wired, November 2005); Wikipedia on Ariane 5 and
Therac 25.
PS 5 was handed out today. It's due on Friday.
12 January 2011 (W):
proofs and sets.
Reading: §2.1–2.3.
PS 6 was handed out today. It's due on Monday.
14 January 2011 (F):
more sets and sequences; error-correcting codes.
PS 10 was handed out today. It's due on Wednesday.
Because we're slightly behind in class
relative to problem sets, I'm giving you all another free late pass to
use as you please throughout the term. Enjoy!
Week 4:induction, analysis of algorithms; recurrence relations
24 January 2011 (M):
proofs by induction.
Reading: §4.2.
PS 11 was handed out today. It's due on Friday.
26 January 2011 (W):
problems and algorithms; Fibonacci numbers.
Reading: §4.3–4.4.
PS 12 was handed out today. It's due on
Monday.
Our first preliminary exam 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. Any material up to and including
induction (so through class on Friday, and including PS 12) is fair
game.
28 January 2011 (F):
Fibonacci numbers, computing mods, and I'm Thinking of a Number.
Reading: §3.1–3.3.
Week 5:analysis of algorithms; midterm!
31 January 2011 (M):
analysis of algorithms, recurrence relations, and mergesort.
Reading: §7.1–7.3.
PS 13 was handed out today. It's due on Friday.
The expository exam was handed out today. It's
due next Wednesday (9 February).
2 February 2011 (W): prelim #1!
4 February 2011 (F): solving recurrences and the master method.
Reading: review §7.2–7.3.
PS 14 was handed out today. It's due on Friday.
Week 6:counting
7 February 2011 (M): midterm break!
9 February 2011 (W): master method; counting introduction.
Reading: §5.1, 5.3, 5.5.
PS 15 was handed out today. It's due Monday.
11 February 2011 (F): counting practice and some weekend magic.
Reading: §7.5–7.6.
PS 16 was handed out today. It's due Wednesday.
(Note that question #2 is optional.)
Week 7:counting and probability
14 February 2011 (M): counting rules, variant chess, and
combinatorial proofs.
Reading: §5.2, 5.4; the handout from Cormen/Leiserson/Rivest/Stein.
PS 17 was handed out today. It's due Friday
(despite what it says on the sheet). (Note that question #3 is
optional.)
16 February 2011 (W): sorting lower bounds; probability basics.
Reading: §6.1
PS 18 was handed out today. It's due on Monday.
18 February 2011 (F): probability, independence, and conditional
probability.
PS 19 was handed out today. It's due on Wednesday.
Week 8:number theory and cryptography
21 February 2011 (M):
random variables and expectation.
Reading: §6.4
PS 20 was handed out today. It's due on Friday.
23 February 2011 (W):
ESP
and an introduction to cryptography.
Reading: §3.4–3.6
PS 21 was handed out today. It's due on Monday.
25 February 2011 (F):
modular arithmetic and Diehard with a Vengeance.
Reading: §3.7
PS 22 was handed out today. It's due on Wednesday.
Week 9:cryptography
28 February 2011 (M):
multiplicative inverses and Fermat's Little Theorem.
Reading: review §3.4–3.7
PS 23 was handed out today. It's due Friday Monday.
The second exam is scheduled for Friday, 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. Any material up to and including cryptography
(so through class on Monday, and including PS 23) is fair game.