Section | 2 |
---|---|

Instructor(s) | Singh Sahota, Davender (dsahota) |

Location | Online Only |

Meeting Times | Wednesday 5:20pm - 7:20pm |

Fulfills | Immersion Math |

***This course will be conducted remotely and will be online only for Autumn 2020***

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 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, incuding divisibility, prime numbers, and modular arithmetic; 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; graphs, including graph isomorphism, Euler and Hamiltonian paths and circuits, trees, and graph coloring; recurrences and asymptotic notation. ** **

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

• Lectures: Students are responsible for all material presented in lectures.

• Homework: Weekly homework assignments are assigned after class and are due at the start of the next class. Students are required to submit homework electronically.

• Exams: There is a midterm exam (week 6), and a final exam (week 11). There will be no make-up exams.

**Course grade**

The course grade is based on attendance/participation, homework, and exams.

• Attendance/Participation: 10%.

• Homework: 20%.

• Midterm examination: 30%.

• Final examination: 40%.

**Textbook**

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

**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 50101 Concepts of Programming (completed or concurrently taking) OR successfully passing the Programming Placement exam.

MPCS Students only.

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

- MPCS 51230-1 -- User Interface and User Experience Design
- MPCS 52011-1 -- Introduction to Computer Systems
- MPCS 53112-1 -- Advanced Data Analytics
- MPCS 56420-1 -- Bioinformatics for Computer Scientists