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

Section 1
Instructor(s) Chaudhary, Amitabh (amitabh)
Location Ryerson 276
Meeting Times Thursday 5:30pm - 8:30pm
Fulfills Immersion Math

Syllabus

Course Description

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

On completion of the course, students will be trained to think about and use mathematical concepts and techniques to solve problems, and to express 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, greatest common divisors, modular arithmetic, Chinese remainder theorem, Fermat's little theorem; counting, including permutations, combinations, binomial theorem, pigeonhole principle, inclusion/exclusion principle; discrete probability, including conditional probability, independence, Bayes's theorem, random variables, expected value, variance, covariance; graphs, including graph isomorphism, graph coloring, trees, planar graphs; recurrences and asymptotic notation. 

 

Textbook

Discrete Mathematics and its Applications (7th edition) (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095).

 

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.

Course Prerequisites

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

Other Prerequisites

Overlapping Classes

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

  • MPCS 55001-1 -- Algorithms
  • MPCS 52011-2 -- Introduction to Computer Systems
  • MPCS 51083-1 -- Cloud Computing
  • MPCS 51240-1 -- Product Management
  • MPCS 51044-1 -- C++ for Advanced Programmers

Eligible Programs

Masters Program in Computer Science MS in Computational Analysis in Public Policy (Year 1) 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)