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 (CS1) * and * should have some familiarity with basic math.
You should know the concepts given here .

- Deeparnab Chakrabarty (Instructor), M,T, Fr (4:30p - 5:30 p), Anonymous 316, "Individual" Offuce Hour: Th (4:30p - 5:30p) Anonymous 308
- Prantar Ghosh (Head TA), Tue, W (3p - 4:30p), Anonymous 316
- Manuel Stoeckl (TA), M (2p - 3p), F (12n - 1p) in Anonymous 316, Saturday (1:30p - 2:30p), Sudikoff 114
- Janvi Kalra (TA), Sunday (10a - 11a), Sudikoff 114
- Linda Xiao (TA), Monday (5:30p - 6:30p), Tuesday (8p - 9p), Sudikoff 159
- Josiah Putman (TA)
- Anand Mittal (TA), Thu (3p - 4p), Sudikoff 202
- Sucharita Jayanti (TA), Mon (1p - 2p), Tue (12:15p - 2:10p), Sudikoff 202

** Text Book **

I will post lecture notes for every class. No text is required. However, the course will loosely follow a text by
David Liben-Nowell, Discrete Mathematics for Computer Science. * It is not necessary to buy this text *

** Evaluation **

- Drill Exercises: 30%
- Problem Sets : 24%
- Midterm : 12 + 12%
- Final : 21%
- Participation : 1%

** Collaboration **

I highly recommend forming work groups of two or three to work on the weekly problem sets, and also going over the material.
* Your final submission must be your own words and must acknowledge who you discussed with. *
You are

Date | Topics | Notes | Textbook Material |
---|---|---|---|

6th Jan (Mon): | Jargon: Introduction, Sets | Lec | Sec 2.3 |

8th Jan (Wed): | Jargon: Functions | Lec | Sec 2.5 |

9th Jan (X) : |
Jargon: Propositional Logic | Lec , Suppl. | Sec 3.1, 3.2 |

10th Jan (Fri): | Jargon: Predicate Logic | Lec | Sec 3.4 |

13th Jan (Mon): | Proofs: Contradiction | Lec | Sec 4.3 |

15th Jan (Wed): | Proofs: Induction (Basics) | Lec | Sec 5.1 |

16th Jan (X): |
Proofs: Induction (Strong) | Lec | Sec 5.3 |

17th Jan (Fri): | Proofs: Induction (Correctness of Recursive Progs) | Lec | |

22nd Jan (Wed): | Combinatorics: Sum and Product Principles | Lec | Sec 9.1, 9.2 |

24th Jan (Fri): | Combinatorics: Bijections, Division Principle | Lec | Sec 9.4 |

27th Jan (Monday): | Combinatorics: The Four Fold Formula | Lec | Sec 9.4 |

29th Jan (Wed): | Combinatorics: Binomial Coefficients, Combinatorial Identities | Lec | Sec 9.4 |

30th Jan (Thu): | Midterm 1 | Venue: Rocky 3 | Time: 6:30p - 9:30p |

31st Jan (Fri): | Probability: Basics | Lec | Sec 10.1, 10.2 |

3rd Feb (Mon): | Probability: Conditional Probability, Independence | Lec | Section 10.3 |

5th Feb (Wed): | Probability: Bayes Rule | Lec , Suppl. | Section 10.3 |

6th Feb (X): |
Probability: Random Variables | Lec | Section 10.3 |

7th Feb (Fri): | Probability: Expectation and Variance | Lec | Section 10.4 |

10th Feb (Mon): | Graphs: Basics, Handshake Lemma | Lec | Section 11.1, 11.2 |

12th Feb (Wed): | Graphs: Paths, Trees | Lec | Section 11.3, 11.4 |

13th Feb (X) : |
Graphs: Trees | Lec | Section 11.3, 11.4 |

14th Feb (Fri): | Graphs: Bipartite Graphs | Lec | |

17th Feb (Mon): | Graphs : Matchings, Hall's Theorem | Lec | |

19th Feb (Wed): | Graphs: Proof of Hall's Theorem | Lec | |

20th Feb (Thu): | Midterm 2 | Venue: Rocky 3 | Time: 6:30p - 9:30p |

21st Feb (Fri): | Number Theory: Modular Arithmetic | Lec | Section 7.1 |

24th Feb (Mon): | Numbers: GCD, Euclid's Algorithm, Bezout's Identity | Lec | Sec 7.2, 7.3 |

26th Feb (Wed): | Numbers: Multiplicative Inverses | Lec | Section 7.4 |

27th Feb (X): |
Numbers: Fermat's Little Theorem | Lec | Section 7.4, Check out this video |

28th Feb (Fri): | Numbers: RSA | Lec | Section 7.5 |

2nd Mar (Mon): | Infinity: Countability | Lec | Sec 2.5 |

4th Mar (Wed): | Infinity: Uncountability and The Halting Problem | Lec | Sec 4.4.4 |

6th Mar (Fri): | COSC 30: Review, AMA | ||

9th Mar (Mon): | Finals | Venue: Filene | Time: 8a - 11a (Caution: Clocks change on 8th Mar) |

** Attendance **

Attend ** all ** classes including X-hours, of which I may use all of.

** Regrading Policy**

If you feel that the grader has not graded accurately then you should compose an email clearly writing down which problem __ and __ your reason
why you think the grading is
incorrect, and email it to the relevant TA ** cc-ing the head TA **. If you are unsatisfied by the grader's response, get back to the head TA.
If even after all 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.

** Lateness Policy **

You are ** not ** allowed any late submissions under any circumstances. This is for logistic reasons so that I can release solutions and get grading done on time.
I fully understand that unforeseen circumstances may occur. For this reason, there will be a buffer of 12%. This is designed so that on the weekly problem sets you can still
get 100% even if you * completely miss * handing in one.

Furthermore, on the weekly problem sets, if you hand in ** one day early **, then you get a ** bonus ** of one point (you can never get more than 100% though).

All timestamps will be based on what Canvas says. Please do not email us saying Canvas did not upload properly, etc; email Canvas instead.

** Timing Conflicts **

There are two in-class midterms (30th Jan and 20th Feb) during the evenings.
If you cannot be present for these, you need to consult your undergraduate dean regarding your reason and have them email me about it.
I may make an adjustment if the reason sounds valid. For example, going to a concert is not a valid reason, even if you are in the band.

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

** Student Accessibility Needs **

Students with disabilities who may need disability-related academic adjustments and services for this course are encouraged to see me privately as early in the term as possible.
Students requiring disability-related academic adjustments and services must consult the Student Accessibility Services office (Carson Hall, Suite 125, 646-9900).
Once SAS has authorized services, students must show the originally signed SAS Services and Consent Form and/or a letter on SAS letterhead to their professor.
As a first step, if students have questions about whether they qualify to receive academic adjustments and services, they should contact the SAS office. All inquiries and discussions will remain confidential.

** Mental Health **

The academic environment at Dartmouth is challenging, our terms are intensive, and classes are not the only demanding part of your life.
There are a number of resources available to you on campus to support your wellness, including your undergraduate dean (http://www.dartmouth.edu/~upperde/),
Counseling and Human Development (http://www.dartmouth.edu/~chd/), and the Student Wellness Center (http://www.dartmouth.edu/~healthed/).

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