|
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).
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/29/13 - Added Lecture 1 link as well as information on class
mailing list
06/03/13 - Added HW1 below
07/09/13 - Fixed the HW2 and Lecture 3-6 links. Added thew
new lecture 7-8 notes.
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.
Subscribe at http://cs.nyu.edu/mailman/listinfo/csci_ga_2340_001_su13
Messages to: csci_ga_2340_001@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
-
In the past, we have utilized Kenneth H Rosen's Discrete Mathematics
and Its Applications; however, I have also become frustrated with
this text, and depsite its lower quality, the price has soared. It is still a good book for consultation purposes, so if
you can find a used affordable copy (6th edition or higher), please do so.
-
As a replacement to Rosen's book, we have chosen a more concise text:
Concrete Mathematics: A Foundation for Computer Science (2nd Edition)
Ronald L. Graham, Donald E. Knuth, Oren Patashnik
2nd edition (1994) - Other editions exist online and may suffice
|
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.
|
Student Presentations
|
Depending on the pace of the course and overall level of student
involvement, a final presentation may replace the final exam.
|
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 Exam or 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
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. wit hspecial topics along
the way as is possible.
|
|
Lecture
|
Date |
Lecture Topic |
Reading |
| 1-2 |
May
29-June 5 |
Basic Information and Intro to Logic |
Lecture 1 Slides |
| 3-6 |
June
12-July 3 |
Logic of Quantified Statements,
Methods of Proof, Set Theory,
Number Theory Introduction |
Lecture 3-6 Slides |
| 7-? |
July 10-? |
Basic Information and Intro to Logic |
Lecture 7-? Slides |
|
