This course introduces the student to the basic subjects of discrete mathematics, which forms the mathematical foundation of computer and information science. The course will include small projects in SageMath.

Prerequisites

 Common requirements and some knowledge of elementary combinatorics and finite sample spaces

Faculty Fall 2019

Octavio ARIZMENDI ECHEGARAY

On completion of the course, students will:

• strengthen mathematical thinking and problem-solving abilities;
• know a range of discrete models and topics which are found in applications in modern fields like data science;
• develop confidence in working with discrete mathematical objects on a computer programming language.

This course is intended for 14 weeks which include 5 small computer labs.

1. Logic, proofs, and induction (2 weeks)
   Elements of logic. Basic proof techniques. Proof by cases and geometry. Induction, Well-order. Inductive definitions.
2. Sets, functions and relations (1 week)
   Relations (ordered pairs). Functions. Data bases and sets.
   Computer lab: Programming functions.
3. Recurrence and generating functions in algorithms (2 weeks) Recurrences and recursive functions. Fibonacci numbers. Linear recurrence relations with constant coefficients. Rational power series. Arrangements and involutions. Generating functions. Exponential generating function.
   Computer lab: Multiplying polynomials and formal series.
4. Number theory (2 weeks)
   Divisibility. Modular arithmetic. Primes. Euler function. RSA cryptosystem. Computer lab: Encryption.
5. Counting (2 weeks)
   Factorial and binomial coefficients. Pascal triangle. Permutations and combinations. Combinatorial identities. Inclusion-exclusion principle. Double counting and pigeonhole principle.
6. Combinatorics and probability (1 week)
   Computing probabilities in classical problems. Bernoulli trials. Law of large numbers. Central limit theorem.
   Computer lab: Playing with Pascal triangle.
7. Trees (1 week)
   Expanding trees. Binary trees. Rooted trees.
8. Advanced graph theory (2 weeks)
   Graph coloring. Connectivity. Hamiltonian and Eulerian paths. Graph isomorphism. Introduction to spectral graph theory.
   Computer lab: Generating random graphs.
9. Probabilistic methods (1 week)
10. Basic inequalities in probability. First moment method. Second moment method.

Bibliography

1. Alon, Noga; Spencer, Joel H. (2004). The Probabilistic Method, John Wiley & Sons.
2. Newman, Mark (2010). Networks: an Introduction, Oxford University Press.
3. Rosen, Kenneth H. (2007). Discrete Mathematics and its Applications, McGraw-Hill Education.
4. Wilf, Herbert S. (2006). Generating Functionology, CRC Press.
5. Anderson, Ian (1989). Combinatorics of Finite Sets, Oxford University Press.
6. Diestel, Reinhard (1994). Graph Theory, Graduate Texts in Mathematics, Springer.
7. Knuth, Donald E.; Graham, Ronald L.; Patashnik, Oren (1994). Concrete Mathematics, A Foundation for Computer Science, 2nd. Edition, Pearson.
8. Lovász, László; Pelikán, József; Vesztergombi, Katalin (1999). Discrete Mathematics: Elementary and Beyond, Springer.

Support Sessions

2 hours per week with a teaching assistant.

Grading

Two midterm exams (40%), homework (40%), a simulation project to be submitted/ presented by the end of the course (20%).