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 (CS 30 / ENGS 66) will cover the mathematical foundations required for proving and analyzing algorithms.
We begin with mathematical notation, logic, sets, functions, and relations. We will then study proof techniques, combinatorics (counting), probability, asymptotic notation, recurrences, and the beginnings of graph theory. By the end of this course, you will have become familiar with a number of discrete structures that are used throughout computer science.
The main purpose of this course is for you to become comfortable with mathematical thinking that allows you to write clean, logical, proofs.
- Prasad Jayanti | Room 224 Sudikoff | firstname.lastname@example.org
- Graduate Teaching Assistants
- Keith E Carlson | Keith.E.Carlson.GR@dartmouth.edu
- Anup Joshi | Anup.S.Joshi.GR@dartmouth.edu
- Vasanta Kommineni| Vasanta.Lakshmi.Kommineni@dartmouth.edu
- Undergraduate Teaching Assistants
- Ethan B Blackwood '17 | Ethan.B.Blackwood.email@example.com
- Kendall A Ernst '18 | Kendall.A.Ernst.firstname.lastname@example.org
- Milan P Huynh '17 | Milan.P.Huynh.email@example.com
- Matthew G Jin '17 | Matthew.G.Jin.firstname.lastname@example.org
- Christopher J Kymn '18 | Christopher.J.Kymn.email@example.com
- John E Martin '17 | John.E.Martin.firstname.lastname@example.org
- Getting Help
- Primary source of help is professor's and TA office hours.
- For only very quick clarification (e.g., of a potential ambiguity on how a problem is phrased in the homework), you might try piazza (link will be up soon)
- Textbooks (strongly recommended)
- Lehman, Leighton, and Meyer. Mathematics for Computer Science (May 2015 revision; Ebook).
- Kenneth Rosen. Discrete Mathematics and Its Applications (Seventh Edition).
- CS 1, ENGS 20, or placement through either AP or local placement exam.
- We will have three types of help hours: Section Hour, Concept Hours, and Homework Help Hours.
The class will be divided into six sections, each consisting of about 15 students. Each section is led by an undergraduate TA and it meets once a week for an hour (on Sundays). Section attendance is not mandatory, but is recommended. Section provides an opportunity to meet with the same TA along with the same set of students each week, for clarifying concepts and homework problems. In the first week of classes, we ask for your available times and place you in a section.
The concept hours provide an opportunity for asking conceptual questions, e.g., questions arising from class, material you are confused about or don't have a good grasp on etc. Questions about homework problems should not be asked or discussed during the concept hour.
Homework Help Hours are when you can get help from the professor or the TAs on the weekly homework set. While you can get plenty of help on homework, you are completely on your own in the three exams, which together count for as high as 64\% course weight. So, to get good practice for the exams, you should receive help on homework only after you have tried it hard on your own.
- Protocol during Homework Help Hours
- Sometimes, as we discuss homework problems during office hours, the discussion might even lead to the professor or a TA writing down the solution on the whiteboard. We don't mind providing such generous help when appropriate and when we feel it helps your learning. However, I expect you to understand whatever we develop together on the board, walk away from the office hours, and recreate the proof/solution on your own for your homework submission. Thus, it is unacceptable to copy or photograph any work from the whiteboard. Our policy requires that laptops and notebooks remain closed during homework help hours.
- List of Concept Hours
- All concept hours are in 213 Sudikoff. They are 8.00-9.00pm everyday except Friday (by Kendall on Tuesday and by Anup on other days). On Friday, the concept hour is 3.00-4.00pm (by Prof. Jayanti).
- List of Homework Help Hours
- 7.00-9.00pm Sunday | Room 212 Sudikoff | John Martin
- 3.00-4.00pm Monday | Room 213 Sudikoff | Prof. Jayanti
- 4.00-5.00pm Monday | Room 213 Sudikoff | Vasanta Kommineni
- 7.00-10.00pm Monday | Room 214 & 115 Sudikoff | Keith Carlson & Kendall Ernst
- 2.30-4.00pm Tuesday | Room 212 Sudikoff | Prof. Jayanti
- 4.00-5.00pm Tuesday | Room 212 Sudikoff | Keith Carlson
- 6.00-9.00pm Tuesday | Room 212 & 115 Sudikoff | Chris Kymn & Vasanta Kommineni & Anup Joshi
- 7.00-8.00pm Wednesday | Room 213 Sudikoff | Kendall Ernst
- 8.00-9.00pm Thursday | Room 212 Sudikoff | Matt Jin
- 4.00-5.00pm Friday | Room 213 Sudikoff | Milan Huynh
- 2.00-4.00pm Saturday | Room 213 Sudikoff | Ethan Blackwood
Lectures, X-hours and Absences
- Lectures are in Life Sciences Center (LSC) Room 201 in the 11 hour: MWF 11.30-12.35.
- X-hours are 12.15-1.05pm on Tuesdays and I expect to use all X-hours. Be sure to attend them, they are no less important than MWF lectures.
- 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 a lecture because of illness, sports or other college engagements, family reasons, or other emergencies. To accommodate all this, you are allowed to miss up to 8 lectures (which is a little over 20% of the lectures) without penalty, i.e., anyone who misses 8 or fewer lectures (including X-hours) will get the full 4% grade set aside for attendance. Anyone who misses 9 or more lectures (including X-hours) will lose all of the 4% grade set aside for attendance.
Exams, Homework, and Grade
- Grading scheme
- Your grade will be based on nine weekly homework sets, two midterms, and a final.
- The weights are: nine homework sets (36%), first midterm (20%), second midterm (20%), final exam (20%), and attendance (4%). Read the attendance policy described above.
- Exam Schedule
- Midterm 1: 4.30-7.30pm Thursday, October 6, in LSC 100
- Midterm 2: 4.30-7.30pm Thursday, October 27, in LSC 100
- Final: 3.00-6.00pm Sunday, November 20, room to be announced later
- Final exam review: 10.00am-Noon Thursday, November 17, room to be announced later
- Assigned on Wednesday afternoons and due by 11.59pm the following Tuesday. You submit homework via canvas. The first homework goes out on September 14.
- For homework collaboration policy, see the section below on Academic Integrity
- For homework lateness policy, see the section below on Policies
Ungraded Practice Problems
- On most lecture days, I will post a problem or two that you should attempt to solve the same evening to confirm your understanding of some of the material from that day's lecture. I post my solution too to help you check your answer. You don't submit anything and there are no points involved; these problems merely aid your learning.
How to avoid falling behind
- Most importantly, don't miss even a single lecture. Be on time and attentive.
- Each day do the reading, including the notes you have taken in class.
- Solve any ungraded practice problems I may have posted for the day.
- If you didn't understand something in class or are not able to solve the ungraded practice problems, go to the concept hour and get help from a TA or the professor.
- You can receive plenty of help from me or the TAs with homework problems, but don't get into the habit of approaching for help without first trying the problems very hard on your own. If you don't heed this advice, you won't get enough practice in problem solving, which will hurt you on the exams (remember that exams have 64% weight towards the course grade).
- 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.)
- No-Laptop, No-Notetaking Policy during Homework Help Hours:
- We have a firm policy that you do not take any notes on paper or on any electronic device during Homework Help Hours. Accordingly, laptops/tablets/phones as well as notebooks should remain closed during these hours. Please see my explanation above for why we have such a policy. The basic idea is that you should understand what we have discussed and be able to reconstruct the solutions later.
- Absences and Scheduling 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 and make alternative arrangements. The final exam will be held one time only, at the registrar's appointed time.
- Late Submissions
- Each student has 3 free late days towards homework submission over the course of the 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). No exceptions! Any portion of a late day is counted as one full day (i.e., even one minute late counts as a full day) and if the Canvas timestamp says you're late, you're late; no exceptions. Homework can only be turned in electronically, via canvas.
- Regrading Policy
- If you are unsure why you lost points on a homework or 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 Monday after the homework is returned.
The resolution deadlines for Midterm 1 and Midterm 2 are
11:59pm on October 17 and November 7, 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
To make such a request you must email the Head-TA (Anup Joshi) 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 the Head-TA ot the professor may regrade your entire homework and they typically have stricter standards than the graders.
- Collaboration on Written Homework
- When working on homework problems, you may collaborate and discuss with the course staff and other students enrolled in this term's offering of this course (and not with any other persons). However, 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 that in writing.
- When working on homework problems, you may consult this course's website, any handouts given out in class, any discussions on this course's piazza forum, the two recommended textbooks for this course, and your own notes from this class. Consulting any other sources is forbidden, unless the professor has made an exception in writing. You should take a look at Dartmouth's Sources and Citations.
- 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 ask the course staff for clarifications.