Some Courses

AAM10C Finite Mathematics

AAM343 Combinatorial Analysis

AAM438 Graph Theory

MSM912 Discrete Mathematics for Educators

MSM941 Selected topics of graph theory

MSM942 Applications of graph theory

AAM10C Finite Mathematics

Course Topics:

· Basic principles of counting;

· the numbers of permutations and combinations, their relation;

· different types of combinations and permutations;

· apply binomial theorem and other combinatorial properties to study some identities

· apply pigeonhole principle to study the existence of some type of objects

· fundamental concepts on sample space, probability distributions;

· conditional probability and apply it to study the probability of some event;

· study the probability of independent events.

References:

• C.C. Chen and K.M. Koh, Principles and techniques in combinatorics, World Scientific, 1992.
• Khee Meng Koh and Eng Guan Tay, Counting. World Scientific, 2013.

Tutorials: Around 10 homework, and solutions are provided during tutorials.

Assessment Mode: Three tests and final exam.

AAM 43J Graph Theory

Lecturer	A/P Dong Fengming
Text Book	K.M. Koh, F.M. Dong and E.G. Tay, Introduction to Graph Theory, World Scientific, 2007. Everyone taking this module should have one copy. It can be bought from NIE, NTU or NUS bookstores. It is also available from the above link ($36 for softcover). Chapter 1 can be downloaded.
Topics	Chapter 1 Fundamental concepts and basic results (1.1) Multigraphs and graphs (1.2) Vertex degrees (1.3) Paths, cycles and connectedness
	Chapter 2 Graph isomorphism, subgraphs and the complement of a graph (2.1) Isomorphic graphs and isomorphism (2.2) Testing isomorphic graphs (2.3) Subgraphs of a graph (2.4) The complement of a graph
	Chapter 3 Bipartite graphs and trees (3.1) Bipartite graphs (3.2) Trees
	Chapter 4 Vertex-colourings of graphs (4.1) Vertex-colourings and chromatic number (4.2) Enumeration of chromatic number (4.3) Greedy colouring algorithm (4.4) Brooks’ Theorem

Assessment: Three tests and final exam.

AAM33J Combinatorial Analysis

Lecturer:

A/P Dong Fengming

Course Description:

1. Application of the general inclusion-exclusion formula to study Stirling numbers of the Second Kind, derangements, Euler j-function, etc.
2. Application of the generating functions and exponential generating functions to study problems on distributions of objects, partitions of integers, etc.
3. (Optional) Application of recurrence relations to study sequences. For example, we will study how to find an expression for the general term a_n, if a₀=2, a₁=3 and a_n=3a_n-1-2a_n-2 for all n≥2.

References:

• Anderson, A first course in combinatorial mathematics, Oxford University Press, 1989.
• R.A. Brualdi, Introductory combinatorics, Prentice-Hall, INc, 1999.
• C.C. Chen and K.M. Koh, Principles and techniques in combinatorics, World Scientific, 1992.

Lecture Note: It will be provided. Chapter one is available now. But it may be modified at the beginning of the semester.

Topics:

Chapter 1. The Principle of Inclusion and Exclusion

(1.1) Introduction

(1.2) The principle of inclusion and exclusion

(1.3) A generalization

(1.4) Surjective mappings

(1.5) Derangements

(1.6) Erler φ-functions

Chapter 2. Generating Functions

(2.1) Ordinary generating functions

(2.2) Operations on generating functions

(2.3) Some modelling problems

(2.4) Partitions of integers

(2.5) Exponential generating functions

Chapter 3. (Optional) Recurrence Relations

(3.1) Introduction

(3.2) Examples of applying recurrence relations

(3.3) The first order linear recurrence relation a_n=pa_n-1+q

(3.4) The second order linear recurrence relation a_n=pa_n-1+qa_n-2+r

Assessment: Two tests and final exam.

MSM912

Discrete Mathematics for Educators

Part 1: Foundation of Combinatorics

(1.1) Basic Counting Principles

(1.2) Bijection Principle

(1.3) Binomial Theorem

(1.4) Pascal’s Triangle

Part 2: Foundation of Graph Theory

(2.1) Introduction of Graphs

(2.2) Graph isomorphism and subgraphs

(2.3) (Optional) Hamiltonian Graphs

Text Book for Part 1:

Koh K.M. and Tay E.G/ (2002). Counting. World Scientific.

The book can be bought from NIE, NTU or NUS bookstores. It is also available from the above link.

Lecture note for part 2 will be provided.

Assessment: Two tests and presentations.

MSM 941

Selected Topics in Graph Theory

Topics

1. Isomorphism of graphs

2. Vertex-colorings of graphs

3. Planar graphs

4. Chromatic polynomials of graphs

References:

· Koh, K. M., Dong, F., Ng, K. L., & Tay, E. G. (2015). Graph Theory: Undergraduate Mathematics. World Scientific Publishing Company.

· Fengming Dong, K.M. Koh and K.L. Teo,  Chromatic Polynomials and Chromaticity of Graphs, World Scientific, Singapore, 2005.

Lecture note will be provided.

Assessment: Three tests and presentations.

MSM 942

Applications of Graph Theory

Topics

1. Digraphs, Orientations and Tournaments
2. Applications of Graph Theory
3. Complexity

References:

· Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications (Vol. 290). London: Macmillan.

· Koh, K. M., Dong, F., Ng, K. L., & Tay, E. G. (2015). Graph Theory: Undergraduate Mathematics. World Scientific Publishing Company.

· West, D. B. (2001). Introduction to graph theory (Vol. 2). Upper Saddle River: Prentice hall.

· Wilson, R. J. (1979). Introduction to graph theory. Pearson Education India.

Lecture note will be provided.

Assessment: Two tests and presentations.