Description
Material
Syllabus
##### Description

This course looks at modeling and solving problems that involve discrete objects. The course starts with the study of integer numbers and using techniques for manipulating numbers we learn how real-world problems such as RSA encryption can be solved. The course then moves to basic propositional logic. Students will learn how to apply formal logic to determine if an argument is valid and will also indirectly use logic in proofs throughout the course. With numbers and logic as underpinnings, students will then learn proof techniques such as induction. Much of the course is then focused on counting, in particular learning tools for counting large groups of discrete objects and for determining the probability of discrete events occurring. These techniques in combinations and permutations are then applied to some problems in error-detection and error-correcting codes. Students will then learn about relations, including equivalence relations and partial orders. It will be shown how results from partial orders can be used to do computer job scheduling. An introduction to graph theory (which can be used to represent the relationship between discrete objects) will be given. Students will learn how to find certain kinds of paths through graphs (Euler circuits) and will see how such paths can be used to solve an analog-to-digital conversion problem. Some of the material in this course is also covered in or complemented by ELEC271, ELEC276 and ELEC278.

##### Objectives

Objectives and goals in this course are as follows:

• Compute inverses in modular arithmetic and use them to solve linear congruences.
• Apply the concepts of modular arithmetic to solve RSA encryption/decryption problems.
• Use a selection of proof techniques such as mathematical induction and formal logic to solve mathematical problems.
• Understand, reason about and perform complex mathematical proofs.
• Use techniques such as inclusion-exclusion, the pigeonhole principle and various results in combinations and permutations to count large groups of objects.
• Apply counting tools to games of chance (such as lotteries, poker).
• Work with, manipulate and reason about relations, including equivalence relations and partial orders.
• Apply partial orders to do computer job scheduling.
• Know enough graph theory to understand the information conveyed by an undirected or directed graph, determine if two graphs are isomorphic, and find Euler circuits in graphs.

Lecture: 3
Lab: 0
Tutorial: 0.5