CS 30: Discrete Mathematics in Computer Science, Winter 2019


Schedule Policies

Course Description and Goals:
Discrete Mathematics is what one needs to talk about most problems in computer science which involves discrete objects such as bits, integers, files in a directory, nodes in a network, etc. At the end of this course, students will be comfortable understanding and using this language. The other main objective is to read, write, and understand rigorous mathematical proofs of propositions involving these discrete objects. Proofs are important not only to prove correctness of, say, your code, but also important to design new algorithms as well. Most importantly, all of these are a lot of fun!

Background Assumed:
Students should have basic knowledge about programming and should have some familiarity with basic math. You should know the concepts given here . If you have taken CS 1 and MATH 3 or equivalents, you should be fine. Talk to the instructor if you have any questions about prerequisites.


Class Times: 10 (MWF: 10:10am - 11:15am), X-hours (R: 12:15pm - 1:05pm)
Venue: Filene
Discussions: Piazza (via Canvas)
Problem Sets: Canvas
Personnel and Office Hours:

Text Book (Strongly Recommended):
David Liben-Nowell, Discrete Mathematics for Computer Science. There is an e-version which is less expensive. I will also post some reading materials online before class. At times, I will expect you to read before you come to class.

Evaluation

After almost every class there will be a drill exercise of 1 or 2 problems with a 36 hour deadline. There will be weekly problem sets. There will be two Midterms and one Final Examination which are in-class and closed-book.

Tentative Weekly Schedule

Anything in light grey is tentative which will (hopefully) become black as the classes occur. The tentative schedule breaks the quarter into roughly 8 modules, and will be covering one module per week. As seen below, we will be utilizing our X-hours a lot. If some notes links aren't working, they can be found in the "Files" section of Canvas.



Date Topics Notes Textbook Material
3rd Jan (X hour): Proofs: Direct Lec , Supp Sec 4.3.1 (Direct Proofs)
4th Jan (Fri): Proofs: Contradiction. Lec , Supp Sec 4.3.1 (Proof by Contradiction)
7th Jan (Mon): Sets and Functions: Basics Lec Sec 2.3
9th Jan (Wed): Sets and Functions: Countability Lec Sec 2.5
10th Jan (X hour): Sets and Functions: More Countability Lec Page 937 (caution: not that comprehensive)
11th Jan (Fri): Sets and Functions: Uncountability and Halting Problem Lec Sec 4.4.4
14th Jan (Mon): Number Theory: Modular Arithmetic, ModExp Lec Chap 7, pg (701--708)
16th Jan (Wed): Number Theory: GCD and Euclid's Algorithm Lec Sec 7.2.4 and Sec 7.3.2
17th Jan (X hour): Number Theory: Multiplicative Inverses, Fermat's Little Theorem Lec Sec 7.4
18th Jan (Friday): Number Theory: RSA Lec , Article , and some videos Sec 7.5
23rd Jan (Wed): Logic : Propositional Logic Lec Sec 3.1,3.2
24th Jan (X hour): Logic: Satisfiability of Formula, Applications Lec Sec 3.3
25th Jan (Fri): Logic: Predicates and Quantifiers Lec Section 3.4, 3.5
28th Jan (Mon): Induction: Basics Lec Section 5.1, 5.2
30th Jan (Wed): Induction: Strong and Strengthening Lec Section 5.3
31st Jan Midterm 1 Venue and Time: Moore 110, 4:30p - 6:30p
1st Feb (Fri): Induction: Proving recursive programs correct Lec , Ind. Supp.
4th Feb (Mon): Combinatorics: Sum and Product Principles Lec Section 9.1, 9.2
6th Feb (Wed): Combinatorics: Bijections, Division Principle Lec Section 9.3
8th Feb (Fri): Combinatorics : The Four Fold Formulas Lec Section 9.4
11th Feb (Mon): Combinatorics: Combinatorial Identities, Binomial Expansion Lec Section 9.4
13th Feb (Wed): Probability : Outcomes, Events, Tree Diagrams Lec Section 10.1, 10.2
14th Feb (X-hour): Combinatorics: More Identities We solved some UGP problems.
15th Feb (Fri): Probability : Conditional Probability, Independence Lec Section 10.3
18th Feb (Mon): Probability : Conditional Independence, Bayes Rule Lec Section 10.3
20th Feb (Wed): Probability : Random Variables, Expectation Lec , Supp Section 10.4
22nd Feb (Fri): Probability : Independence, Variance Lec Section 10.4
25th Feb (Mon): Graphs: Basics, Induction on Graphs Lec
27th Feb (Wed): Graphs: Connectivity, Trees Lec
28th Feb Midterm 2 Venue and Time: Filene, 7p - 9p
1st Mar (Fri): Graphs : Bipartite Graphs, Matchings, Hall's Theorem Lec
4th Mar (Mon): Graphs: Proof of Hall's Theorem Lec
6th Mar (Wed): COSC 30: Review, AMA (Long) Review

Policies

Lectures, X-hours, Attendence Policy, and Notes
Attend all classes including X-hours, of which I may use all of. I will post some notes which may contain more than what is covered.

Regrading Policy
If there is a totalling error, please see any of the TAs and they will fix it rightaway.
On the other hand, if you feel that the grader has not graded accurately then you should clearly write down which problem and your reason why you think the grading is incorrect, staple it with your answer-sheet and hand it to the Head TA during his or her office hour
If even after this you feel unsatisfied, then you can email the instructor for a full regrade . I will look at the entire problem set and re-grade it completely.

Late Exercises and Problem Sets
Problem Sets are submitted via Canvas. Each student has a total of two late days available. Note that even a minute late in canvas is a day late. I will be extremely strict on this: any late submissions after the two late days will be straight given a zero. No excuses shall be entertained. Drill Problem Sets have no late days available; but there will be some slack on how many drills you need to do.

Laptops and Phone Policy
We encourage students not to use devices in class. If they have to, then they need to seat themselves on the fringes of the classroom so as to not distract other students.

Academic Integrity / Honor Code
All work submitted for credit must be your own. This means what you put down on paper for submission cannot be in any way copied from a black/white board, a computer screen, or even your notes from class.
You cannot discuss the drill problem sets with anyone. You may discuss the problem sets with your classmates (taking the course with you), the TAs, and the instructor. No one else. You are also not allowed to give away solutions to your classmates. Clarification questions about problems should be asked on Piazza.
        At the beginning of each problem you must write who you discussed with, and what way did the person help you or you help them. This is important. If you did not talk with anyone about any of the problems, mention this at the beginning of the homework. Any written sources used (apart from the text, your lecture notes and any homework solutions that I distribute) must also be acknowledged; however, you may not consult any solutions on the Internet or from previous years' assignments, whether they are student- or faculty-generated.
        Dartmouth's Academic Honor Principle applies to this course. Please be sure to read the principle, which you can find here . Please ask me if you have any questions about the honor code as it applies to CS 30. Better safe than sorry!