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

Syllabus PDF: Please look at the attached syllabus (Winter 2024 version) for full details about the class. There may be small changes in this iteration of the class.

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: combinatorics, 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, Euclid's division algorithm, prime numbers, modular arithmetic, Fermat's little theorem.
• Discrete Probability: conditional probability, independence, Bayes rule, random variables, expected value, linearity of expectation, variance, Markov's inequality, the probabilistic method as a proof technique.
• Graphs: Directed and undirected graphs, various representations of graphs, graph isomorphism, graph colouring, paths, connectivity, Eulerian and Hamiltonian paths, trees, bipartite graphs, matchings.
  
  

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. Optional resubmissions will be allowed for homework; in these resubmissions students are expected to incorporate grader feedback.
• Quizzes (20%): There will be two pre-announced quizzes, one before the midterm and one after the midterm.
• Midterm (20%)
• Final (40%)

The quizzes/exams will be closed-book/notes.

Prerequisites: 

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

MPCS 50101 Concepts of Programming (completed or concurrently taking) or a PASS on the Programming Placement exam.

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

• MPCS 55003-1 -- Intermediate Algorithms

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