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.

We will generally follow the textbook, tentatively in this order of chapters: 3, 4 & 2, 5, 6, 9, 10, 7, and (if there's time) 11.

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