MATH 125  INTRODUCTION TO DISCRETE MATHEMATICS 
WHAT IS DISCRETE MATHEMATICS? 

The following are examples of problems from discrete mathematics: 

In how many ways can 12 different problems be distributed among 20 students if no student gets more than one problem and each problem is assigned to at most one student? How many social security numbers have no repeated digits? Find all integers n such that "n2 + l" is a multiple of 11. (Travelling Salesman Problem) A salesman must go on a sales trip, beginning at his hometown H, visiting each of the cities A, B, C, D, E, F, and G. Under what conditions is it possible for him to do so in such a way that he visits each of the cities exactly once and then returns home? If possible, design an algorithm (stepbystep process) that provides a solution to the Travelling Salesman Problem.

Notice that each problem deals with a finite collection of objects, a finite process, or the positive integers 1, 2, ...... 

Any problem that involves a finite collection of objects or a finite process is a problem in discrete mathematics. This course serves as an introduction to some of the basic techniques of the discipline, including methods of counting, modular arithmetic, and formal logic. The focus of the course will be on formulating problems into mathematical models, and on methods applicable to the analysis of these models. 


INTENDED AUDIENCE 

Students who are interested in a career in Mathematics, Computing Science, or Engineering. 


PREREQUISITES 

One of the following: C+ or better in Principles of Math 12; or C or better in one of MATH 124, Foundations of Mathematics 12, or Precalculus 12; or C or better in both MATH 094 and MATH 095; or B or better in Applications of Math 12; or MATH 110. 




TRANSFERABILITY 

Open University, SFU and UVic (unassigned first year course credit for UBC). 




The Konigsberg Puzzle 

Seven bridges connect the four parts of the town. Is it possible to make a journey crossing each bridge once, and only once? 



