,

CPS230: Discrete Math for Computer Science

Instructor: Kamesh Munagala

    Tu-Th 1:25 - 2:40 @ Gross 107

Spring 2018


Overview

Informal Course Description

Computer Science requires a somewhat different type of math than what you have learnt so far. Classical continuous math, like calculus or differential equations is based on recipes -- once you learn the recipes, the entire exercise is to apply them correctly. In contrast, computer science can be viewed as problem solving with discrete objects -- bits, integers, sets, and graphs. This requires a different style of creative thinking, where the goal often is to come up with a recipe instead of applying a known recipe. The entire goal of the course is to train you to think in this fashion.

Course Goals

At the end of the course, you should be able to:

Prerequisites

This is a math course with no programming component. Familiarity with math at a high school level, and with computer programming at the level of CompSci 101 is required.


Logistics

Course Calendar 



Grading 

Other Logistics


Reading Materials

Textbook

There will be two textbooks for the course. The [LLM] book is available online for free, or as a print version. The [Z] is an online textbook (zybook) which has structured reading material and exercises.  Both textbooks are optional, and you should make your own decision on buying them.

[LLM]  Mathematics for Computer Science by Eric Lehman, Tom Leighton, and Albert Meyer. 
[Z] Discrete Mathematics by Sandy Irani.    You need the Subscription Code DUKECPS230Spring2018

Other Reading Material

[JS] Fundamentals of Discrete Math for Computer Science by Tom Jenkyns and Ben Stephenson   
[Ro] Discrete Mathematics and its Applications by Kenneth Rosen


Lecture Schedule


Lecture NumberDateTopicReading Assignment from {Z]
For maximum gains, please
complete before coming to lecture

Readings from {LLM]
Proofs, Logic, and Sets
1
Jan. 11
Course Organization
Basic Proof Techniques


Chapter 1

Chapter 1

2
Jan. 16

Jan 18
SNOW DAY
3
Jan. 23
Propositional Logic

Chapter 2

Chapter 3
4
Jan. 25
First order Logic
5
Jan. 30
Set Theory
Chapter 3
Chapter 4.1, 4.3
6
Feb. 1
Functions, Sequences, Summations

Chapters 4,5
Chapter 4.2, 14
7
Feb. 6
Mathematical Induction Chapter 2, 5
8
Feb. 8
Strong Induction,
Infinite sets

Chapter 8
9
Feb. 13
MIDTERM 1 (Lectures 1 - 7)
Computation
10 Feb. 15
Diagonalization, Halting Problem

Chapter 8
11
Feb. 20
Approximate Summation, Asymptotics
Chapter 6
Chapter 14
12
Feb. 22
Recursion and Recurrence Relations



Chapter 7
Chapter 22
13
Feb. 27
Structural Induction Chapter 6
Combinatorics and Probability
14
Mar. 1
Basic counting rules, Counting Subsets
Chapter 8
Chapter 15
15
Mar. 6
Inclusion-Exclusion, Pigeonhole Principle Chapter 9
Chapter 16
16
Mar. 8
MIDTERM 2 (Lectures 10 - 15)
SPRING BREAK
17
Mar. 20
Events and Sample Spaces



Chapter 10
Chapter 17
Tomasi's Notes
18
Mar. 22
Conditional Probability, Independence
Bayes' rule, Monty Hall Problem
Chapter 18
19
Mar. 27
Random Variables, Expectation
Bernoulli Trials
Chapter 19
Graph Theory
20
Mar. 29
Basic terminology and applications


Chapter 11



Chapter 12
21
Apr. 3
Matchings and Hall's theorem
22
Apr. 5
Graph Isomorphism, Colorings
23
Apr. 10
Connectivity, Eulerian and Hamiltonian paths
24
Apr. 12
Trees, Tree traversal, Spanning trees
Chapter 12
25
Apr. 17
MIDTERM 3 (Lectures 15 - 23)
Applications
26
Apr. 19
(slack)
Opinion polls and estimation
Variance and Chebychev's Inequality
Weak Law of Large Numbers

Chapter 20
27
Apr. 24
(slack)
Ranking the Web
Markov Chains and Random Walks

Lecture Notes
Chapter 21
28
Apr. 26
(slack)
Non-mandatory Review Session



May 3, 9 AM
FINAL EXAM   (French Science 2231)