News

The last homework is available if you drop by my office.
I'm around most of the time.
If you'd like to know what your hw grade is please send me an email, and I'll tell you.

Study problems from Sections 10.1 to 10.4:
Sec. 10.1, nos. 5, 21, 23.
Sec. 10.2, nos. 3, 7, 11, 15, 17.
Sec. 10.3, nos. 7, 15, 29.

Homework due Friday, November 30:
Sec. 9.4, nos. 20, 26 (you might use the adjacency matrix, but a better hint is to show that if you remove an edge from a simple circuit in a connected graph, it stays connected), 30, 32, 46.
Sec. 9.7, nos. 6, 8, 14, 24.
Sec. 9.8, nos. 6, 8, 10, 36.
Sec. 10.1, nos. 20, 24, 44.

Class on Monday, December 3 will be review.
We will review further during the x-period Tuesday, December 4.

Here is the supplement that was mentioned earlier: click here.

Abstract

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

Here is a tentative syllabus:

1. Logic and proof techniques

3 lectures, Rosen Ch. 1.

2. Induction

2 lectures, Rosen Ch. 4.

3. Set theory

3 lectures, Rosen Secs. 2.1, 2.2, 8.1, 8.5, 2.3.

4. Counting

3 lectures, Rosen Ch. 5.

5. Asymptotics

2 lectures, Rosen Secs. 3.1, 3.2, 2.4, 3.3.

6. Discrete probability

6 lectures, Rosen Ch. 6, Secs. 7.5, 7.6; Cormen for Quicksort and Bucketsort.

7. Hashing

2 lectures, Cormen for hash tables.

8. Grahphs and trees

6 lectures, Rosen Chs. 9, 10.

Classes

Room: 108 Kemeny
Lectures: Monday-Wednesday-Friday 12:30 pm--1:35 pm (12 hour)
X-hour: Tuesday 1:00 pm--1:50pm

Tutorials

There may be occasional tutorials during our x-period, Tuesdays, 1 PM - 1:50 PM, in our classroom

Staff

Instructor:

Carl Pomerance -- 339 Kemeny / Tel. 6-2635
Office hours: Tuesday, Wednesday, Thursday 9:00 AM--9:55 AM and by arrangement at other times.

Homework grader:

Alan Faubert, '11

Textbook

Kenneth H. Rosen
Discrete Mathematics and Its Applications, McGraw Hill.
(required)

This book is available from Wheelock Books and elsewhere.

There will also be some handouts from another text that is not required, but you might want to get it for your other computer science courses:
Introduction to Algorithms, 2nd edition, by Cormen, Leiserson, Rivest, and Stein, published by McGraw Hill.

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 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

Homework due on Monday, Nov. 19.
Section 9.1, nos. 12, 16.
Section 9.2, nos. 20, 22, 24, 26, 28, 34, 48, 60.
Section 9.3, nos. 10, 12, 34, 36, 38, 40, 42, 44.

Homework due Wednesday, November 7.
Sec. 6.2, nos. 6, 10, 16, 30.
Sec. 6.3, no. 10.
Sec. 6.4, nos. 4, 6, 12, 24, 30.
Sec. 7.5, no. 16.
Sec. 7.6, nos. 6, 8, 14. (On these you may use the formulas found in class, and on no. 14, give the answer as a decimal that is correct to 7 places-it's easy!)

Homework due Wednesday, October 31.
Sec. 2.4, nos. 22, 24.
Sec. 3.2, nos. 14, 18, 24.
(In 18e, take both logs to the same base.)
Show that the sum of a geometric progression with positive terms and r not 1 is
&Theta(the biggest term of the sum).
(On some browsers the symbol big theta I tried to type above doesn't come out well.)
Sec. 3.1, no. 44.
Sec. 3.3, no. 8.
Sec. 6.1, nos. 8, 24.

Homework due WEDNESDAY, October 24.
Sec. 5.1, nos. 30, 46.
Sec. 5.2, nos. 18, 32.
Sec. 5.3, nos. 12, 24.
Sec. 5.4, nos. 8, 10, 22. (Hint on 22: think of a committee of size r which has a subcommittee of size k.
Sec. 5.5, nos. 10, 16, 30.

Homework due MONDAY, October 15
Section 2.2, nos. 20, 48.
Section 8.1, no. 4.
Section 8.5, nos. 14, 24, 36, 52.
Section 2.3, nos. 30, 34, 70.

Homework due Wednesday, October 10
Section 4.1, nos. 4, 10, 24, 48, 56.
Section 4.2, nos. 8, 12, 26.
Section 4.3, nos. 4, 8, 18.
Section 4.4, no. 10.
Section 2.1, nos. 30, 34, 36.
This is the complete assignment for Wednesday.

Homework due Wednesday, October 3:
(For some problems you'll have to read the text, I did not cover everything.)
Sec. 1.1, nos. 18, 30, 46,
Sec. 1.2, nos. 6, 8a,b,c, 12, 20,
Sec. 1.3, nos. 6, 10, 16, 36, 44, 50,
Sec. 1.4, nos. 4, 10, 26, 30, 40,
Sec. 1.5, nos. 16, 20,
Sec. 1.6, nos. 6, 12, 26.
(This is the complete assignment.) Note that there is no reason to be abundantly wordy. Terseness is a good mathematical quality. However, it is good to write in complete sentences, and if something needs explaining, please do so. But tersely!

Exams

There will be two midterm exams, held in the evenings of Tuesday, October 16 (topics 1, 2, 3) and Tuesday, November 13 (topics 4, 5, 6) from 7:00 pm to 9:00 pm. I will attempt to construct the exams to be doable in 60 minutes; the extra hour is to help with possible scheduling conflicts, but I will allow you to spend the full two hours if you wish.

The (cumulative) final exam will be held on Monday, December 10 from 8:00 am to 11:00 am in our Kemeny classroom.

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, 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 another person's 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, and I 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.