Mathematics 121

Course Outline

LENGTH OF COURSE: One Semester (14 weeks)
 
CLASSROOM HOURS PER WEEK: 4 hours of lectures
 
NUMBER OF CREDITS: 3 credits
 
PREREQUISITE: Math 120.
 
DESCRIPTION OF COURSE:
A second course in discrete mathematics covering probability theory, generalized permutations and combinations, the binomial theorem, advanced counting techniques, recurrence relations, power series, generating functions, graphs, graph isomorphism and connectivity, planar graphs, assorted path problems, trees, trees and sorting algorithms and spanning trees. This course is designed for students of Mathematics, Computer Science, or Engineering.
 
COURSE OUTLINE
1) Counting and Probability(4 weeks)
Basic counting principles, inclusion-exclusion principle, pigeonhole principle, permutations and combinations, binomial coefficients, the binomial theorem, discrete probability and random variables, independence, expected value and variance of random variables, Bernoulli trials and Bernoulli random variables, generalized permutations and combinations.
 
2) Advanced Counting Techniques (4 weeks)
Formulating and solving recurrences, homogeneous and non-homogeneous recurrence relations with constant coefficients, divide and conquer recurrences, formal power series and generating functions, generating functions applied to counting problems and solving recurrence relations, more on inclusion-exclusion principle with applications.
 
3) Graphs (3 weeks)
Definitions and graph terminology, graph isomorphism, connectivity of graphs, Euler and Hamilton paths, shortest path problems, planar graphs with euler's formula and Kuratowski's theorem, graph coloring.
 
4) Trees (2 weeks)
Definitions and basic properties, trees and sorting algorithms, spanning trees, minimum spanning trees.
 
EVALUATION:
Three one-hour tests: 50%
Homework and participation: 10%
Fianl examination: 40%
 
TEXT BOOK:
Discrete Mathematics and its Applications, 4th edition Kenneth H. Rosen
 
TRANSFERABILITY:
Simon Fraser University - MACM 210 (3 credits)
University of British Columbia - CPSC 2nd (3 credits)
University of Victoria - Mathematics 222 (1.5 units)
 
INSTRUCTORS:
Kim Peu Chew, B.Sc.(Nanyang) M.A., Ph.D. ( British Columbia)
Sam Ekambaram, B.Sc., M.Sc. (Madras), M.Sc., Ph.D. (Simon Fraser)
Peter Hurthig, B.Sc., M.Sc. ( British Columbia)
David Medalen, B.A. (St.Olaf), M.Sc. ( British Columbia)