CS177 (Mathematics of Computer Science)
Fall 2006, Carleton College
Basic information:
- Instructor: David
Liben-Nowell
- Lecture: 2/3c (TR 10:10a--11:55a), CMC 209.
- Office Hours: Mondays 1--2p, Wednesdays 2--4p, and Thursdays 2--3:30p.
Always feel free to email for an appointment if the scheduled times
aren't good for you.
(I'm typically unavailable for appointments on Fridays and
before 12:00p on Mondays.)
- 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 Carleton Sentinel is the mailing list of the CS community here
at Carleton. We'll use it to send occasional updates on things that
might be of interest. Sign up here!
- There are tentative topics listed for each week of the term. They
are meant as a rough guide only, and they are subject to change based
on schedule, weather, and whim.
Course Materials:
Week 0 (The beginning of time [1 January 1980] to
10 September 2006):
There is a
form for office-hours scheduling
available. Please fill it out by Tuesday, 5 September 2006, and I'll
schedule office hours soon thereafter. (Be sure to include your
email address!)
Week 1 (11 September 2006 through 17 September 2006):
logic (and Deep Blue, NLP, and satisfiability)
The background survey ("PS0") distributed in
class on Tuesday is due on Thursday.
Part I of Problem Set 1, distributed on Tuesday,
is due on Friday.
- 12 September 2006 (T): (Dave Appleyard.) logistics and logic. Reading:
§1.1–1.5, §3.1.
- 14 September 2006 (R): circuits, satisfiability, game trees.
Reading: §9.2 (pp. 651–56), Wikipedia on SAT, P
vs NP, Deep Blue.
Week 2 (18 September 2006 through 24 September 2006):
sets, vectors, matrices (and error-correcting codes)
Part II of Problem Set 1, distributed last Tuesday,
is due on Tuesday.
Part I of Problem Set 2, distributed Tuesday,
is due on Friday.
Clarification on PS2#1: the
parameters to the size function are reversed in one spot, and you
should treat "OR" as inclusive throughout the question.
Week 3 (25 September 2006 through 1 October 2006):
induction (and recursive algorithms)
Part II of Problem Set 2, distributed last Tuesday,
is due on Tuesday.
Part I of Problem Set 3, distributed Tuesday,
is due on Friday.
- 26 September 2006 (T): error-correcting codes concluded; problems, algorithms, and induction. Reading: §3.3–3.5.
- 28 September 2006 (R): more induction. Reading: §2.1.
Week 4 (2 October 2006 through 8 October 2006):
analysis of algorithms, recurrence relations (and AVL trees and median finding)
Part II of Problem Set 3, distributed last Tuesday,
is due on Tuesday.
Part I of Problem Set 4, distributed Tuesday,
is due on Friday.
- 3 October 2006 (T): asymptotics and Netflix, analyzing algorithms, recurrence relations. Reading: §2.2–2.3, 6.1–6.3, NYT on Netflix.
- 5 October 2006 (R): recurrence relations.
Week 5 (9 October 2006 through 15 October 2006):
midterm exam!, relations (and computer graphics)
The first midterm of the course is scheduled
for Thursday, in class. You may bring one 8.5"-by-11" sheet
of paper containing handwritten notes. You may write on both sides of
the paper, but don't staple/tape/superglue/attach anything to 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 5
October 2006 in class, and through Problem Set 4) is fair game.
Part II of Problem Set 4, distributed last Tuesday,
is due on Tuesday.
- 10 October 2006 (T): relations and Renoir. Reading: §7.1,
7.4–7.6; Wikipedia on Painter's
Algorithm.
- 12 October 2006 (R): midterm!
Week 6 (16 October 2006 through 22 October 2006):
counting (and compression)
Problem Set 5, distributed last Tuesday,
is due on Tuesday.
Part I of Problem Set 6, distributed Tuesday, is
due Friday next Tuesday.
Recommended counting problems from Rosen:
4.1.5, 4.1.11, 4.1.17, 4.1.29; 4.2.3, 4.2.7, 4.2.15, 4.2.29; 4.3.11,
4.3.17, 4.3.30; 4.4.5, 4.4.9, 4.4.21; 4.5.5, 4.5.11, 4.5.27, and
4.5.43.
- 17 October 2006 (T): topological sort, a magic trick, counting begun. Reading: §4.1–4.5, 6.5, 6.6
- 19 October 2006 (R): more counting—pigeonhole principle, permutations, combinations.
Week 7 (23 October 2006 through 29 October 2006):
counting and probability
Part I of Problem Set 6, distributed last
Tuesday, is due Tuesday (postponed from last Friday).
Part II of Problem Set 6, distributed last
Tuesday, is due Tuesday Thursday.
Starting on Sunday, 22 October, there will be
weekly review/problem-solving sessions from 1:00 to 5:00pm on Sunday
afternoons on the third floor of the CMC.
Recommended probability problems from Rosen: 5.1.14, 5.1.33, 5.1.40;
5.2.13, 5.2.23, 5.2.38; and 5.3.7, 5.3.11, 5.3.16.
- 24 October 2006 (T): even more counting—combinations,
permutations, and the binomial theorem.
- 26 October 2006 (R): introduction to probability. Reading:
§5.1–5.3, Iowa
Electronic Markets, NYT on Monty
Hall.
Week 8 (30 October 2006 through 5 November 2006):
probability (and hash tables and quicksort)
Problem Set 7, distributed last Thursday,
is due on Tuesday.
Part I of Problem Set 8, distributed Tuesday,
is due on Friday.
- 31 October 2006 (T): random variables, expectation. Reading: sunk costs wiki;
articles on probabilistic reasoning [1,
2,
3,
4].
- 2 November 2006 (R): more on probability and expectation.
Week 9 (6 November 2006 through 12 November 2006):
graphs (and the structure of the web and social networks)
Part II of Problem Set 8, distributed last Tuesday,
is due on Tuesday.
Office hours for Wednesday 8 November are
cancelled. If you'd like to make an appointment for another time,
please email.
The final exam will be self-scheduled. It
will be comprehensive, but it will focus on more recent material more
heavily. You may use one 8.5"-by-11" sheet of paper
containing handwritten notes or notes typed by you. You may use on
both sides of the paper. It must be in my hands by 2:00p on Thursday,
16 November 2006, so that I can put it into the exam envelope.
- 7 November 2006 (T): graphs (definitions, connectivity,
representation). Reading: §8.1–8.4, 8.8, 9.4; web as a bowtie.
- 9 November 2006 (R): BFS/DFS, trees, spanning trees. Reading:
§9.1–2; 9.4–9.5.
Week 10 (13 November 2006 through 15 November 2006):
(TBA—probably more on graphs)
Problem Set 9, distributed last Tuesday,
is due on Tuesday.
Update: Because I didn't get to graph coloring in class last
Thursday, question #3 on ps9 is officially optional. You may hand it
in (separately from the rest of your ps9) up until 5:00p on
Wednesday.
- 14 November 2006 (T): graph coloring, bipartite graphs, etc.
Finals Period:
Our final is scheduled for Monday, 20 November
2006, from 3:30p to 6:00p.