V63.0120: Discrete Mathematics Spring 2011
[[!table header="no" class="mointable" data=""" Class Time/Location | Monday, Wednesday 3:30pm-5:20pm Silver Center rm. 514 Instructor | Andreas Kloeckner Email | kloeckner@courant.nyu.edu Office | Courant Institute, Warren Weaver Hall, Room 1311 Office Hours | Monday, Wednesday 2pm-3pm Class Webpage | http://wiki.tiker.net/Teaching/DiscreteMathSpring2011 Email Listserv | http://lists.tiker.net/listinfo/discrete11, discrete11@tiker.net, archive """]]
[[!toc ]]
Topics and goals
Our major goal will be to familiarize ourselves with some of the important tools of discrete mathematics.
- Mathematical language, logic, writing, and proof
- Set theory
- Functions and Relations
- Combinatorics and discrete probability
- Graph theory and trees
Text
Discrete Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns, and Games, by Douglas E. Ensley and J. Winston Crawley. Wiley, ISBN 0-471-47602-1
The book has a rather helpful companion web site which we will be using on occasion.
Summary of Chapters 4 through 7 by Ashish Myles
Assessment
Homework : will be assigned weekly (generally assigned and collected on Mondays). In fairness to the other students in the course, late homework will generally not be accepted. We will, however, drop the lowest homework score in computation of final grades. Please talk to the instructor in cases of emergency.
Quizzes : There will be five quizzes, generally on Wednesdays. They are tentatively scheduled as indicated in the syllabus below. Quizzes will start at the beginning of class and run for about 15-20 minutes. We will also drop the lowest quiz.
Midterm : There will one midterm examination, on March 9 in class.
Final : The cumulative final examination for this course is scheduled as indicated on the calendar below. We will not be able to accommodate early finals for nonacademic, nonemergency reasons. Please plan your travel schedule accordingly.
Grades will be computed by a weighted average: [[!table header="no" class="mointable" data=""" Homework | Quizzes | Midterm | Final 10% | 20% | 30% | 40% """]]
Final scores will be converted to letter grades beginning with the following scale:
[[!table header="no" class="mointable" data="""
93 | 90 | 87 | 83 | 80 | 75 | 65 | 50
A | A- | B+ | B | B- | C+ | C | D
"""]]
As for a curve, these cutoffs might be adjusted, but only in the downward direction (to make letter grades higher).
On the homework, each problem will be worth three points, assigned as follows: [[!table header="no" class="mointable" data=""" Points | Description of Work 3 | Work is completely accurate and essentially perfect. Work is thoroughly developed, neat, and easy to read. Complete sentences are used. 2 | Work is good, but incompletely developed, hard to read, unexplained, or jumbled. Answers which are not explained, even if correct, will generally receive 2 points. Work contains the 'right idea' but is flawed. 1 | Work is sketchy. There is some correct work, but most of the work is incorrect. 0 | Work minimal or non-existent. Solution is completely incorrect. """]]
For the purposes of assembling the final grade, the grade on each homework set is converted to a percentage of all achievable points, on a scale from 0 to 100.
Material about Tests
[[!map pages="^Teaching/DiscreteMathSpring2011/(Quiz[0-9]+.*|Midterm)"]]
Homework
[[!map pages="^Teaching/DiscreteMathSpring2011/HomeworkSet[0-9]+"]]
Tentative Calendar
[[!table header="no" class="mointable" data="""
Week | Day | Book Section | Topic/Notes
1 | 1/24 | 1.1 | First Examples
1/26 | 1.2 | Number Puzzles and Sequences
2 | 1/31 | 1.3 | Truth-tellers, Liars, and Propositional Logic
2/2 | 1.4 | Predicates
3 | 2/7 | 1.5 | Quiz; Implications
2/9 | 2.1 | Mathematical Writing
4 | 2/14 | 2.2 | Proofs about Numbers
2/16 | 2.3 | Mathematical Induction
5 | 2/21 | President's day (no class) ||
2/23 | 2.5 | Quiz; Contradiction and the Pigeonhole Principle
6 | 2/28 | 3.1, 3.2 | Set Definitions and Operations (taught by Dr. Wesley Pegden)
3/2 | 3.3 | Proving Set Properties (taught by Dr. Wesley Pegden)
7 | 3/7 | Review ||
3/9 | Midterm on 1.1-3.3 ||
8 | 3/14 | _Spring Recess (no class) ||
3/16 | Spring Recess (no class) ||
9 | 3/21 | 3.4 | Boolean Algebra
3/23 | 4.1, 4.2 | Definitions of Functions, Diagrams, Relations, and Inverses, Composition
10 | 3/28 | 4.3 | Properties of Functions and Set Cardinality (taught by Dr. Michael O'Neil)
3/30 | 4.4 | Properties of Relations
11 | 4/4 | 4.5 | Quiz; Equivalence Relations
4/6 | 5.1, 5.2 | Intro to Combinatorics, Basic Rules for Counting
12 | 4/11 | 5.3 | Cominatorics and the Binomial Theorem
4/13 | 5.4 | Binary Sequences
13 | 4/18 | 5.5 | Quiz; Recursive Counting
4/20 | 6.1, 6.2 | Intro to Probability, Sum and Product Rules
14 | 4/25 | 6.3 | Probability in Games of Chance
4/27 | 7.1, 7.2 | Graph Theory, Proofs about Graphs and Trees
15 | 5/2 | 7.3 | Quiz; Isomorphism and Planarity
5/4 | Review ||
16 | 5/9 | Review ||
5/11 | Final Exam 4:00pm-5:50pm ||
"""]]
(see also the academic calendar)