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

***Instructor office hours are by appointment from Mar 23 onward. Please send an email to Debmalya and Kate for scheduling an appointment.

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

Jingxian Huang
Email: jh654@cs.duke.edu
Office Hours on Monday from 6 - 8 pm in Physics 205

Kevin Sun
Email: ksun@cs.duke.edu
Office Hours on Monday from 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

***Due to the changes in Duke policy in light of COVID 19, lectures are moving online from Mar 23. Lectures will be delivered in two parts: (a) lecture videos that will be recorded and uploaded on Sakai, and (b) lecture discussions at the regular class meeting times via Zoom meetings that can be accessed via the Sakai course site. The latter will also be recorded and the recordings will be accessible via Sakai.

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 Hours 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-9:00 pm in Physics 205 (Grace Llewellyn 6 - 7; Jingxian Huang 6 - 8; Kevin Sun 7 - 9)
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

***The weights below have changed because of the cancellation of the second midterm.

Homework

Tentative Course Plan

LectureDateTopicScribe NotesReferences
Mathematical Logic and Proofs Notes
1 We 1/8 Welcome. Introduction to Proofs and Logic. LLM: 3.1-3.5
2 Mo 1/13 Introduction to Propositional Logic. Propositional Operators. The Algebra of Logic. LLM: 3.6, 8.4
3 We 1/15 Normal Forms: CNF, DNF. Introduction to Predicate Logic. Quantifiers and Predicates. LLM: 1.1-1.4
Mo 1/20 Martin Luther King, Jr. Holiday: No class
4 Wd 1/22 Basic Proof Techniques. Rules of Inference. Contrapositives and Proof by Contradiction. LLM: 1.5, 1.8
5 Mo 1/27 Proof Techniques (cont'd): Implications and Equivalences. LLM: 1.6
6 We 1/29 Proof Techniques (cont'd): Proof by Cases. LLM: 1.7
7 Mo 2/3 Introduction to Mathematical Induction. Weak Induction. LLM: 5.1
8 We 2/5 Strong Induction. LLM: 5.2
9 Mo 2/10 Strong Induction (cont'd). LLM: 5.2
10 We 2/12 Structural Induction. LLM: 7.1,7.6
Set Theory Notes
11 Mo 2/17 Sets. Basic Operations on Sets. LLM: 4.1-4.2
We 2/19 Midterm 1: Lectures 1-11
12 Mo 2/24 Relations and Functions. LLM: 4.3-4.4, 10.11
13 We 2/26 Properties of Relations on Sets.
14 Mo 3/2 Equivalence Relations and Equivalence Classes. LLM: 10.10-10.11
15 We 3/4 Partially and Totally Ordered Sets. LLM: 10.6
Mo 3/9
We 3/11
Mo 3/16
We 3/18
Spring break: No class
The rest of the lectures will be delivered via online tools.
Graph Theory Notes
16 Mo 3/23 Introduction to Graphs. Important Classes of Graphs. Matchings. LLM: 12.1-12.5
17 We 3/25 Connectivity. Coloring. LLM: 12.6-12.8
18 Mo 3/30 Applications of Graphs. LLM: 12.11
19 We 4/1 Acyclic graphs: Trees, Forests, and Directed Acyclic Graphs. LLM: 10.1-10.2, 10.5
20 Mo 4/6 Strongly Connected Components. LLM: 10.1-10.2, 10.5
23 We 4/8 Applications of Directed Graphs. Inductive Proofs on Graphs.
Probability Notes
24 Mo 4/13 Sample spaces and Events. Conditional Probability. Bayes rule. Union bound. Inclusion Exclusion Principle. Independent Events. LLM: 17, 18.1-18.5, 18.7-18.8
25 We 4/15 Random Variables: Discrete and Continuous. Independence. Joint Distribution. Conditional Distribution. LLM: 19.1-19.3
26 Mo 4/20 Expectation. Variance and Standard Deviation. LLM: 19.4-19.6, 20.3
27 We 4/22 Popular Distributions: Binomial. Poisson. Normal.
Fr 5/1 Final Exam: All Lectures
Exam will be released at 12:01 am and will be due at 11:59 pm Durham time. (The exam will be designed as a 3 hr exam but will not be timed.)
Online. Open book, open notes.

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 Predicates and Proofs Notes
4 Fr 1/31 Proving Properties of Algorithms Notes
5 Fr 2/7 Induction Notes
6 Fr 2/14 More induction Notes
7 Fr 2/21 Set Basics Notes
8 Fr 2/28 Relations and Functions Notes
9 Fr 3/6 Partial and Total Orders Notes
Fr 3/13 Spring break: no recitation
10 Fr 3/20 Extraordinary Circumstances: no recitation
11 Fr 3/27 Graphs Notes
12 Fr 4/3 Graphs Contd. Notes
13 Fr 4/10 Induction on Graphs and DFS Notes
14 Fr 4/17 Probability Notes