Discrete Mathematics G22.2340-001
Summer 2008

Tuesdays 6:00-8:20 Room 102 WWH

Extra Slides and Notes:

As promised, here are some extra slides and notes for everyone to review:

Asymptotics and Algorithm Introduction Part 1 and Part 2
Notes from Siegel/Cole for review (for the rest of the book, check the Unique Copy Center. As stated, the book is worth reviewing)
Other books worth considering (check library or Amazon):

Final Presentations:

Instructor's Information                              
Harper Langston                              
harper AT cs DOT nyu DOT edu                              
719 Broadway, Room 1212                              
(212) 998 3342                              
Office Hours: TBA and by appt.                              

Course Information
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.

Updates!

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.

http://www.cs.nyu.edu/mailman/listinfo/g22_2340_001_su08

Textbooks
There will be one basic textbook and several suggested textbooks, from which sections for reading may be chosen or sample bonus problems.
We will attempt to assign challenge problems continuously (mainly for extra credit).

Required

  • 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
    McGraw-Hill Science/Engineering/Math
    6th edition (2007) - Make sure to get the 6th only!
    ISBN:

    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: 0-486-29615-6)
  • Doctor Ecco's Cyberpuzzles by Dennis Shasha (ISBN: 0-393-05120-X)

Homework

The homework will be designed to supplement readings and lectures. The best way to become adequately mathematically literate in this material is through continuous exercises, so homework will given semi-regularly and will be due the week following when it is assigned. Students can work with others, but they must indicate on their homework with whom they have worked (working together in no way affects your grade). Additionally, homework will be posted on-line the day it is handed out and students can present their solutions via e-mail in case they are unable to attend a lecture. Collaboration is encouraged but must be acknowledged on the top of your assignment. See the Academic Integrity Policy for more information: http://www.cs.nyu.edu/web/Academic/Graduate/academic_integrity.html.

  • Homework assignment #1 (Due 6/10/2008): hw1.pdf
  • Homework assignment #2 (Due 7/1/2008): hw2.pdf
  • Homework assignment #3 (Due 7/15/2008): hw3.pdf
  • Homework assignment #4 (Due 7/29/2008): assign4.html

Student Presentations

Here is a list of all of the student presentations as well as copies of their final papers. I will be adding to these as I receive them (listed in presentation order):

Exams

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.

Attendance/Class Participation

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

Additionally, students will be assigned challenge problems for presenting and leading a discussion for 5-10 minutes 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.

Grading

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.

Collaboration

Students are encouraged to collaborate but are expected to indicate as such on any homework turned in. Exams will be in class, so no collaboration will be allowed. See the Academic Integrity Policy for more information: http://www.cs.nyu.edu/web/Academic/Graduate/academic_integrity.html.

Syllabus

Lecture
Date Lecture Topic Reading
1 May 20 Class to be rescheduled
2 May 27 Introduction and Logic of Compound Statements Lecture Notes and
Chapter 1 Notes (by J.L. Gross, courtesy of Eitan Grinspun)
3 June 3 Continuation of last week + Start Logic of Quantified Statements and Intro to Proofs Lecture Notes
4 June 10 Continuation of Slides (Proofs, Set Theory, etc.) Notes worth reading:
Chapter 2 Notes and
Chapter 3 Notes(by J.L. Gross, courtesy of Eitan Grinspun)
5 June 17 Continuation
6 June 24 Continuation
7 June 24 Review some Hwk Problems, Discuss Pigeonhole Principle, Work on Sequences and Induction, and Maybe Begin Probability Lecture Slides