Course Goals
Designing efficient algorithms for computational problems is at the core of computer science. While the design of algorithms is the subject of CS 31, this course covers the mathematical foundations required for proving and analyzing algorithms.
We begin with sets, relations, functions, and logic, and then study proof techniques, combinatorics (counting), probability, and the beginnings of graph theory.
The main purpose of this course is for you to become comfortable with mathematical thinking that allows you to write clean, logical proofs, and mathematical tools that allow you to analyze algorithms. Three specific goals are: (i) learn the mathematical notation and discrete structures that commonly arise in computer science, (ii) learn to write rigorous proofs, and (iii) learn the tools necessary for analyzing algorithms.
Course Staff & Office Hours
- Instructor
- Prasad Jayanti | 224 Sudikoff | prasad@cs.dartmouth.edu
- Instructor's Office Hours (in 213 Sudikoff, starting Tuesday, June 27)
- 1.30-3.00pm Monday
- 3.00-4.30pm Tuesday
- 1.30-2.30pm Thursday
- Graduate Teaching Assistants
- Anup Joshi | Anup.S.Joshi.GR@dartmouth.edu
- Vasanta Kommineni| Vasanta.Lakshmi.Kommineni@dartmouth.edu
- Haider Syed | Haider.Syed@dartmouth.edu
- Undergraduate Teaching Assistants
- Hanting Guo '19 | Hanting.Guo.19@dartmouth.edu
- Andrew Liu '19 | Andrew.A.Liu.19@dartmouth.edu
- Neerja Thakkar '19 | Neerja.B.Thakkar.19@dartmouth.edu
- TA Office Hours (in 213 Sudikoff, starting Tuesday, June 27)
- Mondays | 3.00-6.00pm | Vasanta (first half) and Haider (second half)
- Tuesdays | 4.30-6.00pm | Anup
- Wednesdays | 4.30-6.00pm | Anup
- Thursdays | 4.30-6.00pm | Neerja
- Fridays | 4.30-6.00pm | Haider
- Saturdays | 4.30-6.00pm | Hanting
- Sundays | 4.30-6.00pm | Andrew
Prerequisite & Lectures & Textbooks
- Prerequisite
- CS 1, ENGS 20, or placement through either AP or local placement exam.
- Textbooks (strongly recommended)
- Lehman, Leighton, and Meyer. Mathematics for Computer Science (June 2017 revision; Ebook).
- Kenneth Rosen. Discrete Mathematics and Its Applications (Seventh Edition).
- Lectures
- Lectures are in Life Sciences Center (LSC) Room 201 in the 10A hour: Tue and Thu 10.10-12.00
- X-hours
- X-hours are 3.30-4.20pm on Wednesdays and I expect to use all X-hours. Be sure to attend them; they are no less important than Tue and Thu lectures.
- Attendance Policy
- To do well in the class, the single most important thing is to attend all lectures and be attentive in class. To emphasize the importance of attendance, 4% of the grade is set aside for attendance. However, I do understand that students may have to miss an occasional lecture because of illness, sports or other college engagements, family reasons, or other emergencies. To accommodate these situations, you are allowed to miss up to 8 units of lecture without penalty (I count each Tuesday or Thursday lecture as 2 units and each X-hour as 1 unit). Anyone that misses more than 8 units will lose all of the 4% grade set aside for attendance.
- Ungraded Practice Problems (UGP)
- On most lecture days, I post problems that you should solve the same evening to confirm your understanding of some of the material from that day's lecture. I post my solutions usually within a day to help you check your work and to provide samples for how to write proofs. You don't submit anything and there are no points involved. These problems merely aid in your learning and help you understand how to write up your solutions to homework problems.
Exams, Homework, and Grade
- Grade components
- Your grade will be based on eight weekly homework sets, two midterms, a final, and
attendance (read the attendance policy described above). The weights are:
- Eight homework sets: 24%
- Midterm 1: 24%
- Midterm 2: 24%
- Final: 24%
- Attendance: 4%
- Exams
- Exams are closed book and closed notes (cheat sheets are not allowed).
- Each exam will be designed to take two hours, but I allow you take an hour extra so that you are not stressed for time.
- The exam times are:
- Midterm 1: 4.00-7.00pm Friday, July 21, in Life Sciences Center 201
- Midterm 2: 4.00-7.00pm Friday, Aug 11, in Life Sciences Center 201
- Final: 11.30am-2.30pm Saturday, August 26, Life Sciences Center 100
- Homework
- Homework is assigned late Wednesday and is due by 11.59pm the following Tuesday.
- You should submit your homework electronically, via canvas.
- The first homework goes out on June 28, and the last homework (HW 8) goes out on August 16.
- Homework problems on exams: Solving homework on your own and mastering the homework problems using the solutions I supply are a great way to learn the subject. To encourage such mastery, I will include some homework and/or ungraded practice problems, possibly with minor variation, on each exam. Such problems will constitute about 25% of each exam.
- Self-reliance: To learn the subject well and to be able to do well on the exams (which have a combined weight of 72% towards the course grade), you will have to learn to solve the homework problems on your own, without depending on the TAs or the professor. So, during the professor's and TAs' office hours, we won't provide any direct help with problems from the current homework, but will help you with concepts, UGPs (ungraded practice problems), and problems from previous homeworks.
- What collaboration is allowed: As just explained, the course staff do not help with problems from the current homework, but you may discuss current homework with other students enrolled in this term's offering of CS 30 (but not with any others). Such collaboration should be restricted to discussing the ideas and concepts with each other, and should not degenerate to sharing one's work with another. Thus, when you write the solutions, you must work entirely on your own and write the answers in your own words. At the top of your submission, you must list all people you collaborated with, received help from, or gave help to. If you did the entire homework on your own, you must state so in writing.
- Lateness policy: Each student has 3 free late days towards homework submission over the entire term. Manage them wisely, conserving them for unforeseen situations such as falling sick, or a week with multiple midterms etc. Once these three late days are used up, any homework turned in late will be returned ungraded (and earn a score of 0). There will be no exceptions. Any portion of a late day is counted as one full day and if the Canvas timestamp says you are late, you are late.
- Regrading Policy
- If you are unsure why you lost points on a homework or an exam problem, or feel that the grader made a mistake, you must act before the resolution deadline for that homework/exam. The resolution deadline for a homework is 11.59pm on the first Friday after the homework is returned. The resolution deadlines for Midterm 1 and Midterm 2 are 11:59pm on July 28 and August 18, respectively. Before the resolution deadline you must first contact the relevant grader(s) and try to resolve the matter with them. If you are unable to resolve the matter at this step, you may (optionally) make a formal regrade request. This must be made within the resolution deadline.
To make such a request you must email the Head-TA (Vasanta) with a subject line that says something like "Formal regrade request for HW1", give evidence of having tried to resolve the matter with the graders, and say why you still feel the grading is not fair. The Head-TA, in consultation with the professor, will then make a final determination. Please note that if you make a formal regrade request then a TA or the professor may regrade your entire homework and they typically have stricter standards than the graders. - Midterm Exam Conflicts
- If you have a truly unavoidable academic conflict with one of the scheduled midterms, you must let me know by the end of the second week of the term (i.e., by June 30) and make alternative arrangements. The final exam will be held one time only, at the registrar appointed time (11.30am-2.30pm Aug 26).
How to avoid falling behind
- Most importantly, don't miss even a single lecture. Be on time and attentive. If you had to miss, watch the lecture video, which we strive to publish. However, please understand that the video is at best a poor substitute to the live lecture.
- Each day do the reading, including the notes you have taken in class.
- Solve any ungraded practice problems I have posted for the day.
- If you don't understand something from class or are not able to solve the ungraded practice problems, go to the office hours and get help from a TA or the professor.
- Start early on the homework.
No-Laptop/No-Phone Policy during Lecures
- We have a firm no-laptop/no-phone policy in class. Texting, sleeping or engaging in other activities unrelated to the class is also forbidden. This policy will be strictly enforced so as to encourage active participation by all students and to avoid distracting people that are focusing on the lecture. If you come to class you are expected to obey this policy. (Please read this article to better understand this policy.)
Academic Integrity
- Collaboration on Written Homework
- As explained, the course staff do not help with problems from the current homework, but you may discuss current homework with other students enrolled in this term's offering of CS 30 (but not with any others). Such collaboration should be restricted to discussing the ideas and concepts with each other, and should not degenerate to showing or sharing one's work with another. Thus, when you write the solutions, you must work entirely on your own and write the answers in your own words. At the top of your submission, you must list all people you collaborated with, received help from, or gave help to. If you did the entire homework on your own, you must state so in writing.
- When working on homework problems, you may consult this course website,
the two recommended textbooks for this course, and your own notes from this class.
Consulting any other sources---be they online, electronic, or paper, or homework solutions from previous offerings of this course---is forbidden.
You are urged to read Dartmouth's Sources and Citations.
- Exams
- The exams in this course are closed-book and closed-notes. Cheat sheets are not allowed and you are not allowed to consult any material---paper or online. Giving and receiving help is forbidden, except that you may approach the course staff for clarifications.