CS177 (Mathematics of Computer Science)
Fall 2006, Carleton College


[Jump to current week]

Basic information:

Announcements:

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.
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.
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.
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.
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.
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.
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.
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.
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.
Finals Period:
Our final is scheduled for Monday, 20 November 2006, from 3:30p to 6:00p.