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.
Students should be comfortable with Basic Algebra and have a strong
matheamtical backgound and understanding of basic math techniques. 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).
There will be a small number of programming assignments in the C
programming languages. No prior programming experience is required,
but students will be encouraged to learn the basics of C with some
small problems meant to highlight certain important topics such as
logic rules, basic probability, recurrence relations, basic graph theory, etc.
Updates!
05/20/19  Posting website
05/28/19  Lecture 1 posted and NYU Classes page created
06/04/19  Lecture 2 posted
06/11/19  Homework 1 posted
06/11/19  Lecture 3 posted
06/18/19  Lecture 4 posted
06/18/19  Homework 2 posted
07/08/19  Homework 3 posted
07/22/19  new Lecture notes posted
07/23/19  Homework 4 posted
08/06/19  Homework 5 posted
NYU Classes
All students are required to use NYU Classes. I will use that for
answering general homework questions, posting announcements, etc.
Homework and slides will also be posted to this website, but
announcements will be through Classes. Information on NYU Classes
will be posted soon!

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
by Susanna Epp
4th Edition, 2010

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: 0486247759)

Puzzling Adventures: Tales of Strategy, Logic, and Mathematical Skill by Dennis Shasha

Puzzles for Programmers and Pros by Dennis Shasha

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, a final, and regular quizzes along with
weekly homeworks. Dates to be
decided.

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.)
Additionally,
students may be assigned
challenge problems for presenting and leading a discussion for
510 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
Class Participation/Attendance = 5%
Homework = 30%
Quizzes = 15%
Exam = 20%
Final Exam = 30%
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, students
who routinely strive to complete the homework and stay current with
lectures and reading can expect to receive good final grades and
perform well on quizzes and exams.

Collaboration
Syllabus
The course will begin with a review of basic logic and compound
statements. Depending on the level of mathematical sophistication of
the group, the pace and the direction of the course will
change. Students can expect to cover the basics of number theory,
probability, set theory, graph theory, etc. with special topics along
the way as is possible.

Lecture Slides

Lecture 1 (Intro, Beginning Logic, etc.)

Slides (PPT)


Lecture 2 (More Logic, etc.)

Slides (PPT)


Lecture 3

Slides (PPT)


Lectures 48

Slides (PPT)


Lecture 9

Slides (PPT)

