Venue:
Monday, Wednesday 8:55AM-10:45AM @ Global Center for Academic & Spiritual Life / 238 Thompson Street (GCASL), Room 369
Instructor:
Sivaram Ambikasaran, firstname@cims.nyu.edu
Office: WWH, 1105A. Office hours: Mondays 2:00 PM - 4:00 PM and Tuesdays 2:00 PM - 4:00 PM.
Syllabus:
A first course in discrete mathematics. Sets, algorithms, induction, recurrences, combinatorics, number theory, graph theory, probability.
Textbook:
Other recommended texts:
PLEASE READ THIS: It is most important that you regularly read the textbook and notes posted. You are also strongly encouraged to read the other recommended texts. Given that this is the first rigorous mathematics course for most of you, it is highly unlikely that you will be able to keep pace with the material presented without reading the textbook and notes. You are strongly encouraged to attend office hours. The most efficient way to learn this subject is to work out a lot of problems, problems, and more problems (exercises and examples from the book provide a wonderful opportunity) apart from homework problems. Getting a feel for definitions, theorems, etc will take time and this is where doing problems will help you to build your intuition on why things are defined in a specific way and why are certain theorems useful. Getting confused and spending sufficient time to understand a theorem is also common. Whenever you read a theorem, try to construct counterexamples by invaliding a particular assumption of the theorem. Some concepts are genuinely challenging and hard (especially since you will be learning it for the first time), but that's what makes this class entertaining and fun.
Grading:
| Evaluation | Assignments | Inclass Quiz | Class Exam-I | Class Exam-II | Final Exam |
| Points | 21 | 14 | 20 | 20 | 25 |
| Week | Monday | Wednesday | Homework |
| 1 | Jan 26: Logistics, introduction, sets Lecture 1 | Jan 28: More on sets Lecture 2 | Due Tuesday, Feb 3 HW1 HW1soln |
| 2 | Feb 2: Logic Lecture 3 | Feb 4: Logic continued Lecture 4 | Due Tuesday, Feb 10 HW2 HW2soln |
| 3 | Feb 9: Combinatorics Lecture 5 | Feb 11: Counting and combinatorial arguments Lecture 6 | Due Thursday, Feb 19 HW3 HW3soln |
| 4 | Feb 16: NO CLASS | Feb 18: Pascal's triangle, counting and functions Lecture 7 | Due Thursday, Feb 26 HW4 HW4soln |
| 5 | Feb 23: Functions, Equinumerous sets Lecture 8 | Feb 25: Pigeon hole principle, Induction Lecture 9 | Due Thursday, Mar 5 HW5 HW5soln |
| 6 | Mar 2: Exam 1 solutions, Induction Lecture 10 | Mar 4: Tower of Brahma/Hanoi, Recurrence Lecture 11 | Due Thursday, Mar 12 HW6 HW6soln |
| 7 | Mar 9: Recurrences, Bezout's lemma Lecture 12 | Mar 11: Linear Diophantine equations, Euclid's Algorithm, Exam 1 statistics Lecture 13 | Due Tuesday, Mar 24 HW7 HW7soln |
| 8 | Mar 16: Spring break | Mar 18: Spring break | |
| 9 | Mar 23: Prime factorization, divisors, Modular arithmetic Lecture 14 | Mar 25: Chinese remainder theorem, Pell's equation Lecture 15 | Due Tuesday, Mar 31 HW8 HW8soln |
| 10 | Mar 30: Pell's equation, Characterizing Pythagorean triplets Lecture 16 | Apr 1: Graph theory | Due Tuesday, Apr 7 HW9 HW9soln |
| 11 | Apr 6: Exam 2 solutions | Apr 8: Simple graphs, hand shake lemma, trees and its properties | Due Thursday, Apr 16 HW10 HW10soln |
| 12 | Apr 13: Subgraph, Trees, Cliques and Independent set | Apr 15: Connected components, Cut edge, cut vertex, graph coloring, bipartite graph | Due Thursday, Apr 23 HW11 HW11soln |
| 13 | Apr 20: Bipartite graph, Graph coloring, Bounds on chromatic number, Eulerian path, Eulerian cycle, Planar graphs | Apr 22: Euler's formula for planar graphs, \(K_5\) and \(K_{3,3}\) not planar, Probability | Due Tuesday, Apr 28 HW12 HW12soln |
| 14 | Apr 27: Equally likely, Disjoint events, Conditional Probability, Bayes rule. | Apr 29: Bayes rule, Dependent and independent events, Random variables (discrete and continuous). | Due Tuesday, May 5 HW13 HW13soln |
| 15 | May 4: Probability density function (pdf), cummulative distribution function(cdf), moments of a distribution. | May 6: Various discrete and continuous probability distribution function. | Due Tuesday, May 12 HW14 HW14soln |
| 16 | May 11: Review of all the material. Review problems Review solutions | May 13: Final exam. Final exam solutions |
There will be a total of 14 written homework. Homework will be posted on this website and will be due on Tuesday (or) Thursday before 6 PM. You can drop them in my mailbox at the Courant Institute or hand it in during office hours. Late homework will not be accepted.
Grader(s) will be expecting you to express your ideas clearly, legibly, and completely, often requiring complete English sentences rather than merely just a long string of equations or unconnected mathematical expressions. This means you could lose points for poorly written proofs or answers. Clear exposition is a crucial ingredient of mathematical communication. Clarity of thought and presentation is more important in mathematics than any other field. The only way to master exposition is by repeated practicing. Read a proof from a book, then try to articulate and write the proof in your own words. Then proof read, imagining that someone else wrote the exposition and try to figure out, which parts need more work and are difficult to comprehend. You will be receiving feedback on your homework and you should use this feedback to present your work better the next time.
If the homework is not stapled, the grader is not responsible for losing your work.There will be short (5-10 minutes) quiz each class.
Class Exam-I : March 2nd, Monday in class. The exam will be 75 minutes long.Practice Exam 1
Practice Exam 1 solutions
Class Exam-II : April 6th, Monday in class. The exam will be 75 minutes long. Practice Exam 2
Practice Exam 2 solutions
Final exam : May 13th, Wednesday 8:00AM - 9:50AM in class. The exam will be 110 minutes long. Practice Final Practice Final solutions
There will be no make up exams. Class exams will be closed book, closed notes. No internet/calculator allowed. Final exam will be open book, open notes, open computer, open internet, etc.