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

The due date for HW8 has been extended to April 15.
The course plan has been updated to reflect the new schedule. This course plan is tentative, and is subject to (expectedly minor) changes.
Instructor office hours are by appointment. Please send email to Debmalya and Kate to schedule.
Midterm 2 is cancelled. The final exam will be open book, open notes. Other logistical details, including new grading weights, will be shared soon.
The due date for HW6A has been extended to March 30.
The due date for HW6B has been extended to March 30.
In accordance with Duke policy, all aspects of the course are moving online. This supercedes any information about location provided on this webpage.
There were typos in HW6A. Please download the updated version.

Synopsis

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

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

Resources

Lecture notes will be uploaded on the course website after every lecture.
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.

Grading

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

Homework Assignments (problem sets): 35%
***NEW***Homework Assignment (programming): 15%
Midterm exam: 15%
Class Participation (only includes in-person lectures and discussion sessions): 5%
Final exam: 30%
The midterm is an in-class closed-book exam. The final exam is a take-home, open-book exam.
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.

Homework

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 1A	released on 1/13	due on 1/27
Homework 1B	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 4A	released on 2/10	due on 2/17
Homework 4B	released on 2/16	due on 2/24
Homework 5	released on 2/24	due on 3/2
Homework 6A	released on 3/2	due on 3/30
Homework 6B	released on 3/6	due on 3/30
Homework 7	released on 3/30	due on 4/6
Homework 8	released on 4/6	due on 4/15

Coding Assignment

Coding Assignment	released on 4/6	due on 4/22
Pair.java (helper class)
Problem 1 skeleton
Problem 2 skeleton
Problem 3 skeleton
Problem 4 skeleton

Tentative Course Plan

Lecture	Date	Topic	Scribe Notes	References
		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

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	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