Elements of Discrete Mathematics CSCI-GA.G22.2340-001
Summer 2017

Instructor's Information
M. Harper Langston
harper AT cs DOT nyu DOT edu
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. 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! 03/10/17 - Posting website 05/23/17 - Lecture 1 posted 05/24/17 - Homework 1 posted 05/30/17 - Lecture 2 posted 05/30/17 - Homework 2 posted 06/06/17 - Quiz # 1 Tonight! 06/06/17 - Lecture 3 posted 06/15/17 - Homework 3 posted 06/21/17 - Homework 4 posted 06/26/17 - Lecture 6 slides posted 07/13/17 - Homework 5 and 6 (combined) posted 07/18/17 - Lecture slides posted 08/03/17 - Homework 7 posted NYU Classes All students are required to use NYU Classes. I will use that for answering general homework questions, posting announcements, etc. Homeowrk and slides will also be posted to this website, but announcements will be through Classes. 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: 0-486-24775-9) 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 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 1 Homework 2 Homework 3 Homework 4 Homework 5 and 6 Homework 7 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 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 may 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 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 Students are encouraged to collaborate on homework and study in groups, but they 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 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 05/23/2017 Lecture 1 (Intro, Beginning Logic, etc.) Slides (PPT), (PDF) 05/30/2017 Lecture 2 Slides (PPT), (PDF) 06/06/2017 Lecture 3 Slides (PPT), (PDF) 06/27/2017 Lecture 6 Slides (PPT), (PDF) 07/18/2017 Lecture 8 Slides (PPT), (PDF)