V63.0120-003: Discrete mathematics
| Term: | Spring 2011 |
| Meeting times: | 3:30 - 5:20 MW in WWH 201 |
| Instructor: | Andreas Kloeckner |
| Office: | 1311 WWH |
| Office hours: | Monday, Tuesday 10-11and by appointment |
| Phone: | 212-992-5874 |
| Email: | kloeckner@cims.nyu.edu |
Prerequisites
Students who wish to enroll in Discrete Mathematics must meet the
following
prerequisites:
- Calculus I (V63.0121) Refer to Calculus website: http://math.nyu.edu/degree/undergrad/calculus.html
Goals and Topics
- Mathematical language, logic, writing, and proof
- Set theory
- Functions and Relations
- Combinatorics and discrete probability
- Graph theory and trees
Course Details
Textbook and Materials
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
Homework
Homework will be assigned weekly and collected on Wednesdays. 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.Exams
Quizzes
There will be five quizzes, tentatively scheduled for TBD. Quizzes will
start at the beginning of class. We
will also drop the lowest quiz.
Midterms
There will two midterm examinations, on TBD, both in class.
Final
The cumulative final examination will meet May 11 from 4-5:50. We will not be
able to accommodate early finals for nonacademic, nonemergency reasons.
Please plan your travel schedule accordingly.
Grading policy
Grades will be computed by a weighted average:
Homework
10%
Quizzes
10%
Midterm I
20%
Midterm II
20%
Exam
40%
Final scores will be converted to letter grades beginning with the
following scale:
93
A
90
A-
87
B+
83
B
80
B-
75
C+
65
C
50
D
As for a curve, these cutoffs might be adjusted, but only in the
downward direction (to make letter grades higher).
Tentative Calendar
| Week | Day | Book Section | Topic and Notes |
|---|---|---|---|
| 1.1 | First Examples | ||
| 1.2 | Number Puzzles and Sequences | ||
| 1.3 | Truth-tellers, Liars, and Propositional Logic | ||
| 1.4 | Predicates | ||
| 1.5 | Quiz 1 on 1.1–1.3; Implications | ||
| 2.1 | Mathematical Writing | ||
| 2.2 | Proofs about Numbers | ||
| 2.3 | Mathematical Induction | ||
| 2.4 | Contradiction and the Pigeonhole Principle | ||
| Midterm I on 1.1–2.2 | |||
| 3.1, 3.2 | Set Definitions and Operations | ||
| 3.3 | Proving Set Properties | ||
| 3.4 | Boolean Algebra | ||
| 4.1, 4.2 | Quiz 2 on 2.3 and 2.5; Definitions of Functions, Diagrams, Relations, and Inverses, Composition | ||
| 4.3 | Properties of Functions and Set Cardinality | ||
| 4.4 | Quiz 3 on Chapter 3; Properties of Relations | ||
| 4.5 | Equivalence Relations | ||
| 5.1, 5.2 | Introduction to Combinatorics, Basic Rules for Counting | ||
| 5.3 | Combinations and the Binomial Theorem | ||
| 5.4 | Quiz 4 on Chapter 4; Binary Sequences | ||
| 5.5 | Recursive Counting | ||
| Midterm II on 2.3–5.2 | |||
| 6.1, 6.2 | Introduction to Probability, Sum, and Product Rules | ||
| 6.3 | Probability in Games of Chance | ||
| 7.1, 7.2 | Graph Theory, Proofs about Graphs and Trees | ||
| 7.3 | Quiz 5 on Chapter 5; Isomorphism and Planarity | ||
| Review | |||
| Final Exam | |||