,

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
Chapter 8

Chapter 15
15
Mar. 6
Counting Subsets
16
Mar. 8
MIDTERM 2 (Lectures 10 - 15)
SPRING BREAK
17
Mar. 20
Inclusion-Exclusion, Pigeonhole Principle Chapter 9 Chapter 16
18
Mar. 22
Events and Sample Spaces



Chapter 10
Chapter 17
Tomasi's Notes
19
Mar. 27
Conditional Probability, Independence
Bayes' rule, Monty Hall Problem
Chapter 18
20
Mar. 29
Random Variables, Expectation
Distributions
Chapter 19
Graph Theory
21
Apr. 3
Basic terminology, Connectivity,
Isomorphism



Chapter 12



Chapter 12
22
Apr. 5
Trees, Breadth first search
Eulerian Tours
23
Apr. 10
Bipartite Graphs and Matchings
24
Apr. 12
Graph Colorings and Planarity
25
Apr. 17
MIDTERM 3 (Lectures 14-20)
26
Apr. 19
Directed Acyclic Graphs, Topological Sort Chapter 12
Chapter 12
Applications
27
Apr. 24
(slack)
Opinion polls and estimation
Variance and Chebychev's Inequality
Weak Law of Large Numbers

Chapter 20

May 3, 9 AM
FINAL EXAM