V63.0120-001: Discrete mathematics
| Term: | Spring 2011 |
| Meeting times: | 11:00 a.m. - 12:50 p.m. MW in 202 WWH |
| Instructor: | Prof. Wesley Pegden |
| Office: | 921 WWH |
| Office hours: | TBD and by appointment |
| Email: | pegden@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
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
Course Details
Textbook and Materials
Discrete
Mathematics: Mathematical Reasoning and Proof with Puzzles, Patterns,
and Games
by
Douglas E. Ensley and J. Winston Crawley.
ISBN
0–471–47602–1
Homework
Assigned weekly (during the Wednesday class) and collected at the beginning of next Monday class (5-6 problems / week)Exams
QuizzesThere will be five quizzes, tentatively scheduled for TBD. Quizzes will start at the beginning of class. We will also drop the lowest quiz grade.
Midterm
There will be midterm examinations on (TBD) in class.
Final
The cumulative final examination for this course is Monday, May 16th
from 10:00 - 11:50 a.m. Please note the final will take place an
hour earlier than the regularly scheduled time. [CLASSROOM TBD] 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: Final scores will be
converted to letter grades beginning with the following scale:
Homework
10%
Quizzes
10%
Midterm I
20%
Midterm II
20%
Exam
40%
93
A
90
A-
87
B+
83
B
80
B-
75
C+
65
C
50
D
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 | |||