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

Drop-In Hours TBD

Graduate Teaching Assistants (GTAs)

Alex Steiger

LSRC D208

Email: asteiger@cs.duke.edu

Office Hours on

Kevin Sun

LSRC D227

Email: ksun@cs.duke.edu

Office Hours on

Erin Taylor

North 001

Email: ect15@cs.duke.edu

Office Hours on

Undergraduate Teaching Assistants (UTAs)

Noam Bendavid

Email: noam.bendavid@duke.edu

Office Hours on

Glenn Huang

Email: glenn.huang@duke.edu

Office Hours on

Chentian Jiang

Email: chentian.jiang@duke.edu

Office Hours on

Muhammad Murtaza

Email: muhammad.murtaza.mubin@duke.edu

Office Hours on

Rahul Ramesh

Email: rahul.ramesh@duke.edu

Office Hours on

Vinit Ranjan

Email: vinit.ranjan@duke.edu

Office Hours on

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.

Section 02D:

Section 03D:

Section 04D:

Section 05D:

Section 06D:

Section 07D:

Monday:

Tuesday:

Wednesday:

Thursday:

Friday:

Saturday:

- 4/19: The Homework 10 deadline has been extended from 4/22 to 4/23.
- 3/8: The Homework 6 deadline has been extended from 3/18 to 3/19.
- 2/16: The Midterm grading policy has been posted under "Grading".
- 1/22: Recitations for Section 03D will meet in Allen 103 from now on.
- 1/16: There will be no office hours on Monday, January 21, due to the MLK holiday.
- 1/8: Office hours will begin on Monday, January 14.
- 1/8: If you are not signed up on Sakai, Gradescope, or Piazza, please contact a graduate teaching assistant ASAP.

- 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): 35%
- 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.**Schedule:**

Homework 1 (Handout, Code) released on 1/14 due on 1/28 Homework 2 (Handout) released on 1/28 due on 2/4 Homework 3 (Handout, Code) released on 2/4 due on 2/11 Homework 4 (Handout, Code) released on 2/11 due on 2/25 Homework 5 (Handout) released on 2/25 due on 3/4 Homework 6 (Handout, Code) released on 3/4 due on 3/ ~~18~~19Homework 7 (Handout) released on 3/18 due on 3/25 Homework 8 (Handout, Code) released on 3/25 due on 4/1 Homework 9 (Handout) released on 4/1 due on 4/8 Homework 10 (Handout) released on 4/8 due on 4/ ~~22~~23

Lecture | Date | Topic | Scribe Notes | References |

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 |

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