MPCS 50103 Mathematics for Computer Science: Discrete Mathematics (Summer 2025)

Course Overview [WATCH VIDEO]

Course Description
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 number theory, counting, discrete probability, and basic graph 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, incuding divisibility, prime numbers, and modular arithmetic; counting, including permutations, combinations, binomial theorem, pigeonhole principle, inclusion/exclusion principle, and recurrences; discrete probability, including conditional probability, independence, Bayes's rule, random variables, expected value, variance, Markov and Chebyshev bounds; graphs, including graph isomorphism, graph connectivity; trees; Euler and Hamiltonian paths and circuits, graph coloring, and matching.

Requirements
Students are responsible for all material presented in lectures and on homework assignments.

• Class sessions: Course material will be presented in lecture format at the class meetings.
• Homework: All students are required to submit homework weekly. Weekly homework assignments are assigned after class and due the day before the next class.  Students are required to submit homework electronically.
•  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 homework and exams.

• Homework: 10%
• Midterm examination: 30%
• Final examination: 60%

Textbook
Discrete Mathematics and its Applications (7th ed.) (McGraw-Hill) by Kenneth Rosen (ISBN 978-0073383905)

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

MPCS Students:
MPCS 50101 Concepts of Programming (completed or concurrently taking) OR a PASS on MPCS Programming Placement Exam I.

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

• MPCS 56605-1 -- Introduction to Blockchain and Smart Contracts
• MPCS 53001-1 -- Databases
• MPCS 51238-1 -- Design, Build, Ship

MS in Computational Analysis in Public Policy (Year 1) MS in Computational Analysis in Public Policy (Year 2) MS in Molecular Engineering 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) Masters Program in Computer Science Masters Program in Computer Science (new) Placement: Pass I Masters Program in Computer Science (new) Placement: Pass I + II Masters Program in Computer Science (new) Placement: Pass I + II (w/ Advanced) Masters Program in Computer Science (Immersion)