Course Description and Learning Objectives

This course develops the mathematical foundations of computer science that are not calculus-based. It covers basic set theory, logic, mathematical proof techniques, and a selection of discrete mathematics topics such as combinatorics (counting), discrete probability, and graph theory. The learning objectives of the course are the following

Learn how to read and write precise statements using mathematical notation.
Learn certain methods to prove mathematical statements, and learning to apply them.
Learn certain basic mathematical concepts arising in counting, probability, and graph theory, and also learn how to apply them.
Learn how the aforementioned goals are relevant to computer science.

What I know after taking CS 30

Logistics

Prerequisites: CS10; Read: "what should I be knowing before CS 30?"
Class timing: 10hour (M-W-F, 10:10 - 11:15, X-hour on Th, 12:15-1:05)
Class venue: Cummings 200
Discussions: via Ed Discussion
Work Submissions: Canvas, Gradescope
Personnel & Office hours: Instruction Team & Office Hours
Policies: Policies
Textbook: No particular textbook needed. Lecture notes and plenty of practice problems (with solutions) will be posted.
Read these: Best Practices ; Honor Principle & CS 30

Evaluation

Drill Exercise Sets: 15%
Problem Sets: 35%
Two in-class + take home Midterms: 15% + 15%
One in-class Final: 20%
Details: Deliverables and Evaluation

Tentative Weekly Schedule
Date	Lecture Material	Associated Exercises/Problems	Other info
4 Jan (Wed)	Introduction, Sets	Lec 1 Drill Quiz; UGP 1, Problems 1 to 5 Problem Set 1, Problem 1
5 Jan (X)	catch up (already?!)
6 Jan (Fri)	Functions	Lec 2 Drill Quiz; UGP 1, Problems 6 to 10 Problem Set 1, Problem 2
9 Jan (Mon)	Logic I: Propositional Logic Supplement: An Application of Propositional Logic	Lec 3 Drill Quiz; UGP 1, Problems 11 to 13 Problem Set 1, Problem 3a Extra Credit Problem Set 1	PSet 0 due
11 Jan (Wed)	Logic II: Predicate Logic	Lec 4 Drill Quiz; UGP 1, Problems 14 to 15 Problem Set 1, Problem 3b
12 Jan (X)	X-ercise hour, ECSC 116	X-hour (1/12) exercise set
13 Jan (Fri)	Proofs I: Contradiction	Lec 5 Drill PDF submission UGP 2, Problems 1 to 5 Problem Set 2, Problem 1 Extra Credit Problem Set 2, Prob 1
16 Jan (Mon)	MLK Day, no class		Pset 1 due
18 Jan (Wed)	Proofs II: Induction	Lecture 6 + 7 Drill PDF, Problem 1 UGP 2, Problems 6 to 8 Problem Set 2, Problem 2a, 3a
19 Jan (X)	Proofs III: Strong Induction	Lecture 6 + 7 Drill PDF, Problem 2 UGP 2, Problems 9 to 16 Problem Set 2, Problem 2b, 3b Extra Credit Problem Set 2, Prob 2
20 Jan (Fri)	Proofs IV: Proving Programs Correct		Supplementary videos 1. Strengthening Ind. Hypo. 2. Minimal Counterexample view of Induction
23 Jan (Mon)	Comb I: Product & Sum Principle	Lecture 10 Quiz UGP 3, Problems 1 to 7 Problem Set 3, Problem 1, 2b, 2c
25 Jan (Wed)	Comb II: Bijections & Division Rule	UGP 3, Problem 8 to 10 Problem Set 3, Problem 2a, 3	Pset 2 due
26 Jan (X)	X-ercise hour, ECSC 042	X-hour (1/26) exercise set
27 Jan (Fri)	Comb III: Four Fold Formula	Lecture 11 + 12 Quiz Problem Set 4, Problem 1 UGP 3, Problems 11-13
30 Jan (Mon)	MT 1 Review Session		Midterm 1 In-class component: 6:30p - 8:30p, Cummings 100 Take home: due 31st, Jan, 11:59p
1 Feb (Wed)	Comb IV: Pascal's Idenity	Lecture 13 drill coding exercise Problem Set 4, Problem 2 UGP 3, Problems 14-21
2 Feb (X)	converted to office hour @ECSC110
3 Feb (Fri)	Comb V: Binomial Expansion	Problem Set 4, Problem 2 UGP 3, Problems 14-21	A videoshowing another "combinatorial identity". This is a problem from the UGP
6 Feb (Mon)	Prob I: Basics	Lecture 15 Quiz Problem Set 4, Problem 3 UGP 4, Problems 1-6	Pset 3 due
8 Feb (Wed)	Prob II: Cond. Prob, Independence	Lecture 16 Quiz UGP 4, Problems 7-11 Problem Set 5, Problem 2
9 Feb (X)	X-ercise Hour, ECSC 042	X-hour (2/9) exercise set
10 Feb (Fri)	Prob III: Bayes Rule	Lecture 17 Drill Quiz UGP 4, Problems 12-16 Problem Set 5, Problem 1	Supplement notes on conditional independence, and something called the "Naive Bayes" assumption.
13 Feb (Mon)	Probability IV: Random Variables	Lecture 18 Drill Quiz UGP 4, Problems 17-21 Problem Set 5, Problem 3	Pset 4 due
15 Feb (Wed)	Probability V: Expectation	Lecture 19 Drill Quiz UGP 4, Problems 17-21 Problem Set 5, Problem 3
16 Feb (X)	X-ercise hour (ECSC 042)	X-hour (2/16) exercise set
17 Feb (Fri)	Probability VI: Expectation	Lecture 19 Drill Quiz (No Lec 20 Drill) UGP 4, Problems 17-21 Problem Set 5, Problem 3 Extra Credit Problem Set 5
Probability Supplement Material	Expectation vs Shape, Markov (video) Variance (video)
20 Feb (Mon)	Graphs I: Degrees, Handshaking	Lecture 21 Drill Quiz UGP 5,Problems 1 - 5 Problem Set 6, Problem 1,2
22 Feb (Wed)	Graphs II: Connectivity	Lecture 22 Drill Quiz UGP 5,Problems 6 - 9 Extra Credit Problem Set 6	PSet 5 due
23 Feb (X)	converted to office hour @ECSC110
24 Feb (Fri)	Graphs III: Trees	UGP 5,Problems 10 - 13 Problem Set 6, Problem 2, 3
26 Feb (Sun)	Review Session for MT2 (1pm - 2pm, Cummings 200)	Sample MT2 (solutions)
27 Feb (Mon)	Graphs IV: Bipartite Graphs	UGP 5,Problems 14 - 17	MT2 [Syllabus: Comb & Prob., PS3,4,5] In-class: 6:30p - 8:30p, Cummings 100 Take-home: Due 2/28, 11:59p
1 Mar (Wed)	Graphs V: Matchings & Hall's Theorem	UGP 5,Problems 14 - 17
2 Mar (X)	X-ercise hour, ECSC 042	X-hour (3/2) exercise set
3 Mar (Fri)	Graphs V: More on Hall's Theorem	Proof of Hall's Theorem
6 Mar (Mon)	Review + AMA	(won't be recorded)	Pset 6 due
13 Mar (Mon)			Final (in-class), Syllabus: everything done in CS30 till Feb 28th. Time: 11:30am - 2:30pm Venue: Cummings 100

Accessibility Needs

Students requesting disability-related accommodations and services for this course are required to register with Student Accessibility Services (SAS; Apply for Services webpage; student.accessibility.services@dartmouth.edu; 1-603-646-9900) and to request that an accommodation email be sent to me in advance of the need for an accommodation. Then, students should schedule a follow-up meeting with me to determine relevant details such as what role SAS or its Testing Center may play in accommodation implementation. This process works best for everyone when completed as early in the quarter as possible. If students have questions about whether they are eligible for accommodations or have concerns about the implementation of their accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

Religious Observances

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations.

Discrete Mathematics in Computer Science (WI23)