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 Friday.
PS 2 was handed out today. It's due on Monday.
6 January 2012 (F):
propositional logic and applications.
Reading: §1.3, 1.4.
PS 3 was posted to Moodle today. It's due on
Wednesday.
Week 2:logic; error-correcting codes
9 January 2012 (M):
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 Friday.
11 January 2012 (W):
game trees; binary search; proofs (why).
Reading: §1.6–1.7; handout on basic datatypes. Optional:History's Worst Software Bugs (Simson Garfinkel, Wired, November 2005); Wikipedia on Ariane 5 and
Therac 25.
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.
PS 5 was handed out today. It's due on Monday.
13 January 2012 (F):
proofs and sets.
Reading: §2.1–2.3.
PS 6 was handed out today. It's due on Wednesday.
Week 3:error-correcting codes; induction
16 January 2012 (M):
error-correcting codes.
Reading:
Posted notes on error-correcting codes, §0.1 intro,0.1.1,0.1.2. Optionally:
Wikipedia article on credit card
numbers.
PS 7 was handed out today. It's due on Friday.
18 January 2012 (W): error-correcting codes, formalized; Hamming codes.
Reading: Posted notes on error-correcting
codes, §0.3.
PS 8 was handed out today. It's due on Monday.
20 January 2012 (F):
Hamming codes, polynomials, and Reed–Solomon codes.
Reading:Rosen §4.1, 2.4.
PS 9 was handed out today. It's due on
Wednesday.
Week 4:induction
23 January 2012 (M):
polynomials, Reed–Solomon codes, and secret sharing.
Our first preliminary exam is scheduled for
next WednesdayFriday, 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 Monday, and
including PS 12) is fair game.
27 January 2012 (F):
strong induction; workshopping ps9-1(a) solutions; triangulation.
Reading: §4.3–4.4.
PS 12 was handed out today. It's due on
MondayWednesday. (Sorry for the typo.)
Week 5:analysis of algorithms; recurrence relations; midterm!
30 January 2012 (M):
Fibonacci numbers.
Reading: §3.1–3.3.
1 February 2012 (W):
Fibonacci numbers, problems and algorithms, computing mods, and I'm Thinking of a Number.
Reading: §7.1.
PS 13 was handed out today. It's due on Wednesday.
The expository exam was handed out today. It's
due next Friday.
3 February 2012 (F): prelim #1
Week 6:recurrences
6 February 2012 (M): midterm break!
8 February 2012 (W):
analysis of algorithms, asymptotics, recurrence relations.
Reading: §7.2–7.3.
PS 14 was handed out today. It's due on Monday.
10 February 2012 (F):
solving recurrences and the master method.
Reading: handout; review §7.2–7.3.
PS 15 was handed out today. It's due on Wednesday.
22 February 2012 (W):
probability, independence, and conditional probability.
Reading: §6.3–6.4. Optional: Tom Jagatic, Nathaniel Johnson, Markus Jakobsson, and Filippo Menczer. Social Phishing, CACM, 2005.
PS 20 was handed out today. It's due on FridayMonday.
24 February 2012 (F):
random variables and expectation; an introduction to cryptography.
Reading: §3.4–3.6
PS 21 was handed out today. It's due on Friday.
Week 9:number theory and cryptography
27 February 2012 (M):
modular arithmetic and the Euclidean algorithm.
PS 22 was handed out today. It's due on Monday.
The second exam is scheduled for 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 probability
(so through class on Friday 2/24, and including PS 21) is fair game.
29 February 2012 (W): prelim #2
2 March 2012 (F):
multiplicative inverses and Diehard with a Vengeance.
Reading: §3.7
PS 23 was handed out today. It's due Wednesday.
Week 10:cryptography; course wrapup
5 March 2012 (M):
Fermat's Little Theorem and the RSA cryptosystem.
PS 24 was handed out today. It's due Friday.
Reading: review §3.4–3.7.
7 March 2012 (W): RSA.
The comprehensive final is self-scheduled (see
below). You may use a crib sheet consisting of one
8.5"-by-11" sheet of paper containing notes handwritten or
typed by you. (Details on getting it to me will be finalized in class
on Friday.) You may write on both sides of the paper. Any material
in the course is fair game.
9 March 2012 (F): why breaking RSA seems hard; course evals; ask
me anything.