CS 30: Discrete Mathematics in Computer Science
Winter 2016 | 11 hour (MWF 11:15-12.20, X-hour Tue 12:00-12:50) | Rockefeller 003
Computer Science 30, Winter 2016 Syllabus

Course Description

Designing efficient algorithms for computational problems is at the core of computer science. This course will cover fundamental mathematical foundations required for conceiving, proving, and analyzing algorithms.

We will begin with an overview of mathematical notation and the basic concepts of sets, functions, and relations. We will then study logic, 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.

Administrative Information

Prasad Jayanti | Room 224 Sudikoff | prasad@cs.dartmouth.edu
Graduate Teaching Assistants
Max Bolonkin | Maksim.Bolonkin.GR@Dartmouth.edu
Jun Han | Jun.Han.GR@Dartmouth.edu
Undergraduate Teaching Assistants
Ethan B. Blackwood '17
Barry Y Chen '16
Lynn S Huang '16
Kooshul S Jhaveri '18
Dylan C. Scandinaro '17
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.

Office Hours

Two types of office hours
We will have two types of office hours: Concept Hours and Homework Help Hours.

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 highh as 65\% course weight. So, to get good practice for the exams, you should receive help on a 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.
Concept Hours
7.00-8.00pm Sunday | Room 213 Sudikoff| TA: Jun Han
7.00-8.00pm Monday | Room 213 Sudikoff| TA: Lynn Huang
2.00-3.00pm Tuesday | Room 224 Sudikoff| Professor Jayanti
7.00-8.00pm Tuesday | Room 213 Sudikoff| TA: Kooshul Jhaveri
7.00-8.00pm Wednesday | Room 213 Sudikoff| TA: Ethan Blackwood
7.00-8.00pm Thursday | Room 213 Sudikoff| TA: Max Bolonkin
7.00-8.00pm Friday | Room 213 Sudikoff| TA: Barry Chen
7.00-8.00pm Saturday | Room 213 Sudikoff| TA: Dylan Scandinaro
Homework Help Hours
8.00-9.00pm Sunday | Room 213 Sudikoff | Ethan Blackwood
8.00-9.00pm Tuesday | Room 213 Sudikoff | Kooshul Jhaveri
1.00-2.00pm Wednesday | Room 213 Sudikoff | Professor Jayanti
1.30-3.00pm Wednesday | Room 213 Sudikoff | Max Bolonkin
8.00-9.00pm Wednesday | Room 213 Sudikoff | Ethan Blackwood
12.30-2.00pm Thursday | Room 213 Sudikoff | Professor Jayanti
1.00-3.30pm Thursday | Room 213 Sudikoff | Jun Han
5.00-7.00pm Thursday | Room 115 Sudikoff | Lynn Huang
8.00-9.00pm Thursday | Room 213 Sudikoff | Barry Chen
8.00-9.00pm Friday | Room 213 Sudikoff | Barry Chen
8.00-9.00pm Saturday | Room 213 Sudikoff | Dylan Scandinaro

Lectures and X-hours

Lectures are in Rockefeller 3 in the 11 hour: MWF 11.15-12.20.
No lecture on two Mondays---Jan 18 because it is MLK day and January 25 because I will be out of town on a college assignment.
X-hours are 12.00-12.50pm on Tuesdays and I expect to use all X-hours. Be sure to attend them, they are no less important than MWF lectures.
Attendance carries points
To not fall behind, it is important that you don't miss even a single lecture or X-hour. To reflect the importance of attending the lectures, attendance is taken during lectures and x-hours and it contributes to your grade. There is no excused absence: any absence, even if due to sickness or being away to represent the college, will be marked as such. However, recognizing such needs, full points will be awarded even if a student is absent for two classes.

Exams, Homework, and Grade

Grading scheme
Your grade will be based on your attendance to lectures and X-hours, and performance on eight weekly homework sets, two midterms, and a final.
The weights are: attendance (5%), homework (30%), each midterm (20%), and final (25%).
Exam Schedule
Midterm 1: 6.00-9.00pm Monday, February 1, in LSC 100
Midterm 2: 6.00-9.00pm Monday, February 22, in LSC 100
Final: 8.00-11.00am Friday, March 11, in Silsby 028
Final exam review: 11.00am Thursday, March 10 in LSC 100
Assigned on Friday afternoons and due by 11.59pm the following Thursday. You submit homework via canvas.
For homework collaboration policy, see the section below on Academic Integrity
For homework lateness policy, see the section below on Policies

Self-Check Exercises

On most lecture days, I will post a few problems 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 self-check exercises help you remain on top of the material.

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 self-check exercises I may have posted for the day.
If you didn't understand something in class or are not able to solve the self-check exercises, go to the concept hour the same day for help from a TA. There will be a concept hour nearly everyday of the week.
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 65% 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 may not take any notes on paper or on an 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 it later.
Absences and Scheduling Conflicts
If you miss a class, there will be no way to earn points for that day's class exercises. 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 to be used for homework assignment over the course of the term as he/she likes. 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 Feb 8 and Feb 29, 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 12 hours of the resolution deadline.
   To make such a request you must email the Chief-Grader-TA 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 something is wrong. The chief-grader or the professor will then make a final determination. Please note that if you make a formal regrade request then the chief grader ot the professor may regrade your entire homework and they typically have stricter standards than the graders.

Academic Integrity

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 prepare the final draft of your solutions, you must work entirely by yourself and write 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. 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, except that each student is allowed to bring in a one-page "cheat sheet" (you may write/print on both sides of the page). The contents of the cheat sheet must be prepared by you on your own and you must submit the cheat sheet along with the exam. Consulting any other sources is forbidden. Giving and receiving help is forbidden, except that you may ask the course staff for clarifications.

These rules will be strictly enforced and any violation will be treated with the utmost seriousness.

Dartmouth's Academic Honor Principle applies to this course. Please be sure to read it.


Students with disabilities enrolled in this course and who may need disability-related accommodations are encouraged to make an appointment to see me on or before Friday, January 15. All discussions will remain confidential, although the Student Accessibility Services office may be consulted to discuss appropriate implementation of any accommodation requested.

Religious Observances

Some students may wish to take part in religious observances that occur during this acdemic term. If you have a religious observance that conflicts with your participation in the course, please meet with me on or before Friday, January 15 to discuss appropriate accommodations.