Spring 2019 - 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
Drop-In Hours TBD

Graduate Teaching Assistants (GTAs)

Alex Steiger
LSRC D208
Email: asteiger@cs.duke.edu
Office Hours on Mondays at 4 - 6 pm in Physics 130

Kevin Sun
LSRC D227
Email: ksun@cs.duke.edu
Office Hours on Mondays at 5 - 7 pm in Physics 130

Erin Taylor
North 001
Email: ect15@cs.duke.edu
Office Hours on Sundays at 5 - 7 pm in Physics 150

Undergraduate Teaching Assistants (UTAs)

Noam Bendavid
Email: noam.bendavid@duke.edu
Office Hours on Tuesdays at 6 - 7 pm in Physics 128

Glenn Huang
Email: glenn.huang@duke.edu
Office Hours on Wednesdays at 6 - 7 pm in Physics 128 and Sundays at 6 - 7 pm in Physics 150

Chentian Jiang
Email: chentian.jiang@duke.edu
Office Hours on Thursdays at 5 - 6 pm in Physics 128

Muhammad Murtaza
Email: muhammad.murtaza.mubin@duke.edu
Office Hours on Fridays at 5 - 7 pm in Physics 128

Rahul Ramesh
Email: rahul.ramesh@duke.edu
Office Hours on Thursdays at 6 - 7 pm in Physics 128 and Sundays at 5 - 6 pm in Physics 150

Vinit Ranjan
Email: vinit.ranjan@duke.edu
Office Hours on Saturdays at 6 - 7 pm in Physics 128 and Mondays at 6 - 7 pm in Physics 130

NOTE: We will use Piazza for all correspondence and discussions related to the course. If you have a question about the course material or want to initiate a discussion, post it on Piazza allowing the entire class to view and participate in it. If you want to contact the course staff only, create a private post on Piazza that is visible only to the relevant course staff.

Lectures

French Science 2231 on Mondays and Wednesdays at 1:25 - 2:40 pm

Recitations

Section 01D: Physics 047 on Fridays at 1:25 - 2:40 pm (Alex)
Section 02D: Allen 318 on Fridays at 10:05 - 11:20 am (Alex)
Section 03D: Allen 103 on Fridays at 1:25 - 2:40 pm (Kevin)
Section 04D: Allen 318 on Fridays at 11:45 - 1:00 pm (Kevin)
Section 05D: Physics 235 on Fridays at 1:25 - 2:40 pm (Erin)
Section 06D: Social Sciences 105 on Fridays at 3:05 - 4:20 pm (Alex)
Section 07D: LSRC A156 on Fridays at 4:40 - 5:55 pm (Erin)

Office Hours

Sunday: 5:00 - 7:00 pm in Physics 150 (Erin 5-7, Rahul 5-6, Glenn 6-7)
Monday: 3:00 - 4:00 pm in LSRC D203 (Debmalya), 4:00 - 7:00 pm in Physics 130 (Alex 4-6, Kevin 5-7, Vinit 6-7)
Tuesday: 6:00 - 7:00 pm in Physics 128 (Noam)
Wednesday: 6:00 - 7:00 pm in Physics 128 (Glenn)
Thursday: 5:00 - 7:00 pm in Physics 128 (Chentian 5-6, Rahul 6-7)
Friday: 5:00 - 7:00 pm in Physics 128 (Muhammad)
Saturday: 6:00 - 7:00 pm in Physics 128 (Vinit)

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

Course Plan

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

Recitations

DiscussionDateTopicDiscussion Notes
1 Fr 1/11 (Dis)proving implications Notes
2 Fr 1/18 More proofs and the WOP Notes
3 Fr 1/25 More WOP and prop. logic Notes, Equivalences
4 Fr 2/1 Quantifiers and set equivalences Notes, Equivalences
5 Fr 2/8 Relations Notes
6 Fr 2/15 More relations and induction Notes
7 Fr 2/22 Strong induction Notes
8 Fr 3/1 Structural induction Notes
9 Fr 3/8 Matchings and connectivity Notes
Fr 3/15 Spring break: no recitation
10 Fr 3/22 Connectivity in digraphs Notes
11 Fr 3/29 DFS and infinity Notes
12 Fr 4/5 Sums and uncountability Notes
13 Fr 4/12 Counting and probability Notes
14 Fr 4/19 Conditional probability Notes