SFU Math Home > Courses > Outlines: Spring 06 > MACM 201
| MSSC All Levels | ||||
| 480-1 | 481-1 | |||
| MACM All Levels | ||||
| 201-3 | 201-3 S | 202-3 | ||
| 316-3 | 316-3 S | |||
| MATH 100 Level | ||||
| 100-3 | 100-3 S | 113-3 | ||
| 130-3 S | 150-4 S | 151-3 | ||
| 152-3 | 152-3 S | 154-3 | ||
| 155-3 | 155-3 S | 157-3 | ||
| 158-3 | 160-3 | 190-4 | ||
| MATH 200 Level | ||||
| 210-3 S | 232-3 | 232-3 S | ||
| 242-3 | 251-3 | 252-3 | ||
| MATH 300 Level | ||||
| 314-3 | 320-3 | 339-3 | ||
| 343-3 S | 345-3 | 348-3 S | ||
| MATH 400 Level | ||||
| 439-3 | 443-3 | 462-3 | ||
| 495-3 | ||||
| MATH 600 Level | ||||
| 604-4 | ||||
| MATH 700 Level | ||||
| 739-3 | 743-3 | 762-3 | ||
| MATH 800 Level | ||||
| 820-4 | 845-4 | |||
| APMA 900 Level | ||||
| 905-4 | 935-4 | |||
MACM 201-3
DISCRETE MATHEMATICS II
MATH OPEN LAB (room TBA)
DAY COURSE
Surrey Campus |
| Instructor: Dr. R. Pyke |
| Lab Coordinator: Dr. N. Kouzniak |
Prerequisite:
MACM 101
Textbook:
Discrete Combinatorial Mathematics An Applied Introduction, 5th edition by Ralph P. Grimaldi, published by Pearson Education. ISBN: 0-201-72634-3.
Calendar Description:
A continuation of MACM 101. Topics covered include graph theory, trees, inclusion-exclusion, generating functions, recurrence relations, and optimization and matching.
In addition to regularly scheduled lectures, students registered in these courses are encouraged to come to the Mathematics Open Laboratory (OPL) for assistance any time during posted working hours. At the OPL students will have the opportunity to meet with the lab co-ordinator, the teaching assistants and other students, and work together to understand mathematics in a friendly and helpful environment.
Outline:
- Inclusion-Exclusion
- 8.1 The Principle of Inclusion-Exclusion
- 8.2 Generalized Inclusion-Exclusion
- 8.3 Derangements
- 8.4 Rook Polynomials (optional)
- 8.5 Arrangements with Forbidden Positions (optional)
- Advanced Counting: Generating Functions
- 9.1 Introduction
- 9.2 Calculational Techniques
- 9.3 Partition of Integers
- Recurrence Relations
- 10.1 First-Order Linear Recurrences
- 10.2 Second-Order Homogeneous Linear Recurrences with Constant Coefficients
- 10.3 The Nonhomogeneous Recurrence
- 10.4 The Method of Generating Functions
- 10.6 Divide and Conquer Algorithms (optional)
- An Introduction to Graph Theory
- 11.1 Elementary Definitions
- 11.2 Subgraphs, Complements and Graph Isomorphism
- 11.3 Vertex Degree: Euler Trails and Circuits
- 11.4 Planar Graphs
- 11.5 Hamilton Paths and Cycles
- 11.6 Graph Coloring (not Chromatic Polynomials) (optional)
- Trees and Applications
- 12.1 Definitions and Properties
- 12.2 Rooted Trees
- 13.1 Dijkstra's Shortest-Path Algorithm
- 13.2 Minimum Spanning Trees: Kruskal's and Prim's Algorithms
- 12.5 Biconnected Components and Articulation Points (optional)
- 13.4 Matching Theory (optional)
Grading Scheme
- Homework/Quizzes - 15%
- Midterm I - 20%
- Midterm II - 20%
- Final Exam - 45%
THE INSTRUCTOR RESERVES THE RIGHT TO CHANGE ANY OF THE ABOVE INFORMATION
Students should be aware that they have certain rights to confidentiality concerning the return of course papers and the posting of marks. Please pay careful attention to the options discussed in class at the beginning of the semester.