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.

Debmalya Panigrahi

LSRC D203

Email: debmalya@cs.duke.edu

Office Hours on

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

Kevin Sun

Email: ksun@cs.duke.edu

Office Hours on

Shawn Sun

Email: ss1060@cs.duke.edu

Office Hours on

Undergraduate Teaching Assistants (UTAs)

Kevin Day

Email: kevin.day@duke.edu

Office Hours on

Ethan Holland

Email: ethan.holland@duke.edu

Office Hours on

Jerry Huang

Email: jerry.huang@duke.edu

Grace Llewellyn

Email: grace.llewellyn@duke.edu

Office Hours on

Yunhao Qing

Email: yq50@duke.edu

Office Hours on

Rahul Ramesh

Email: rahul.ramesh@duke.edu

Office Hours on

Section 03D:

Section 04D:

Section 05D:

Sunday:

Monday:

Tuesday:

Wednesday:

Thursday:

Friday: NONE

Saturday:

- Introduction: Proof techniques
- Mathematical Logic: Propositional and Predicate Logic, Godel's Incompleteness Theorem
- Set theory: Sets and Sequences, Relations and Functions, Partial and Total Orders
- Mathematical Induction: Induction on numbers, Weak and Strong Induction, Structural Induction
- Graph theory: Basic properties of graphs, Acyclic graphs: DAGs, Trees, and Forests, Matchings
- Counting: Finite Sets and Sequences, Infinite Sets: Countable and Uncountable Sets
- Probability: Events and Sample Space, Conditional Probability and Independence, Random Variables and Probability Distributions

The following book covers most of the syllabus:

- [LLM] Eric Lehman, F. Thomson Leighton, and Albert R. Meyer.
*Mathematics for Computer Science*. Available online at this link.

- Homework Assignments: 35%
- Midterm exams (two): 30%
- Class Participation: 5%
- Final exam: 30%
- Both the midterms and the final exam will be in-class closed-book exams.
- Note: if you do not take a midterm but you submit a valid STINF or Dean's excuse, then your grade for that midterm will be whatever you receive on the final exam. If you do not take a midterm for any other reason, then your grade for that midterm will be 0.

**Collaborations and Honesty:**Review the detailed guidelines on collaboration.**Any violation of these guidelines will be reported without exception to the relevant authorities.**This has led to disciplinary action in the past, so better be safe than sorry.**Submission Website:**We will use Gradescope for all homework submissions.**Submission Format:**Non-programming solutions must typed and submitted in PDF format to Gradescope. It is strongly encouraged that you prepare your homework submissions in LaTeX. All programming solutions will be submitted to Gradescope as well. Specific instructions for programming solutions are to be determined and will be specified with the assignments.**Late Submissions:**Homework solutions must be submitted by 11:59 pm Durham (Eastern) time on the due date.

You will get no credit if you submit your homework after the submission deadline. A submission will be considered late if the submission website (Gradescope) marks it as late. Submissions submitted between 12:00 am and 12:29 am to Gradescope will be penalized with a 10% deduction of the final grade. A submission received after 12:30 am will not be graded and awarded no credit. This means that it is in your best interest to submit sufficiently early so that there is no possibility of the Gradescope server receiving it after 11:59 pm.

In the event that you have technical difficulties submitting to Gradescope, you may send an email to the course staff with your submission file(s) attached. The lateness penalty described above applies regardless of which platform the homework is submitted to.**Extensions:**In exceptional circumstances, you can contact the instructor**before the submission deadline**to request an extension. You should send an email to the instructor if you are requesting an extension, with a clearly stated reason for your request. Requests for extension are at the discretion of the instructor and may be refused. This implies that last-minute requests for extension are at your own peril, since the original deadline will stand if the request is denied. Only the written consent of the instructor granting an extension will be considered valid. Nobody other than the instructor (e.g., graduate or undergraduate TA) is authorized to grant an extension.**Homework Schedule:**

Homework 1 - A released on 1/13 due on 1/27 Homework 1 - B released on 1/19 due on 1/27 Homework 2 released on 1/27 due on 2/3 Homework 3 released on 2/3 due on 2/10 Homework 4 released on 2/10 due on 2/24 Homework 5 released on 2/24 due on 3/2 Homework 6 released on 3/2 due on 3/16 Homework 7 released on 3/16 due on 3/23 Homework 8 released on 3/23 due on 3/30 Homework 9 released on 3/30 due on 4/6 Homework 10 released on 4/6 due on 4/20

Lecture | Date | Topic | Scribe Notes | References |

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 |

Discussion | Date | Topic | Discussion 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 |