CS19/Math19/ENG66

Discrete Mathematics in Computer Science

Instructor: Carl Pomerance (carl.pomerance@dartmouth.edu)

Abstract | Classes | Tutorials | Staff | Textbook | Grading | Homework | Past assignments | Exams | Honor Code


News

Our schedule for the remainder of the term:
We have regular class meetings on Nov. 16, 18, 21, 28, 30.
The x-period will meet on Nov. 29.
The final exam is on Dec. 3 at 3 pm. Tutorials will be held as usual on Nov. 27 and Nov. 30,
but concerning the Nov. 27 tutorial, if no one shows up in the first 15 minutes, Mr. Huang might leave.

There are no more written assignments. However, we will continue to go over new material (Sections 5.6 and 5.7), so it would be good to try and do some of the problems from these sections on your own.

Tutorials meet on Wednesdays and Sundays from 5 to 6 pm.
The Wednesday tutorial meets in Bradley 105 and the Sunday tutorial meets in Bradley 13.
Students are encouraged to attend!

Abstract

This course integrates discrete mathematics with algorithms and data structures, using computer science applications to help motivate the mathematics.

Our textbook has 6 chapters, and we will visit each of them.

Classes

13 Bradley Hall
Lectures: Monday-Wednesday-Friday 11:15am--12:20pm (11 hour)
X-hour: Tuesday 12:00pm--12:50pm

Tutorials

Wednesdays (Bradley 105) and Sundays (Bradley 13), both days from 5 to 6 pm.

Staff

Instructor:
Carl Pomerance -- 102 Choate House (corner of Choate and North Main)/ Tel. 6-2635
Office hours: Tuesday, Wednesday, Thursday 9:00am--10:00am and by arrangement at other times.
TAs:
Chien-Chung Huang -- 221 Sudikoff/ Tel. 6-8753
Office Hours: Thursday, 2:00 pm--4:00 pm and by arrangement at other times.
Yurong Xu
Mr. Xu will grade the homeworks and will help out with test grading.

Textbook

Kenneth P. Bogart, Robert L. Scot Drysdale, and Clifford Stein
Discrete Mathematics for Computer Science, Key College Publishing.
(required)

This book is available from Wheelock Books.

Grading

Your grade will be based on numerical scores for homework, two midterm exams, and a final exam. As much as possible, grades will be based on demonstrated knowledge. However relative performance may be used as a criterion for increasing grades, and grade borderlines will be chosen to place a relatively small number of students on borderlines. At the end of the term, if one of the midterms or your homework average is the lowest of the 4 grades, it will be dropped, with the remaining midterm(s)/homework grades each counting 25% of the grade, and the final counting 50%. If the final exam grade is the lowest, each of the 4 grades will count 25%.

Homework

Homework is due at the start of the class period on the due date. Late homework is generally not accepted unless there is a prior arrangement.
Homework will be generally due once per week on Mondays.
Assignments will be posted on this website, with extra problems and/or comments added as the week progresses.

Past assignments

Assignment #1: Section 1.1, numbers 2, 9, 10, 11.
Section 1.2, numbers 1, 3, 5, 7, 11, 15.
Additional problem: Show there is a bijection between the set of functions from an n-element set S into {0,1} and the set of subsets of S.

Assigment #2: Sec. 1.3, Numbers 10, 13, 14, 17, 18.
Sec. 1.4, Numbers 4, 6, 10, 12, 16b,d,f,h,j.
Sec. 2.1, Numbers 2, 4, 6.

Assignment #3: Section 2.1, #10, 12, 14.
Section 2.2, #2, 4, 6, 12.

Assignment #4, Section 2.4, numbers 2, 6, 10, 12, 14.
Section 3.1, numbers 6, 8, 13, 15.

Assignment #5, Due Monday, October 24.
Section 3.2, numbers 2, 12, 14.
Section 3.3, numbers 3, 5, 8, 10, 13.
Section 4.1, numbers 2, 4, 6, 8.

Assignment #6, due Monday, October 31.
Section 4.2, numbers 2, 7, 11, 13 ,15, 18.

Assignment #7, due Monday, Nov. 7.
Section 4.3, numbers 1, 6, 16 (assume g(n)>0).
Section 4.4, numbers 1c, 1e, 2, 4.
Section 4.5, numbers 2, 4, 9, 10.

Assignment #8, Due Monday, 14 November.
Section 4.6, Numbers 4, 5.
Section 5.1, Numbers 2, 4, 8, 12.
Section 5.2, Numbers 2, 4, 10.

Assignment #9, Due Monday, November 21.
Section 5.3, Numbers 2, 6, 8, 12, 13.
Section 5.4, Numbers 4, 6, 12, 19.
Section 5.5, Numbers 2, 4, 6.

Exams

There will be two midterm exams, held in the evenings of October 11 and November 8 from 7:00pm to 9:00pm. These exams will be constructed so as to be doable in 60 minutes; the extra hour is to help you relax and not feel so rushed.

The final exam will be held on December 3 from 3:00 to 6:00 in Bradley 13.

Honor Code

Students are encouraged to work together to do homework problems. What is important is a student's eventual understanding of homework problems, and not how that is achieved. The honor principle applies to homework in the following way. What a student turns in as a homework solution is to be his or her own understanding of how to do the problem. Students must state what sources they have consulted, with whom they have collaborated, and from whom they have received help. Students are discouraged from using solutions to problems that may be posted on the web for previous offerings of the course, and as just stated, must reference them if they use them. The solutions you submit must be written by you alone. Any copying (electronic or otherwise) of anotehr person's code or solutions, in whole or in part, is a violation of the Honor Code.

The honor principle applies to exams as follows: Students may not give or receive assistance of any kind on an exam from any person except for the professor or someone explicitly designated by the professor to answer questions about the exam. Students may not use library or internet sources on take-home exam problems, but they may use their textbook and personal notes.

If you have any questions as to whether some action would be acceptable under the Academic Honor Code, please speak to me or another member of the course staff, and we will be glad to help clarify things. It is always easier to ask beforehand than to have trouble later!

Disabilities

I encourage any students with disabilities, including "invisible" disabilities such as chronic diseases and learning disabilities, to discuss appropriate accommodations with me, which might help you with this class, either after class or during office hours. Dartmouth College has an active program to help students with disabilities, and I am happy to do whatever I can to help out, as appropriate.

The Student Disabilities Coordinator, Nancy Pompian, can be reached at 6-2014 if you have any questions. Any student with a documented disability requiring academic adjustments or accommodations is requested to speak with me by the end of the second week of the term. All discussions will remain confidential, although the Academic Skills Center may be consulted to verify the documentation of the disability and advise on an appropriate response to the need. It is important, however, that you talk to me soon, so that I can make whatever arrangements might be needed in a timely fashion.

This page was modeled after one written by Alin Popescu.