This offering of Discrete Mathematics is designed to be an
introduction to the mathematical techniques and reasonings that are
required of a good computer scientist. Upon successful completion of
this course, students should be comfortable with tackling the
mathematical issues confronted in an Algorithms and Data Structures course. More importantly, you will begin to learn how to think like a computer scientist and see how solving problems often confronted in computer science can be fun and challenging!
Students should be comfortable with Basic Algebra such as seen at the high school level. The topics we
will cover in this course will include logic, proof techniques,
induction, recursion, combinatorics, basic probability, algorithm
analysis and efficiency, and discrete structures (including elementary
graph theory). No prior programming experience is required, but students will be encouraged to tackle small programming tasks.
3/1/07 - The basic structure for the course and the web page is
up with basic information. More information about the textbook,
etc. will follow
5/15/07 - First two lecture notes posted as well as mailing
list information. Please sign up for the mailing list ASAP!
5/17/07 - First Homework has been posted. See below in the
Homework Section - it is due 5/29/07
5/23/07 - Homework #1 due date has been moved to 5/29/07
5/25/07Second Homework has been posted. See below in the
Homework Section - it is due 6/5/07. I may be adding more problems to
it after the next class, so start early if you can.
6/03/07Third Homework has been posted. See below in the
Homework Section - it is due 6/12/07.
6/12/07Lecture Notes for Lecture 5 have been posted below
6/15/07Homework 4 has been posted. MAKE SURE TO ACKNOWLEDGE
COLLABORATION OR SOURCES.
7/4/07Homework 6 has been posted. ACKNOWLEDGE
COLLABORATION AND/OR SOURCES.
7/25/07 I am posting some final slides and notes on Graphs and
graph theory: Graphs.pdf (These are
slides and notes of Jonathan Amsterdam - review them before the
Also, as discussed, I am posting some more reading
material on asymptotic running times and recurrence relations from
Siegel and Cole's book: SiegelColeNotes.pdf. I suggest
you pick this book up from the Unique Copy Center as well since
despite being incomplete, it is a great resource. Finally, for some
review problems, try some of the problems from Siegel and Cole: Ch14HwkProbs.pdf.
Class Mailing List
All students are required to join the mailing list. We will use the
list for answering general homework questions, posting announcements, etc. You can join the list be going to the
following url and following the instructions.
There will be one basic textbook and several suggested textbooks, from
which sections for reading may be chosen or sample bonus problems.
will attempt to assign challenge problems continuously (mainly for extra credit).
The required textbook will remain the same as last year. The following text is more appropriate for a graduate level course but also provides a good level of background for students who feel they may need it.
Discrete Mathematics and Its Applications (Hardcover)
Kenneth H Rosen
5 edition (April 22, 2003)
There is also a students solutions handbook for the above book, available from Amazon, Barnes and Noble, etc.
Suggested/Supplemental - These texts are by no means required, but we may discuss parts of them in class; they also provide extra background and motivation for material covered.|
How to Solve It - A New Aspect of a Mathematical Method by G. Polya
Introductory Graph Theory by Gary Chartrand (ISBN: 0-486-24775-9)
The Puzzling Adventures of Doctor Ecco by Dennis Shasha (ISBN:
- Doctor Ecco's Cyberpuzzles by Dennis Shasha (ISBN: 0-393-05120-X)
There will be a midterm and a final. Dates to be decided. However, as noted below in grading, homework will be weighed more heavily, and exams will be mainly used so that students can evaluate their own progress and understanding of the material. The midterm may also be take-home.
Regular attendance is the best way to stay current on the material, especially since we will be reviewing homework assignments and general questions. Plus, new material will be introduced weekly. However, we understand that many students have full-time jobs during the summer. If you are interested in the class and are unsure how often you will be able to attend, e-mail the instructor. Office hours will also be able for students who need to review certain topics. (The goal of the course is to adequately prepare you for the rest of the graduate program, so we want to make sure students feel comfortable.)
students will be assigned
challenge problems for presenting and leading a discussion for
of a class. They will be problems from Dennis Shasha's books - these problems are often difficult, but the answers are provided; presenting and discussing these problems will give students an opportunity to better understand how to think like a computer scientist when solving complex problems and how to present an interesting problem and its solution.
Grade distribution has not fully been decided; however, I often feel that homework better reflects students' abilities since not everyone does well on exams, so homework will factor more heavily into the equation:
Class Participation/Attendance = 5%
Homework = 45%
Exam = 25%
Final Presentation = 25% (5% outline + 10% presentation + 10% paper)
Additionally, please note that since the emphasis will be on teaching you as much as possible for preparation for the rest of the graduate program, testing in this course will not be overly intense. Students who routinely strive to complete the homework and stay current with lectures and reading can expect to receive good final grades. Further, extra credit will be available for students who want to work on more interesting problems and supplement their grades.
Still being decided, but the basic structure will follow previous
years: (This is last year's syllabus posted here)