Spring 2020 - COMPSCI 230 - Discrete Mathematics for Computer Science

Overview

Discrete mathematics lays the foundation on which much of modern computer science rests.
This course is an introduction to discrete mathematics, with topics selected based on their relevance to computer science.
These include mathematical logic, set theory, mathematical induction, combinatorics, probability, and graph theory.

Course Staff

Instructor

Debmalya Panigrahi
LSRC D203
Email: debmalya@cs.duke.edu
Office Hours on Mondays at 3 - 4 pm in LSRC D203

Teaching Associate

Kate O'Hanlon
LSRC D105
Email: kate.o.hanlon@duke.edu

Graduate Teaching Assistants (GTAs)

David Fischer
Email: def27@cs.duke.edu
Office Hours on Sunday from 6 - 8 pm in Physics 205

Kevin Sun
Email: ksun@cs.duke.edu
Office Hours on Monday at 7 - 9 pm in Physics 205

Shawn Sun
Email: ss1060@cs.duke.edu
Office Hours on Sunday from 6 - 8 pm in Physics 205

Undergraduate Teaching Assistants (UTAs)

Kevin Day
Email: kevin.day@duke.edu
Office Hours on Saturday from 7 - 8 pm in Soc-Psych 248

Ethan Holland
Email: ethan.holland@duke.edu
Office Hours on Tuesday from 8 - 9 pm in Physics 205

Jerry Huang
Email: jerry.huang@duke.edu

Grace Llewellyn
Email: grace.llewellyn@duke.edu
Office Hours on Monday from 6 - 7 pm in Physics 205

Yunhao Qing
Email: yq50@duke.edu
Office Hours on Wednesday from 8 - 9 pm in Physics 205

Rahul Ramesh
Email: rahul.ramesh@duke.edu
Office Hours on Thursday from 8 - 9 pm in Physics 205

Lectures

LSRC B101 on Mondays and Wednesdays at 1:25 - 2:40 pm

Recitations

Section 01 and 02D: Perkins LINK 071 (Classroom 5) on Fridays at 10:05 - 11:20 pm David Fischer and Rahul Ramesh
Section 03D: Gray 228 on Fridays at 1:25 - 2:40 pm David Fischer and Grace Llewellyn
Section 04D: LSRC A247 103 on Fridays at 1:25 - 2:40 pm Kevin Sun and Shawn Sun
Section 05D: LSRC A155 on Fridays at 3:05 - 4:20 pm Ethan Holland and Kevin Day

Office Hours

Sun-Thurs Office Hours are in Physics 205; Saturday Office Hourse are in Soc Psych 248

Sunday: 6:00 - 8:00 pm in Physics 205 David Fischer and Shawn Sun
Monday: 3:00 - 4:00 pm in LSRC D203 Professor Panigrahi;
6:00-7:00 pm in Physics 205 Grace Llewellyn;
7:00-9:00 pm in Physics 205 Kevin Sun
Tuesday: 8:00 -9:00 pm in Physics 205 Ethan Holland
Wednesday: 8:00 - 9:00 pm in Physics 205 Yunhao Ye
Thursday: 8:00 - 9:00 pm in Physics 205 Rahul Ramesh
Friday: NONE
Saturday: 7:00 - 8:00 pm in Soc-Psych 248 Kevin Day

Announcements

Synopsis

This course covers discrete mathematics for computer science at an undergraduate level. The following is a tentative list of topics to be covered:

Resources

Lecture notes will be uploaded on the course website after every lecture.
The following book covers most of the syllabus:

Grading

Homework

Tentative Course Plan

LectureDateTopicScribe NotesReferences
Mathematical Logic and Proofs Notes
1 We 1/8 Welcome, Intro to Proofs and Logic LLM: 3.1-3.5
2 Mo 1/13 Intro to Propositional Logic: The Algebra of Logic LLM: 3.6, 8.4
3 We 1/15 CNFs, DNFs, Quantifiers, and Predicates; Goldbach's Conjecture LLM: 1.1-1.4
Mo 1/20 Martin Luther King, Jr. Holiday: No class
4 Mo 1/22 Implications and Equivalences, Basic proof techniques LLM: 1.5-1.9
5 We 1/27 The Well Ordering Principle LLM: 2.1-2.4
Sets, Maps, and Sequences
6 We 1/29 Sets and Sequences: Basic Operations LLM: 4.1-4.2
7 Mo 2/3 Relations and Functions LLM: 4.3-4.4, 10.11
8 We 2/5 Examples of Relations and Functions
9 Mo 2/10 Equivalences Relations and Partitions LLM: 10.10-10.11
10 We 2/12 Strict and Weak Partial Orders LLM: 10.6
Induction
11 Mo 2/17 Induction on numbers: Weak and Strong LLM: 5.1-5.2
We 2/19 Midterm 1: Lectures 1-11
12 Mo 2/24 Structural Induction on Strings and Trees LLM: 7.1, 7.6
Graphs and Trees
13 We 2/26 Basic properties, Special Types of Graphs, and Matchings LLM: 12.1-12.3
14 Mo 3/2 Hall's Theorem and its proof LLM: 12.5
15 We 3/4 Graph Coloring and Connectivity LLM: 12.6 - 12.8
Mo 3/9
We 3/11
Spring break: No class
16 Mo 3/16 Connectivity and Acyclic Graphs LLM: 12.8, 12.11
17 We 3/18 Directed Graphs: Strongly Connected Components and DAGs LLM: 10.1-10.2, 10.5
18 Mo 3/23 Depth-First Search and Breath-First Search
Counting
19 We 3/25 Infinite sets: counting with bijections, Countable sets LLM: 8.1
20 Mo 3/30 Infinite sets: Uncountable sets, Diagonalization, Halting Problem LLM: 8.2
21 We 4/1 Finite sets and Sequences: Sums and products, Asymptotics, Approximation by integrals LLM: 14.1-14.3, 14.5
22 Mo 4/6 Elementary Combinatorics: Permutations and Combinations LLM: 15.1-15.3, 15.5
Probability
23 We 4/8 Events, Sample spaces, Conditional Probability, and Independence LLM: Ch 17
24 Mo 4/13 More Conditional Probability, Bayes' rule LLM: 18.1-18.8
We 4/15 Midterm 2: Lectures 12-23
25 Mo 4/20 Random variables and Distribution Functions LLM: 19.1-19.5
26 We 4/22 More Random Variables, Expectation and Variance of Distributions LLM: 20.1-20.3
Fr 5/1 Final Exam: All Lectures
Time: 2:00 - 5:00 pm
Location: LSRC B101

Recitations

DiscussionDateTopicDiscussion Notes
1 Fr 1/10 Propositions, Truth Tables, and Intro to Proofs Notes
2 Fr 1/17 Propostional Algebra, Quantifiers, and Predicate Logic Notes
3 Fr 1/24 Quantifiers and set equivalences
4 Fr 1/31 More proofs and the WOP
5 Fr 2/7 Relations
6 Fr 2/14 More relations and induction
7 Fr 2/21 Strong induction
8 Fr 2/28 Structural induction
9 Fr 3/6 Matchings and connectivity
Fr 3/13 Spring break: no recitation
10 Fr 3/20 Connectivity in digraphs
11 Fr 3/27 DFS and infinity
12 Fr 4/3 Sums and uncountability
13 Fr 4/10 Counting and probability
14 Fr 4/17 Conditional probability