News

All tutorials and office hours will be in force for November 22, 23, and the week of November 29,
except for Prof. Pomerance's Tuesday, Nov. 30 office hour---feel free to make an appointment
with him for another time during the week.

Abstract

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

Classes

Bradley, Room 103
Lectures: Monday-Wednesday-Friday 11:15am--12:20am (11 hour)
X-hour: Tuesday 12:00am--12:50am

Tutorials

Bradley, Room 103
Monday & Thursday 7:00pm--8:00pm

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:

Alin Popescu -- 156 Sudikoff Lab (Computer Science building)/ Tel. 6-8720
Office Hours: Wednesday-Thursday: 3:00pm--4:00pm

Wei Zhang -- 205 Sudikoff
Office Hours: Monday-Tuesday: 3:00pm--4:00pm (Blitz if you'd like to talk at another time.)

Textbook

Kenneth P. Bogart, Robert L. Scot Drysdale, and Clifford Stein
Discrete Mathematics in Computer Science,
(required)

This book is available only from the Copy Center, which is upstairs in Thayer Dining Hall. Ask for the Math 19 text.

Grading

Homework 20%, two mid term exams each 20%, final exam 40%. 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 quarter, the lowest of your 4 grades (hw, midterms, final) will be dropped, except if your final exam is your lowest grade, in which case the weight of the final exam will be halved.

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.

There will be a tutorial session on Thursday from 7:00pm to 8:00pm. The tutor is not supposed to do the homework for you; rather he will attempt to help you figure out how to do problems with which you are having trouble. Thus you should be prepared to tell the tutor what you have tried so far and what results you have obtained.

Past assignments

Homework due Monday, November 29.
Section 6.1, numbers 1-12.

Homework due Friday, November 19.
Section 5.4, numbers 2-10, 16.
Section 5.5, numbers 2, 4, 14.
Section 5.6, numbers 1-4, 16.

Homework due Friday, November 12.
Section 1.4, number 12.
Section 5.2, numbers 6, 8, 9, 11, 13. (Concerning number 11, we derived a related formula in class.)
Section 5.3, numbers 2, 3, 6, 8.
Extra problem: Say there is a breath test for the dread dease mathphobia. It is thought that this rare affliction has probability of occurrence in the population of 1/1000. The breath test will definitely test positive if you are a mathphobic, but if you do not have this disease, the test gives a false positive 1% of the time. What is the probability you have mathphobia if you test positive?

Homework due Friday, Nov. 5:
Section 4.5, numbers 1, 2, 9. You may use what we called the "Master Inequality" (that is, you need not use induction):
If T(n) ≤ aT(n/b)+f(n) and S(n) is a solution to the recurrence S(n)=aS(n/b)+f(n), S(1)=T(1), then T(n) ≤ S(n).
Section 4.6, numbers 4, 5, 6, 8.
For extra credit, prove the following: If a,b>0 with a+b=c<1, and if T(n) ≤ T(an)+T(bn)+n, then T(n) ≤ S(n), where S(n) is a solution to the recurrence S(n)=S(cn)+n, S(1)=T(1).
Note that the above problem has been changed and is now only extra credit. (On some systems, an ampersand followed by "le" displays as its typed, instead of displaying as the less than or equal to sign.)
Section 5.1, numbers 1, 2, 3.

Homework due Friday, Oct. 29:
Section 4.1, number 8. Section 4.2, numbers 8, 11, 13.
Section 4.3, numbers 9, 10, 14, 15.
Section 4.4, numbers 2, 4.

Homework due Friday, Oct. 22:
Section 3.2, numbers 1, 2, 7, 8, 12, 13, 14.
Section 3.3, numbers 3, 5, 8, 12.
Section 4.1, numbers 3, 4, 6.

Homework assignment due Friday, Oct. 15:
Section 2.3, numbers 4, 6, 7, 8 (but do not assume that p must be prime), 14
Section 2.4, numbers 1, 6, 7, 14. Also show that if a is any integer then a^561 mod 561 = a mod 561.
Section 3.1, numbers 4, 6, 13, 15.

Homework assignment due Friday, Oct. 8:
Section 2.1, numbers 1, 4, 7, 10, 19
Section 2.2, numbers 2, 7, 9, 11, 12, 14

Homework assignment due Friday, Oct. 1:
Section 1.3, numbers 2, 3, 5, 11, 14, 18
Section 1.4, numbers 2, 6, 11, 16

Homework assignment due Monday, Sept. 27:
Section 1.1, numbers 1, 2, 3, 9, 11
Section 1.2, numbers 1, 5, 6, 7, 11
Additional problem: How many subsets are there of an n-element set? Use the product rule to justify your answer.

Exams

The two midterm exams will be held in the evenings of October 20 and November 10 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 5 from 3:00pm to 6:00pm.

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.