MPCS 50103 Mathematics for Computer Science: Discrete Mathematics (Autumn 2023)

Section 1
Instructor(s) Agarwal, Ishan (ishanagarwal)
Location JCL 011
Meeting Times Wednesday 10:30am - 1:20pm
Fulfills Immersion Math

Syllabus

Course Description:

This course is an introduction to ideas and techniques from discrete mathematics that are commonly used in computer science. It emphasizes mathematical proof and problem solving, employed on a variety of useful and interesting topics: 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:

  • Mathematical reasoning and proofs: An introduction to mathematical reasoning, common logical fallacies, mathematical proofs and various proof techniques including, most importantly, mathematical induction.
  • Combinatorics: Counting, permutations, combinations, binomial theorem, pigeon hole principle, inclusion-exclusion principle, bijective counting, recurrences. 
  • Number Theory: Divisibility, prime numbers, modular arithmetic.
  • Discrete Probability: Random variables, expected value, variance, independence, conditional probability, Bayes rule, Markov inequality.
  • Graphs: Directed and undirected graphs, various representations of graphs, trees, paths, connectivity, Eulerian and Hamiltonian paths, bipartite graphs, matchings, graph colouring.

Course Activities:

  • Classes: Classes will typically consist of a lecture on the topic interspersed with problem solving/ related activities.
  • Office Hours: Regular office hours will be held by the course instructor as well as TAs. Attendance is optional but highly reccomended.
  • Problem Solving Sessions: Regular problem solving sessions will be held for the purpose of giving the students guided problem solving practice. Attendance is optional but highly reccomended.

Course Materials:

The course textbook is: Discrete Mathematics and its Applications (7th edition) (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095). 
The MIT Open Courseware textbook for their Mathematics for Computer Science course is also a good resource: MIT OCW textbook.
The class is intended to be self contained. Complete lecture notes will be provided for all the lectures. All problems in the problem sets will also be stated in full.

Evaluation:

The course grade will be based on homework, quizzes, a midterm and a final exam.

  • Homework (20%): There will be weekly homework to be submitted online.
  • Quizzes (20%): There will be two pre-announced in-class quizzes.
  • Midterm (20%)
  • Final (40%)

The exams will be closed-book/notes. There will be no make-up exams.

Prerequisites: 

Pre-calculus is a prerequisite. High school level familiarity with sets and functions, as well as common mathematical notation, will be assumed. 

Course Prerequisites

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

Other Prerequisites

Overlapping Classes

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

  • MPCS 56430-1 -- Introduction to Scientific Computing

Eligible Programs

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) Masters Program in Computer Science (new students) Masters Program in Computer Science