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

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.

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

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.

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.

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/1819
Homework 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/2223

Course Plan

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

Recitations

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