Lecture: 2a (MW 9:50--11:00a, F 9:40--10:40a), CMC 210.
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:
This course introduces some of the formal tools of computer science,
using a variety of applications as a vehicle. You'll learn how to
encode data so that when you scratch the back of a DVD, it still plays
just fine; how to distribute "shares" of your floor's PIN so that any
five of you can withdraw money from the floor bank account (but no
four of you can); how to play chess; and more. Topics that we'll
explore along the way include: logic and proofs, number theory,
elementary complexity theory and recurrence relations, basic
probability, counting techniques, and graphs.
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.
31 March 2010 (W):
propositional logic and applications.
Reading: §1.3, 1.4.
PS 3 was handed out today. It's due on Monday.
2 April 2010 (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:proofs, problems, algorithms
5 April 2010 (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.
7 April 2010 (W) (Josh Davis): proofs and sets.
Reading: §2.1–2.3.
PS 6 was handed out today. It's due on Monday.
9 April 2010 (F):
more sets; error-correcting codes.
Because we're slightly behind where I'd thought we'd be, I'm granting
you one additional "late day" pass. You can use it for ps08 or ps09
if you'd like, or you can bank it for use sometime later in the
term.
PS 9 was handed out today. It's due on Monday.
16 April 2010 (F):
polynomials, Reed–Solomon codes, and secret sharing.
PS 10 was handed out today. It's due on Wednesday.
Week 4:analysis of algorithms; recurrence relations
19 April 2010 (M):
proofs by induction.
Reading: §4.3–4.4.
The first exam is scheduled for next Monday,
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 Wednesday, and including PS 12) is fair game.
PS 11 was handed out today. It's due on Friday.
21 April 2010 (W): triangulation, Fibonacci numbers.
Reading: review Chapter 4.
PS 12 was handed out today. It's due on
Wednesday (after the exam).
23 April 2010 (F): Fibonacci numbers, analysis of algorithms,
asymptotic principles.
Reading: §3.1–3.3.
PS 13 was handed out today. It's due next Friday.
Week 5:analysis of algorithms; counting; midterm!
26 April 2010 (M):
antepenultimate exam!
28 April 2010 (W):
analysis of algorithms, recurrence relations, and mergesort.
Reading: §7.1–7.3.
PS 14 was handed out today. It's due next
Wednesday.
The expository exam was handed out today. It's
also due next Wednesday.
30 April 2010 (F):
solving recurrences and the master method; a little counting..
Reading: §5.1, 5.3, 5.5.
PS 15 was handed out today. It's due next Friday.
Week 6:counting and probability
3 May 2010 (M): midterm break!
5 May 2010 (W): midterm evaluations and counting practice.
Reading: nothing new.
PS 16 was handed out today. It's due Monday.
7 May 2010 (F):
more on counting: problems, rules, and a magic trick.
Reading: §5.2, §5.4.
PS 17 was handed out today. It's due on
Wednesday.
I distributed anonymized versions of the
expository essay today. You should return your comments for your
classmate to me by 14 May 2010.
Week 7:probability
10 May 2010 (M): sorting lower bounds; probability basics.
Reading: handout on sorting lower bounds
(§8.1 from Cormen, Leisersen, Rivest, and Stein).
Reading: §6.1–6.2.
PS 18 was handed out today. It's due on Friday.
12 May 2010 (W): probability, independence, conditional probability.
14 May 2010 (F):
random variables and expectation.
Reading: §6.4
PS 20 was handed out today. It's due on Wednesday.
Week 8:number theory and cryptography
17 May 2010 (M):
hash tables
Reading: review Chapter 6. Coming soon: §3.4–3.5
PS 21 was handed out today. It's due on Friday.
19 May 2010 (W):
intro to crypto and basics of modular arithmetic.
Reading: §3.4–3.6
PS 22 was handed out today. It's due on Monday.
Essay rewrites are due on 31 May 2010. There is
a two-day no-penalty extension: you may hand it in by 2 June 2010
without penalty.
21 May 2010 (F):
modular arithmetic and Diehard with a Vengeance.
Reading: §3.7
The second exam is scheduled for next 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.
PS 23 was handed out today. It's due Wednesday.
Week 9:cryptography; graphs
24 May 2010 (M):
Fermat's Little Theorem and the RSA cryptosystem.
Reading: review §3.4–3.7
PS 24 was handed out today. It's due Monday.
26 May 2010 (W): RSA wrapup.
Reading: §9.1–9.4; §10.1.
28 May 2010 (F):
penultimate exam!
Week 10:graphs; course wrapup
31 May 2010 (M):
graphs, trees, spanning trees.
2 June 2010 (W):
course wrapup.
Finals Period:
ultimate exam!
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.