Section | 1 |
---|---|

Instructor(s) | Brady, Geraldine (gb52) |

Location | JCL 298 (In-Person or Online) |

Meeting Times | Wednesday 5:30pm - 8:30pm |

Fulfills | Immersion Math |

**Course d****escription**

This course is an introduction to ideas and techniques from discrete mathematics that are used in computer science. It emphasizes mathematical proof and problem solving, employed on a variety of useful and interesting examples in counting, discrete probability, graphs, and basic number theory.

On completion of the course, students will be practiced in using mathematical concepts and techniques to solve problems, and in expressing mathematical notions precisely. They will be able to use ideas and techniques from discrete mathematics in subsequent courses in computer science, in particular courses in the design and analysis of algorithms, networks, numerical methods, software engineering, data analysis, and machine learning.

**Course contents**

Topics covered include: methods of proof, including mathematical induction; number theory, including divisibility, prime numbers, modular arithmetic, with applications to cryptography; counting, including permutations, combinations, binomial theorem, pigeonhole principle, inclusion-exclusion principle; discrete probability, including conditional probability, independence, Bayes's rule, random variables, expected value, variance, Markov and Chebyshev bounds; graphs, including graph isomorphism, Euler and Hamiltonian paths, trees, graph coloring, and planar graphs; recursion. ** **

**RequirementsStudents are responsible for all material presented in lectures and on homework assignments.**

• Lectures: Course material from the current week will be presented in lecture format at the class meetings.

• Homework: Weekly homework assignments are assigned after class and due the night before the next class. Homework must be submitted electronically. **Students are required to submit weekly homework to pass the course.**

• Exams: There will be a midterm exam and a final exam. There will be no make-up exams.

**Course grade**

The course grade is based on weekly homework assignments and exams.

• Homework: 10%.

• Midterm examination: 30%.

Discrete Mathematics and its Applications (7th edition) (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095). Course notes of MIT's Mathematics for Computer Science

**Prerequisites**

Precalculus, especially logarithms and exponentials, is a prerequisite; calculus is recommended. High-school level familiarity with sets, functions, relations, and mathematical notation will be assumed.

MPCS 50101 Concepts of Programming (completed or concurrently taking) OR passing the Programming Placement exam.

This course requires competency in Unix and Linux. Please plan to attend the MPCS Unix Bootcamp (https://masters.cs.uchicago.edu/page/mpcs-unix-bootcamp) or take the online MPCS Unix Bootcamp Course on Canvas. This course requires weekly homework submissions. Homework must be prepared and submitted electronically.

This class is scheduled at a time that conflicts with these other classes:

- MPCS 53113-1 -- Natural Language Processing

Masters Program in Computer Science
MS in Computational Analysis in Public Policy (Year 2)
MA in Computational Social Science (Year 1)
MA in Computational Social Science (Year 2)
Bx/MS in Computer Science (Option 3: Profesionally-oriented - Non-CS Majors)