CS 202
Fall 2016
Mathematics of Computer Science
Basic Information
- Instructor: Jed Yang, Center for Math & Computing 324,
- Office hours: Monday 16:20–17:20 (in CMC 306), Thursday 14:35–15:35, Friday 13:00–14:00; or by appointment
- Lectures: 3a (MW 11:10–12:20, F 12:00–13:00) in Center for Math & Computing 301
- Course website: http://cs.carleton.edu/faculty/jyang/cs202.16f/
Course Information
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.- Textbook: Discrete Mathematics for Computer Science, David Liben-Nowell, preliminary edition 2016.
Grading
There will be 3 midterm exams and no final exam.Your grade will be determined by a weighted arithmetic mean of component scores:
Homework | Midterm 1 | Midterm 2 | Midterm 3 | Participation |
---|---|---|---|---|
35% | 20% | 20% | 20% | 5% |
Examinations
The midterm exams will be administered during regularly scheduled class time.Missing an exam is permitted only for the most compelling reasons. You should obtain my permission in advance to miss an exam. Otherwise, you will be given a 0. If you are excused from taking an exam, you will either be given an oral exam or your other exam scores will be prorated.
Tentative exam dates:
- Midterm 1, Wednesday, October 05.
- Midterm 2, Wednesday, October 26.
- Midterm 3, Wednesday, November 16.
Homework
Homework will be posted and collected electronically on Moodle.Solutions must be typeset with LaTeX. Some helpful links:
- (optional) homework template: hw-template.tex
- getting started: a short introduction | a tutorial [MIT] | more detailed tutorials | Carleton LaTeX Workshop
- reference: the not so short introduction | a reference guide [Cambridge] | the LaTeX Wikibook
- tools: a symbol finder | a table editor
- cloud-based editors: ShareLaTeX | Overleaf (formerly writeLaTeX)
Calendar
To be updated throughout the term; tentative and subject to change.Day | Date | Agenda | Reading |
---|---|---|---|
September | |||
01 | 12 Mon | course overview; propositional logic | DLN §1, §§3.1–3.2 |
02 | 14 Wed | truth tables, logical equivalence | DLN §3.3 |
03 | 16 Fri | Sheffer stroke, predicate logic | DLN §3.4 |
04 | 19 Mon | quantifiers | DLN §3.5, §2.6 |
05 | 21 Wed | games | DLN §§2.1–2.2 |
06 | 23 Fri | proofs | DLN §4.1, §4.3 |
07 | 26 Mon | sets, sequences, functions | DLN §2.3 |
08 | 28 Wed | error-correcting codes | DLN §4.2, §4.4 |
09 | 30 Fri | matrices, optimality of Hamming code | DLN §2.4, §4.5 |
October | |||
10 | 03 Mon | polynomials, secret sharing, Reed–Solomon codes | DLN §2.5, p.418 |
11 | 05 Wed |
Midterm 1 | DLN chapters 1–4 |
12 | 07 Fri | induction | DLN §§5.1–5.2 |
13 | 10 Mon | strong induction | DLN §5.3 |
14 | 12 Wed | triangulations | |
15 | 14 Fri | linear recurrences | |
17 Mon | (midterm break; no class) | ||
16 | 19 Wed | asymptotics | DLN §§6.1–6.2 |
17 | 21 Fri | analysis of (recursive) algorithms, Master Method | DLN §§6.3–6.5 |
18 | 24 Mon | counting | DLN §§9.1–9.2 |
19 | 26 Wed |
Midterm 2 | DLN chapters 5–6 |
20 | 28 Fri | binomial coefficients | DLN §9.4 |
21 | 31 Mon | other counting principles | DLN §9.3 |
November | |||
22 | 02 Wed | probability, conditional probability | DLN §§10.1–10.2 |
23 | 04 Fri | random variables, expectation | DLN §§10.3–10.4 |
24 | 07 Mon | number theory: modular arithmetic, Euclidean algorithm | DLN §§7.1–7.3 |
25 | 09 Wed | cryptography: RSA encryption | DLN §§7.4–7.5 |
26 | 11 Fri | graphs, connectivity, trees | DLN §§11.1–11.4 |
27 | 14 Mon | matchings | |
28 | 16 Wed |
Midterm 3 | DLN chapters 7, 9–11 |