Discrete Mathematics G22.2340-001
Summer 2005

Tuesdays 6:00-8:20 Room 102 WWH

Instructor's Information                               TA's Information
Harper Langston                               Chris Wu
harper AT cs DOT nyu DOT edu                               wu AT cs DOT nyu DOT edu
719 Broadway, Room 1212                               715 Broadway, Room 704
(212) 998 3342                               (212) 998 3514
Office Hours: Available for appt. anytime(e-mail/call)                               Office Hours: Available for appt. anytime(e-mail/call)

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

Updates!
3/22/05 - The basic structure for the course and the web page is up with basic information. More information about the textbook, etc. will follow
5/12/05 - Book information posted, syllabus updated slightly. Assignment 1 posted (may change slightly by first class).
5/18/05 - Lecture Notes for lecture #1 have been posted.
5/24/05 - Lecture Notes for lecture #2 (Here) have been posted as well as assignment #2 (Here).
5/24/05 - Lecture Notes for lecture #3 (Here) have been posted. Hwk coming soon!
6/7/05 - Lecture Notes for lecture #4 (Here) have been posted. Hwk #3 is also posted
6/15/05 - Lecture Notes for lecture #5 (Here) have been posted. Hwk #4 is also posted
6/22/05 - Hwk #5 has been posted as well as Solutions for Hwks #1-3 (see below)
7/06/05 - Hwk #6 has been posted as well as the Solutions for Hwk #4 (see below)
7/07/05 - Hwk #5 Solutions have been posted below
7/20/05 - Hwk #7 has been posted

If you are curious about the class and would like to know more (or meet with me beforehand to talk about your background), e-mail me!

Class Mailing List
Please sign up for the class mailing list ASAP. We will use this to send out announcements, etc., and students can use it to ask each other for homework help, discuss challenging problems, etc. Go to http://www.cs.nyu.edu/mailman/listinfo/g22_2340_001_su05 and put in the e-mail address you plan to use for the class (You can subscribe with multiple e-mail addresses) and a password, and you will receive a confirmation e-mail. If you want to send a message to the class, e-mail g22_2340_001_su05@cs.nyu.edu

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

  • Discrete Mathematics with Applications, THIRD EDITION by Susanna S. Epp
    Make sure to get the 3rd edition. This was the same text as last summer, so you may be able to get a used copy from students from last summer or at the bookstore.

Suggested/Supplemental
  • How to Solve It - A New Aspect of a Mathematical Method by G. Polya (A new edition is coming out in May, but the current edition is the Second Edition - ISBN 0-691-02356-5)
  • 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.

Assignment 1 (Posted 5/12/05) and Solution #1
Assignment 2 (Posted 5/24/05) and Solution #2
Assignment 3 (Posted 6/7/05) and Solution #3
Assignment 4 (Posted 6/15/05) and Solution #4
Assignment 5 (Posted 6/22/05) and Solution #5
Assignment 6 (Posted 7/06/05)
Assignment 7 (Posted 7/20/05)

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 problmes will give students and opportunity to better understand how to think like a computer scientist when solving complex problems and how to present an interesting problem and how it was solved.

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/Problem Presentation = 5%
Homework = 50%
Midterm = 20%
Final = 25%

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.

Class Mailing List

There will be a class mailing list, which will be posted here. All students will be required to join.

Syllabus

Still being decided, but the basic structure will follow previous years: (This is last year's syllabus posted here)

Lecture
Date Lecture Topic Reading
1 May 17 Introduction and Logic of Compound Statements Chapter 1 and Notes
2 May 24 Logic of Quantified Statements Chapter 2 and Notes
3 May 31 Elementary Number Theory and Methods of Proof Chapter 3 and Notes
4 June 7 Mathematical Induction and Set Theory (Lecture 4 Notes) Sections 3.8, 4.3-4.5 and Chapter 5?
5 June 14 Finish Set Theory and Start Counting (Lecture 5 notes)
6 June 21 More Counting(Lecture notes) Chapter 6
7 June 28 Midterm and Some Counting(Lecture notes)
8 July 5 More Counting(Lecture notes) Chapter 6
9 July 12 Finish Counting and Start Functions Chapter 6 finish and Chapter 7 beginning(Lecture notes)
10 July 19 Finish Functions and Start Recursion Chapter 7 and Start Chapter 8. Also, read in-class Handouts(Lecture notes)
11 July 26 Recursion and Asymptotics
12
Aug 2
Final Class Presentations