2013 March 31,

Math of Computer Science

CS 202-00, Carleton College, Winter 2013

Prof. Joshua R. Davis, , Goodsell 204, x4473


When you first study computer science, you focus on creating algorithms and getting the computer to execute them (CS 111). As you continue studying CS, you might practice creating algorithms more (CS 201), or you might delve into how the computer hardware executes those algorithms (CS 208). If you've worked hard, you emerge from this study with a deep understanding of how to solve problems through programming. That's great, but you probably still can't solve these common computing problems:

Good solutions to these problems require more than just algorithmic thinking and programming knowledge. They require math. In this course, we learn a variety of neat mathematical concepts and facts, that computer scientists use routinely. More importantly, we learn how to prove new facts, so that we are not merely users of math, but creators of math. That's a key step in becoming a computer scientist. The official prerequisites for this course are CS 111 and Math 111 (Calculus I), but you will find that this course is extremely different both of those courses.

Our class meets in CMC 319 during period 5A (MW 1:50-3:00, F 2:20-3:20). My office hours are MWF 6A and Thu 2:20-3:20. You can also schedule an appointment with me. The course materials are as follows.


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 find yourself spending more than, say, 15 hours, then talk to me.

Standards for Work

You are encouraged to work with others on all assignments. Work together to figure out the proofs/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. If Carleton College finds you to not to have upheld its Academic Honesty standards in this course, then you will receive an F for this course.

Writing is not just for English and history majors. Written and oral communication skills are essential to every academic discipline, and are highly prized by employers. In this course, your written work is evaluated both for correctness and for presentation. I do not require you to learn the typesetting system LaTeX, but you may find that it speeds up your homework writing. Talk to me if you're interested.

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. 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.

When handing in multiple pages of paper, staple them into a single packet, in the correct order. Packets that are not stapled are unacceptable. I will not accept packets that are not stapled. Is there a stapler in the classroom? Often not, so staple ahead of time. Is a paper clip okay? No.

Computer files should be submitted in plain text (.txt), PDF (.pdf), or Python (.py) formats only, unless otherwise specified. In particular, Microsoft Word documents are unacceptable. Fortunately, you can "print" any document to PDF easily.

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.

Special Accommodations

During the term, you have one free pass to hand in an assignment late. Instead of handing in the assignment, send me e-mail, by the due date, declaring that you are using your late pass. You assignment is now due when the next assignment is due. When you submit your late work, mark it "Late Pass Used" prominently at the top. Once you have used your late pass, 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.


Because of our textbook situation and my desire to customize our schedule to the students, this schedule has been filled in as we've gone along. Readings marked "DLN" are from David Liben-Nowell's book, while those marked "KHR" are from Kenneth H. Rosen's book.

F 1/0401introductionAssignment A 01
M 1/0702propositional logicAssignment B04DLN 3.1-3.3
W 1/0903predicate logic3.114, 3.126, 3.135, 3.156, 3.158, 3.19007DLN 3.4-3.7
F 1/1104proofs4.199, 4.211, 4.213, 4.240, 4.241, 4.24807DLN 4.1-4.3
M 1/1405inductionAssignment E07DLN 5.1-5.2
W 1/1606in-class workAssignment F: problems B, D, E only10
F 1/1807structural inductionAssignment G10DLN 5.4
M 1/2108asymptoticsQuiz09DLN 6.1-6.3
W 1/2309algorithm analysisAssignment H12
F 1/2510recurrence relationsDLN 6.4
M 1/2811matrices, error correctionfinish lab (A-N)15DLN 2.4.2Matrices
W 1/3012error correctionDLN 4.7
F 2/0113EXAM A
W 2/0614number theory4.1: 4, 13ab, 30, 35, 37, 38, 4118KHR 4.1
F 2/0815number theory4.2: 2c, 4c, 21a, 31, 3318KHR 4.2
M 2/1116number theoryAssignment L18KHR 4.3
W 2/1317number theory
F 2/1518RSA cryptosystemAssignment M21KHR 4.6from Ars Technica
M 2/1819combinatoricsAssignment N21DLN 9.1-9.2
W 2/2020combinatoricsAssignment O24DLN 9.3-9.4
F 2/2221probability7.1: 18, 23, 24b, 37, 4024KHR 7.1
M 2/2522probability7.2: 3, 5, 13, 1624KHR 7.2
W 2/2723Bayesian spam filteringAssignment R26KHR 7.3
F 3/0124expected value, game theoryAssignment S26KHR 7.4
M 3/0425graphsDLN 11.1-11.2
W 3/0626graphsAssignment T28DLN 11.3
F 3/0827EXAM B
M 3/1128graphsAssignment UDLN 11.5Path Finding
S 3/16FINAL EXAM 8:30AM-11:00AM