Schedule | Policies |
---|

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

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

- Deeparnab Chakrabarty (Instructor), M,W,F (4:30pm - 5:30 pm) @Sudi216, Thu (4:30p - 5:30p) "Individual (1-1) Office Hours"
- Prantar Ghosh (Head TA), M (2pm - 3pm) @Sudi212, W (2pm - 3pm) @Sudi214
- Xinchen Zhao (TA), Sat (3pm - 5pm) @Sudi114
- Qirong Li (TA), Tue (4:30pm - 6:30pm) @Sudi115
- Shikhar Sinha (TA), Sun (4pm - 6pm) @Sudi213
- Callum Hening (TA), Mon (6:30p - 7:30p) @Sudi115, Tue (6:30p - 7:30p) @Sudi214

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

- Drill Exercises: 30%
- Problem Sets : 30%
- Midterm : 14%
- Final : 24%
- Participation : 2%

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 |

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