2008 December 2 / jjddaavviiss@@ccaarrlleettoonn..eedduu
Carleton College CS 202, Fall 2008, Prof. Joshua R. Davis
This course is intended to give you basic mathematical knowledge and skills needed by every computer science major. In content it is primarily elementary combinatorics, probability, graph theory, and number theory — broadly, discrete mathematics. However, the most important aspect of the course is learning how to construct logical, rigorous proofs of mathematical statements. Proof is the bottom line in mathematics and computer science; it is how we create new facts and how we know that they are true. By rigorously devising and proving statements, you become a creator of mathematics and computer science, not just a user. In its goals this course is similar to Math 236 (Mathematical Structures), but with more emphasis on algorithms and computational applications.
The official prerequisites are CS 111 (Introduction to Computer Science) and Math 111 (Introduction to Calculus). More generally, this course is appropriate for students who are comfortable with math and programming, including recursion. Talk to me if you are concerned about your background.
Our class meets in CMC 319 during period 4A (MW 12:30PM-1:40PM, F 1:10PM-2:10PM). The basic materials are
Here's how you get in contact with me:
Dr. Joshua R. Davis (most people call me Josh)
E-mail: jjddaavviiss@@ccaarrlleettoonn..eedduu
Office: CMC 327, x4482
Office hours: M 5A (1:40-2:30), T 2C (10:00-11:00), W 3A (11:00-12:00). You can also make an appointment; simply pick a free time from my weekly schedule and e-mail me. You can also talk to me after class.
Final grades (A, B, C, etc.) are assigned according to an approximate curving process. By this I mean that there are no predetermined percentages (90%, 80%, 70%, etc.) required for specific grades. The following elements contribute to the final grade.
You are expected to spend at least 10 hours per week on this course outside class. Some students need to spend more than 10 hours. If you spend less, then your education is suboptimal; we should discuss ways to enrich it.
You are strongly encouraged to work with others on all homework. Work together to figure out the problems/programs, but write/type them up separately, in your own words. You may not copy someone else's work or allow them to copy yours. Presenting someone else's work as your own is an act of academic dishonesty.
Writing is not just for English majors. Written and oral communication skills are essential to every academic discipline; they are also highly prized by employers. It is in this course that you (begin to) learn to communicate like a computer scientist. Your written work is evaluated both for correctness and for presentation.
I strongly encourage you to adopt the following operating procedure. Work with others to figure out the problems on scratch paper. Then, on your own, think about how each problem's solution should be presented, and write that solution on its own sheet of paper. You may need to make revisions. Using separate sheets makes it easy to write and revise your solutions independently of each other.
Editing is even easier if you type, rather than write, your solutions. Unfortunately, most word processors are terrible at mathematical notation. For this reason many computer scientists (and mathematicians and physicists) use the typesetting system LaTeX. I'm happy to help you get started with it; just ask. Once you overcome the learning curve, which is not high, typing can be much more efficient than writing — just as it is for an English paper.
How much work should you show? The answer is simple: Compose your solutions as if the intended audience is your fellow students. By doing so, you show enough detail that your grader can ascertain whether you yourself understand the material. Your solutions should also be self-explanatory. In short, if a classmate were to read one of your solutions, then she or he should be able to understand what the problem was and how you solved it.
Staple your solutions into a single packet, in the order they were assigned. Packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Staple your packet. Your packet? Staple it.
Depending on time constraints in any given week, perhaps not all of your homework is graded; in order to ensure full credit, do all of the assigned problems.
During the term, you have one free pass to hand in an assignment late. Here is how you activate it. Instead of handing in the assignment, send me e-mail (by the due date) declaring that you are using your late pass and proposing a new due date. If the due date is extended by only one class meeting, then no explanation is necessary; if you need longer, then convince me. Use your free pass wisely; once you have used it, no late assignments are accepted, except in extreme circumstances that are truly beyond your control.
If some medical condition affects your participation in class or your taking of exams, let me know in the first week of class. You may need to make official arrangements with the Office of Disability Services.
| Date | Day | Reading | Topic | Homework | Notes |
|---|---|---|---|---|---|
| M 09/15 | 01 | 1.1 | propositional logic | Homework 1 (due Tue 09/16, 5:00PM) | |
| W 09/17 | 02 | 1.2, 1.3 | prepositional logic | Assignment 2 (due Wed Day 05) | |
| F 09/19 | 03 | 1.4, 1.5 | proofs | ||
| M 09/22 | 04 | 1.6, 1.7 | proofs | Assignment 3 (due Wed Day 08) | |
| W 09/24 | 05 | proofs, Hamming codes | 202.hamming.nb | ||
| F 09/26 | 06 | 3.4 | divisibility, modular arithmetic | ||
| M 09/29 | 07 | 3.8 | matrices | ||
| W 10/01 | 08 | 3.5 | Hamming again, primes | ||
| F 10/03 | 09 | 3.2 | growth of functions | Assignment 4 (due Wed Day 11) | |
| M 10/06 | 10 | 3.6 | integer algorithms | ||
| W 10/08 | 11 | 3.7 | RSA cryptosystem | Assignment 5 (due Fri Day 15) | |
| F 10/10 | 12 | 4.1 | induction | ||
| M 10/13 | 13 | 4.2, 4.3 | strong and structural induction | ||
| W 10/15 | 14 | midterm exam | |||
| F 10/17 | 15 | 2.1, 2.2 | sets | ||
| M 10/20 | midterm break | ||||
| W 10/22 | 16 | 2.3 | functions | Assignment 6 (due Wed Day 19) | |
| F 10/24 | 17 | 5.1, 5.2 | counting | ||
| M 10/27 | 18 | 5.3 | permutations and combinations | ||
| W 10/29 | 19 | 5.4, 5.5 | more combinatorics | Assignment 7 (due Wed Day 22) | |
| F 10/31 | 20 | 7.1 | recurrence relations | ||
| M 11/03 | 21 | 7.2 | recurrence relations | ||
| W 11/05 | 22 | 7.3, 6.1 | divide-and-conquer, probability | ||
| F 11/07 | 23 | 6.2 | probability | Assignment 8 (due Fri Day 26) | |
| M 11/10 | 24 | 6.3 | Bayes' theorem | ||
| W 11/12 | 25 | 6.4 | expected value | ||
| F 11/14 | 26 | 9.1, 9.2 | graphs | Assignment 9 (due Wed Day 28) | |
| M 11/17 | 27 | 9.3, 9.4 | paths | 202.graphs.nb | |
| W 11/19 | 28 | 9.5 | Eulerian, Hamiltonian circuits | ||
| M 11/24 | final exam 8:30AM-11:00AM | ||||