50.050 Discrete Mathematics and Algorithm Design
Course information
An in-depth understanding of Computer Science requires strong mathematical foundations. In this course, students will learn the foundations of discrete mathematics and other mathematical areas, with an emphasis on understanding the underlying mathematics for algorithms beyond those covered in 50.004 Algorithms. Through this course, students will appreciate the wide applicability of mathematics for algorithms in artificial intelligence, communications, computer graphics, cybersecurity, data analytics, robotics, etc. Topics include: Counting methods, logic and proof methods, graph theory (incl. graph colorings, matchings, Ramsey theory), graph algorithms (e.g. Fleury’s algorithm, Kosaraju’s algorithm, Kruskal’s algorithm, Prim’s algorithm), number theory (e.g. modular arithmetic, Euclidean algorithm), coding theory (e.g. Huffman coding, Hamming codes), convex geometry (e.g. polytopes, Voronoi diagrams), computational geometry (e.g. Fortune’s algorithm, Gilbert-Johnson-Keerthi algorithm).
Pre-requisites / Co-requisites
- 50.004 Algorithms (can be taken as co-requisite)
- 10.018 Modelling Space and Systems (for Intake Y2020 and subsequent batches)
Learning Objectives
At the end of the term, students will be able to:
- Understand basic concepts in set theory and logic.
- Apply counting methods and proof methods in solving problems.
- Demonstrate familiarity with graph-theoretic terminology and concepts.
- Analyze structural properties in graphs.
- Understand the applications of graph algorithms.
- Solve problems using Kruskal’s algorithm and Prim’s algorithm.
- Understand Sperner’s lemma and its applications.
- Understand basic concepts in elementary number theory.
- Apply Huffman coding to data compression.
- Understand the geometry of error correction codes.
- Demonstrate familiarity with data encoding/decoding using Hamming codes.
- Understand basic geometric concepts in convex geometry and computational geometry.
- Understand Voronoi diagrams and Fortune’s algorithm.
- Understand the Gilbert-Johnson-Keerthi (GJK) algorithm.
Measurable Outcomes
- Solve counting problems via multiple counting methods.
- Write mathematical proofs that incorporate various proof methods.
- Compute matchings in graphs.
- Design simple graph algorithms.
- Design algorithms for fair resource division using Sperner’s lemma.
- Compute minimal spanning trees using Kruskal’s algorithm and Prim’s algorithm.
- Solve congruence equations.
- Apply encoding/decoding techniques to data.
- Analyze the correctness of algorithms using mathematical concepts.
Topics Covered
- Sets, set relations, bijections, cardinality and (un-)countability of sets, propositional logic, predicates and quantifiers, counting methods, permutations & combinations, inclusion-exclusion principle
- Binomial coefficients and identities, proof methods, induction, well-ordering principle, invariance, extremal principle
- Graph colorings, planar graphs, Euler’s formula, four-color theorem, pigeonhole principle, Ramsey theory
- Graph representations, graph isomorphism, graph invariants, bipartite graphs, graph matchings
- Graph connectivity, Eulerian paths and cycles, Fleury’s algorithm, Kosaraju’s algorithm, Sperner’s lemma
- Trees, minimal spanning trees, Kruskal’s algorithm, Prim’s algorithm
- Modular arithmetic, divisibility and primes, Diophantine equations, Euclidean algorithm, solving congruences, Fermat’s little theorem, RSA algorithm
- Integer representations, machine representations of numbers, binary numbers, Hamming metric, introduction to coding theory, Huffman coding
- Hamming codes, perfect codes, geometry of error correction codes
- Geometry of Euclidean spaces, convex hulls, affine geometry, half-spaces, hyperplanes, simplices, polytopes, geometry of simplex algorithm
- Voronoi diagrams, Fortune’s algorithm
- Cones, conic hulls, Minkowski sums, GJK algorithm
Textbook(s) and/or Other Required Materials
“Discrete Mathematics and Its Applications” (6th Edition), by Kenneth Rosen
Course Instructor(s)