50.050 Discrete Mathematics and Algorithm Design

Home / Education / Undergraduate / Courses / 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. 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), computational geometry (e.g. Gilbert-Johnson-Keerthi algorithm).

Pre-requisites

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 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, handshaking lemma, Sperner’s lemma
  • Trees, minimal spanning trees, Kruskal’s algorithm, Prim’s algorithm
  • Modular arithmetic, divisibility and primes, Euclidean algorithm, solving congruences, RSA algorithm
  • Integer representations, binary numbers, Hamming metric, introduction to coding theory, Huffman coding
  • Hamming codes, perfect codes, geometry of error correction codes
  • Geometry of Euclidean spaces, subspaces, hyperplanes, simplices, triangulations, polytopes, convex hulls, simplex algorithm
  • Minkowski sum/difference, GJK algorithm

Textbook(s) and/or Other Required Materials

“Discrete Mathematics and Its Applications” (6th Edition), by Kenneth Rosen

Course Instructor(s)

Prof Ernest Chong

Image Credit