Course Description and Objective

Discrete Mathematics is the study of "discrete" objects that can be enumerated by integers. The mathematical foundations of Computer Science heavily deal with such objects, e.g., bits, counters, logical statements, files, network nodes, etc. This course aims to develop the student's understanding of the mathematics involving these objects and their applications to Computer Science. We shall study four main modules: (1) basic discrete tools, such as sets, logic, functions, and mathematical proof techniques, (2) combinatorics (counting), (3) discrete probability, and (4) graph theory. The topics are motivated by Computer Science applications, some of which we shall see in the course. One important objective of the course is to read, write, and understand rigorous mathematical proofs of propositions involving these discrete objects.

Prerequisites

According to the ORC, the prerequisites are Math 3 and COSC 10; or Math 3, Instructor Permission, and either COSC 1 or ENGS 20. Vaguely speaking, the students should have basic programming knowledge and should have some familiarity with basic math. More precisely, they should know the concepts given in lec0.pdf.

Logistics

Class Time: 10 hour (MWF 10:10am - 11:15am; X-hours: Thu 12:15pm - 1:05pm)

Venue: Zaleski Auditorium, MacLean B01

Discussions: Ed Discussion

Problem Sets: Canvas/Gradescope

Course Staff and Office Hours:

Staff	Email	Role	Office Hour and Venue
Prantar Ghosh	prantar.ghosh.gr@dartmouth.edu	Instructor	Mon & Tue 5-6pm, Thu 6-7pm at ECSC 127; One-on-one: Wed 3-4pm or by appointment at ECSC 217
Ehsanul Kabir	ehsanul.kabir.gr@dartmouth.edu	Head TA	Sun 6-7pm, Mon 4-5pm at ECSC 127
Benjamin Cape	benjamin.j.cape.22@dartmouth.edu	TA	Mon 2-3pm on Zoom
Lily Scott	lily.t.scott.24@dartmouth.edu	TA	Mon 3-4pm at ECSC 127
Avery Fogg	avery.e.fogg.24@dartmouth.edu	TA	Sun 5-6pm at ECSC 127
Daniel Dong	daniel.f.dong.25@dartmouth.edu	TA	Sat 1-2pm at ECSC 127

See weekly office hour schedule in calendar format here.

For other logistics, see "policies" below.

Reference Materials

I will post lecture notes on Canvas after each class. No textbook is required. You can, however, refer to the textbook Mathematics for Computer Science by Lehman, Leighton, and Meyer.

Tentative Schedule

The following is a tentative plan for the upcoming lectures. Hence, it is subject to change. Irregular events (holidays/exams) are marked in red. X-hours are marked in green. If I plan to use an X-hour to teach new materials, then it is marked in bold.

Date	Topic	Notes
June 24 (Fri)	Introduction, Sets	lec1.pdf
June 27 (Mon)	Sets (Continued)	lec2.pdf
June 29 (Wed)	Functions	lec3.pdf
June 30 (Thu, X-hr)	Propositional Logic	lec4.pdf
July 1 (Fri)	Important logical equivalences, Predicate Logic	lec5.pdf
July 4 (Mon)	Holiday, No class
July 6 (Wed)	Predicate Logic (continued), Proof by Contradiction	lec6.pdf
July 7 (Thu, X-hr)	Proof by Contradiction (continued), Induction	lec7.pdf
July 8 (Fri)	More Induction, Strong Induction	lec8.pdf
July 11 (Mon)	Strong Induction (continued), Correctness of Recursive Programs	lec9.pdf
July 13 (Wed)	Minimal Counterexamples, Review	lec10.pdf
July 14 (Thu)	Midterm 1 (No X-hour)
July 15 (Fri)	Minimal Counterexamples (continued), Pigeon-hole Principle	lec11.pdf
July 18 (Mon)	Pigeon-hole Principle (continued)	lec12.pdf
July 20 (Wed)	Combinatorics: Sum and Product Principles	lec13.pdf
July 21 (Thu, X-hr)	Practice Problems on Combinatorics	pps1.pdf
July 22 (Fri)	Combinatorics: Inclusion-Exclusion and Identical Objects	lec14.pdf
July 25 (Mon)	Combinatorics: Identical Objects: Division Rule and Stars & Bars	lec15.pdf
July 27 (Wed)	Combinatorics: Integral Solutions, Binomial Theorem	lec16.pdf
July 28 (Thu, X-hr)	Practice Problems on Combinatorics	pps2.pdf
July 29 (Fri)	Combinatorial Proofs	lec17.pdf
Aug 1 (Mon)	Probability: Basics	lec18.pdf
Aug 3 (Wed)	Probability: Birthday Paradox, Conditional Probability	lec19.pdf
Aug 4 (Thu)	Midterm 2 (No X-hour)
Aug 5 (Fri)	Probability: Independence, Bayes Rule; Supplement: Conditional Independence	lec20.pdf lec20_supp.pdf
Aug 8 (Mon)	Probability: Random Variables and Expectation	lec21.pdf
Aug 10 (Wed)	Probability: Independent Random Variables and Variance Supplement: Deviation Inequaities	lec22.pdf lec22_supp.pdf
Aug 11 (Thu, X-hr)	Practice Problems on Probability	pps3.pdf
Aug 12 (Fri)	Graphs: Basics, Handshake Lemma, Walks	lec23.pdf
Aug 15 (Mon)	Graphs: Traversals, Connectivity, Trees	lec24.pdf
Aug 17 (Wed)	Graphs: Proofs via Minimal Counterexamples/Induction	lec25.pdf
Aug 18 (Thu, X-hr)	Graphs: Bipartite Graphs	lec26.pdf
Aug 19 (Fri)	Graphs: Matchings, Hall's Theorem Supplement: Proof of Halls' Theorem	lec27.pdf lec27_supp.pdf
Aug 22 (Mon)	Graphs: Directed Graphs: Basics, DAGs, SCCs	lec28.pdf
Aug 24 (Wed)	Review, AMA	N/A

Evaluation

After every class (except X-hours that do not have new material), there will be a drill assignment of 1 or 2 very short problems due before the next class. There will be weekly problem sets containing 3 or 4 problems (see "Assignments" under "Policies" for details).

There will be two midterms and one final exam (see "Exams" under "Policies" for details).

There will also be some points for participation and engagement (see "Participation and Engagement" under "Policies" for details).

I shall use the following scheme to calculate the total points earned in the course:

Drill Exercises: 30%
Problem Sets : 20%
Midterms: 15% + 15%
Final: 18%
Participation and Engagement: 2%

I may or may not declare later how I am going to determine the letter grades.

Policies

Classes
- Regular classes (MWF): These will be almost fully lectures. This is kind of necessary as the course covers a lot of materials and concepts within a short span of time. During the lectures, however, I shall definitely stop for questions and comments from time to time. Also, please don't hesitate to raise your hand and stop me during lectures so as to ask questions whenever something is unclear.
- X-hours (Thu): I shall take all X-hours except those on June 23 and on the days of the midterms (July 14 and August 4). However, I plan to use them mainly for discussions, exercises, practice problems, and applications based on the material taught in the last three lectures (the material covered since the last X-hour). I do not plan to cover new material in the X-hours unless I feel that it is necessary to use it for catching up. In such a scenario, I shall announce this in advance.
Attendance

Students are strongly recommended to attend all classes. In general, class recordings will not be available. Attendance is also one of the ways to earn participation points (see "Participation and Engagement" under "Policies" for details). Since I typically won't use the X-hours to cover new material, you can choose to skip it only if you are confident that you have a strong grasp on the material taught in the last three lectures. If I announce that I shall use a certain X-hour to cover new materials, then you are strongly recommended to attend it.
Lecture Notes

I shall post lecture notes on Canvas after every class (even X-hours). Note that the notes are only meant to be review materials. They might be succinct and hence, it might be difficult to follow them if you do not attend that lecture.
Assignments
- Drills
  After every regular class, there will be a drill exercise of 1 or 2 very short problems due before the next class. Drills will become available at noon on Mon, Wed, and Fri (45 minutes after the class) and will be due at 9am on Wed, Fri, and Mon respectively (80 minutes before class). The idea is to strengthen your understanding of the content taught in the last class and to help you keep up with the material before attending the next lecture. It should take you at most an hour to complete a drill, including the time to recap the material, solve the problem, and write it up.
  No late submissions are allowed for drills (see "Lateness" under "Policies" for details).
  There is no collaboration or help allowed on drills, not even from the TAs or the instructor (see "Collaboration" below for details). You can only ask the course staff (ideally the instructor) clarification questions if the problem statement is unclear.
  Drills are worth 30% of the total course points. Although it is highly recommended that you work out and submit all drills, you would not need to score full points in all drills to earn these 30% points; there will be some slack that I shall make precise later (Roughly speaking, there will be about 80 total points over all the drills, and you would need to score roughly 70 points (there will be a ~12% buffer) to get full credit towards drills). Solutions to each drill will be posted 1 hour after its deadline.
- (Graded) Problem Sets
  There will be a problem set due every week (except the first week). Each problem set will contain 3 or 4 problems. They will become available on each Wednesday at 1am and will be due on the next Tuesday at 11:59pm.
  You are strongly encouraged to collaborate with other students on these problems. You can also consult the TAs, the CS 30 ASC group tutor, or the instructor during office hours for hints. The final solution that you write, however, must be in your own words and you must acknowledge everyone with whom you collaborated and from whom you sought help (see "Collaboration" below for details).
  No late submissions are allowed for problem sets. Submissions after the deadline of Tuesday 11:59pm will receive no credit (see "Lateness" under "Policies" for details). However, you can score one "early bonus" point if you submit at least 24 hours before the deadline, i.e., by Monday 11:59pm (Tip: think of it as if Monday is the actual deadline, and submitting one day later costs you 1 point.)
  Problem sets are worth 20% of the total course points. There will be no slack for problem sets. Solutions to the problem sets will be posted 1 hour after the deadline (Wednesdays at 12:59am).
Exams
- Midterms
  There will be two Midterms: Midterm 1 will be on July 14 evening (exact time and location TBD). Midterm 2 will be on Aug 4 evening (exact time and location TBD). These are closed-note and closed-book exams. Each midterm is worth 15% of the total course points. The topics included in the syllabus for the midterms will be announced closer to the exam date.
- Final
  The final exam will take place on the date and time announced by the Registrar. It will be closed-note and closed-book. All topics covered in the course will be in the syllabus for the final exam, with more weightage on the material covered after Midterm 2 (to be made more precise later). The final exam is worth 18% of the total course points.
Additional Resources
- Ungraded Problem Sets
  The most effective way to get used to the course material and strengthen your expertise on the concepts is through practice. Each week, I shall post Ungraded Problem (UGP) sets containing problems that are not due for submission (and hence, ungraded). These UGPs are for your own practice. I highly encourage you to solve them (after you are done with graded problem set for the week) and consult the TAs, the CS 30 group tutor, and myself in case you have any doubts. If you formally write up the solutions, you may submit them later for engagement points (see "Participation and Engagement" below). Every week, I shall post the solutions to ungraded problem sets along with those for the graded ones.
- Extra Credit Problems
  Each week, I shall also post Extra Credit (EC) problem sets, which would contain 1 or 2 challenging problems. The aim of these problems would be to provide a flavor of some advanced topics which I would not be able to cover in the limited time allotted to the course. These are for advanced students who have the time and energy to try them after they are done with the regular course work, and would like to engage with the material in more depth (just out of interest, but not for credits). I strongly discourage you to try them before you are done with the weekly graded problem set. Extra Credit problems are high effort and low reward (with respect to getting credits for the course). They will be, however, highly related to the material taught in class. I recommend looking at them and trying them only after you are done with weekly graded problem sets. The collaboration policy for EC problem sets is same as that for graded problem sets.
  EC problem sets will be due by the same deadline as graded problem sets (i.e., Tuesday 11:59pm). The points earned in extra credit would matter only if your final score is borderline between two letter grades, in which case, I shall award you the higher of those two grades. There is no early bonus point for EC problem sets.
Participation and Engagement

You are highly encouraged to actively participate and engage in the course. This includes attending classes, asking questions during lectures and office hours, posting and answering questions on Ed Discussion, suggesting solution ideas for exercises and practice problems solved during X-hours, and writing formal solutions to Ungraded Problem Sets. During the last week of the course, I shall create an assignment named "Participation and Engagement" where you should submit a document listing all the ways in which you have participated and engaged in the course, with supporting materials if applicable (for example, you can include solutions to UGP sets that you have written up). Participation and Engagement are worth 2% of the total course points.
Office Hours

The course staff is happy to help during office hours. I hold four hours of office hours in a week, out of which one hour is one-on-one. I recommend asking conceptual questions and clarifying any conceptual doubts regarding the material during the one-on-one hour. If the slot doesn't work for you, you can email me and set up an appointment. The TAs also hold ample office hours at different times during the week so as to accommodate everyone's conveniences (see schedule here). You are encouraged to seek help from the course staff during office hours for discussing the materials, clearing your doubts, and for hints to solve the problems in the graded and ungraded problem sets.
Note, however, that you are not allowed to copy and physically retain parts of the solution written on the boards/papers during discussions in the office hours. In an office hour, if you must scribble something on paper, you must submit it to the course staff before you leave the room. The aim of this policy is for you to (mentally) retain just the idea/method behind the solution: you can then reproduce the solution in your own words when you prepare your submission, rather than writing the solution, or parts thereof, exactly as you learn/hear during office hours. Use of electronic devices is not at all allowed during office hours (we can provide you paper for scribbling, but don't use tablets).
You cannot seek help with the drill solutions during office hours, but can ask only clarifying questions about the problem statement if it's unclear.
Lateness

You are not allowed any late submissions under any circumstances. I shall follow this very strictly. Any submission after the deadline will receive no credit, and no exceptions will be made. This is for logistical 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 are slacks: drills have a ~12% buffer, while for the weekly problem sets, if you hand in one day early, then you get a bonus point (in other words, if you think of Monday as the deadline, you lose only 1 point for submitting one day later). All timestamps will be based on what Canvas says. Please do not email me or the TAs saying that Canvas did not upload properly, etc; email Canvas instead.
Collaboration

You are strongly encouraged to collaborate with other students taking the class with you on the weekly problem sets. I recommend forming groups of 2 or 3 to discuss the problems and brainstorm for solutions. However, what you submit must be your own words and must acknowledge whom you discussed with. At the beginning of each problem, you must write with whom you discussed (even mention TAs or the instructor if you got help from them). If you did not talk with anyone about any of the problems, mention this at the beginning of the assignment. Failure to write credit statements might even earn you zero credit for the assignment! (For more details, see "Academic Integrity/Honor Code" below. This is crucial!!)
You are not allowed to collaborate on or even discuss the drills with anyone, including the TAs, the ASC group tutor, and the instructor.
Regrading

We will use Gradescope for grading Drills and Problems Sets. Please submit your regrade requests via Gradescope. In case you are unsatisfied by the grader's responses and the final resolution, then you can email the instructor for a full regrade. I will look at the entire problem set and re-grade it completely. For each exam, the regrading policy will be announced when the graded answer sheets are returned to you.
Timing Conflicts

There are two in-class midterms (July 14 and Aug 4) 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.
Electronic Devices

Students are discouraged to use electronic devices in class, with the exception of (a) Tablets only for the purpose of taking notes, and (b) phones/tablets only for taking photos of the board. If you must use a laptop, then you should seat at a corner of the classroom so that others in the classroom, including the instructor, aren't distracted.
Academic Integrity / Honor Code

All work submitted for credit must be your own. This means what you submit cannot be in any way copied from sources including (but limited to) collaborative notes or documents, books, a black/white board, or a computer screen.
You cannot discuss the drill exercises with anyone, including the TAs, the ASC group tutor, and the instructor. You may discuss the graded problem sets with other students taking the course with you, the TAs, the ASC group tutor, and the instructor. No one else. You are also not allowed to give away entire solutions to your classmates. Clarification questions about problems should be asked on Ed Discussion. At the beginning of each problem, you must write with whom you discussed (even mention TAs, the ASC group tutor, or the instructor if you got help from them). This is important. If you did not talk with anyone about any of the problems, mention this at the beginning of the assignment. Any written sources used (apart from lecture notes and any 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. Failure to write credit statements or acknowledge sources might even earn you zero credit for the assignment! For details on citing sources and what can be categorized as plagiarism, please see this.
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 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.
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 as soon as possible, or before the end of the second week of the term—at the latest, to discuss appropriate adjustments. Dartmouth has a deep commitment to support students’ religious observances and diverse faith practices.

Many of the policies above are exactly as adopted by Deeparnab Chakrabarty for the Winter 2020 version of the same course.