News

NOTE The final exam will be 8:00am (not 8:30!), Tuesday Dec 8, in our regular classroom Kemeny 004.

Pre-exam office hours: Wednesday 12/2, Thursday 12/3 and Monday 12/7, 1:40-2:40.

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

2 lectures, Rosen Ch. 1.

2. Induction

2 lectures, Rosen Ch. 4.

3. Set theory

2 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; plus some supplementary material.

7. Hashing

2 lectures, perhaps from supplementary sources.

8. Graphs and trees

6 lectures, Rosen Chs. 9, 10.

Classes

Room: 004 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:

Peter Winkler -- 231 Kemeny Hall / Tel. 6-3468
new office hours: Wednesday, Thursday, and Friday 1:40 pm--2:40 pm and by appointment.

Homework grader:

Ben Rump, Bernard.C.Rump@Dartmouth.edu

Textbook

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

This book is available from Wheelock Books and elsewhere.

Grading

Your grade will be based on numerical scores for homework (15%), two midterm exams (20% each), and a final exam (45%).

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.
Assignments will be posted on this website.

Past assignments

Due Friday 9/25: pp 17-21, #11 and #47.

Due Monday 9/28: pp 28-30, #60; pp 46-50, #32.

Due Wednesday 9/30: pp 279-283, #6, #10.

Due Friday 10/2: pp 279-283, #66, #72.

Due Monday 10/5: pp 130-133, #26, #48.

Due Wednesday 10/7: pp 527--529, #6; pp 562-566, #2.

Due Friday 10/9: pp 344-347, #30; pp 353-354, #32.

Due Monday 10/12: pp 360-362, #26, #40.

Due Wednesday 10/14, practice only (do not hand in): pp 369-370, #9, #15.

Due Monday 10/19: pp 177-179, #6, #24.

Due Tuesday 10/20: pp 191-193, #24, #44.

Due Friday 10/23: pp 398-400, #8, #26.

Due Monday 10/26: pp 414-416, #10, #26.

Due Wednesday 10/28: pp 424-425, #12; pp 439-443, #10.

Due Friday 10/30: pp 439-443, #14, #24.

Due Monday 11/2: pp 443-445, #10, #20.

Due Wednesday 11/4: pp 439-441, #30; pp 504-505, #14.

Due Wednesday 11/11: 1. In Elbonia families have 0, 1, 2, 3 or 4 kids with equal probability. (a) What is the average number of kids in a family? (b) What is the average number of siblings a kid has? 2. Same questions, but this time a random family has k kids with probability 1/(k!e).

Due Friday 11/13: 1. Determine the complexity of search, insert and delete if the keys assigned to the same hash value are kept in a sorted list. 2. Same, if all the data are kept in a sorted list.

Due Monday 11/16: pp 595-597, #12 and #16.

Due Tuesday 11/17: pp 608-611, #28, #36.

Due Wednesday 11/18: pp 618-621, #16, #28.

Due Monday 11/23: pp 643-647, #26, #40.

Due Monday 11/30: pp. 655-657, #4, #26.

Due Wednesday 12/2: pp. 693-695, #22: pp 742-743, #8.

Exams

There will be two in-class midterm exams, held on Wednesday, October 14 (topics 1, 2, 3, 4) and Friday, November 6 (topics 5, 6) at the regular class times. If for any reason you can't make it to either of these exams, please let me know now.

The (cumulative) final exam will be held at the time for MWF 12:30 classes, namely at 8:00am on Tuesday Dec 8, in Kemeny 004.

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.