Instructor's Information  
Harper Langston  
harper AT cs DOT nyu DOT edu  
719 Broadway, Room 1212  
(212) 998 3342  
Office Hours: Mondays 57 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! 5/16/06  Course email list subscription information has been posted below. Please subscribe yourself! Also, Lecture Notes for Chapter 1 and the lecture have been posted for the first class. 5/17/06  I am required to remind everyone of the department's Academic Integrity Policy at http://www.cs.nyu.edu/web/Academic/Graduate/academic_integrity.html. 5/18/06  Homework #1 has been posted at assign1.html, and is due on 5/23/06. 5/22/06  Lecture Notes for the second lecture have been posted below. Also, in light of our discussion about flawed arguments from last week, take a look at the following blog: http://goodmath.blogspot.com/ called "Good Math Bad Math". I also may discuss Godel's Incompleteness Theorem a little this week, and for those interested, take a look at the articles from a recent Notices of the AMS (April 2006) devoted to his work.
5/25/06  Homework #2 has been posted at assign2.html, and is due on 5/30/06. 5/31/06  Homework #3 has been posted at assign3.html, and is due on 6/06/06. 06/06/06  Lecture 4 Notes have been posted as well as notes for Chapters 2, 3 and 4 06/07/06  Homework #4 has been posted at assign4.html, and is due on 6/13/06. 06/13/06  Homework #5 has been posted at assign5.html, and is due on 6/13/06. 06/16/06  Hwk1 Solutions, Hwk2 Solutions and Hwk3 Solutions have been posted. 06/22/06  Homework #6 has been posted at assign6.html, and is due on 6/2706. 06/26/06  Hwk4 Solutions and Hwk5 Solutions have been posted. 06/27/06  Lecture Notes for tonight: Lecture 6 Notes. Also, notes on asymptotics and recurrences: Siegel/Cole Notes. 06/27/06  I am posting notes for Chapters 5 and 6: Chapter 5 Notes and Chapter 6 Notes. 6/28/06  Homework #7 has been posted. The additional homework problems are in the handout at Ch14HwkProbs.pdf. 7/11/06  Solutions for assignment 6 have been posted below. 7/12/06  Homework #8 has been posted. The additional homework problems are in the handout at Ch14HwkProbs.pdf. Also, make sure to read the Siegel/Cole Notes for understanding how to rank the functions. Try to read all of this material if possible. 7/18/06  Here are the lecture notes from the last two classes: Lecture 8 Notes and Lecture 9 Notes. 7/19/06  Homework #9 has been posted: Homework #9 If you are curious about the class and would like to know more (or meet with me beforehand to talk about your background), email 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_su06 and put in the email address you plan to use for the class (You can subscribe with multiple email addresses) and a password, and you will receive a confirmation email. If you want to send a message to the class, email g22_2340_001_su06@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

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.

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 semiregularly 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 online the day it is handed out and students can present their solutions via email 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.

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 takehome. 
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 fulltime jobs during the summer. If you are interested in the class and are unsure how often you will be able to attend, email 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.) 
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: 
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.

There will be a class mailing list, which will be posted here. All students will be required to join. 
Still being decided, but the basic structure will follow previous years: (This is last year's syllabus posted here) 

Date  Lecture Topic  Reading 

1  May 16  Introduction and Logic of Compound Statements  Lecture Notes and Chapter 1 Notes (by J.L. Gross, courtesy of Eitan Grinspun) 
2  May 23  Logic of Quantified Statements and Intro to Proofs  Lecture Notes 
3  May 30  Elementary Number Theory, Set Theory and Methods of Proof  Continuation of Lecture 2 Notes 
4  June 6  Pigeonhole Principle, Algorithms, Sequences and Mathematical Induction  Lecture 4 Notes and Chapter 2 Notes, Chapter 3 Notes and Chapter 4 Notes(by J.L. Gross, courtesy of Eitan Grinspun) 
5  June 13  Counting  Chapter 5 Notes 
6  June 20  Combinations, Permutations and Probability  Chapter 5 Notes 
7  June 27  Probability and Asymptotics  Chapter 6 Notes 
8  July 11  Recurrences and Sorting  Lecture 8 Notes 
9  July 18  More recurrences and solving  Lecture 9 Notes 
10  July 25  Graphs and Trees  Graphs and Trees Notes 
11  August 1  Final Presentations 