COURSE OUTLINE: MH4300

Course Title

Combinatorics

Course Code

MH4300

Offered Study Year 4, Semester 1
Course Coordinator Kiah Han Mao (Asst Prof) hmkiah@ntu.edu.sg 6513 7185
Pre-requisites (MH1101 and MH1201 and MH1301) or (MH1201 and MH1301 and MH1802)
AU 4
Contact hours Lectures: 39, Tutorials: 12
Approved for delivery from AY 2021/22 semester 1
Last revised 9 Jun 2021, 11:12

Course Aims

This final year mathematics course aims to equip you to apply concepts in symbolic methods and combinatorics to solve a variety of problems related to algorithms. The tools developed in the course are useful for future graduate courses in mathematics, applied mathematics and engineering.

Intended Learning Outcomes

Upon successfully completing this course, you should be able to:

  1. Define a generating function and describe its role in enumerating combinatorial structures.
  2. Distinguish between ordinary, exponential and multivariate generating functions.
  3. Apply the symbolic method to compute combinatorial structures related to algorithms. Such structures include as trees, strings, permutations and mappings.
  4. Apply a variety of methods to extract asymptotic information from generating functions.

Course Content

Generating functions

Asymptotic approximations

Analytic combinatorics

Trees

Strings

Permutations

Words and mappings

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Tutorials
Assignment 1, 2, 3, 4 1. a, b, c, d
2. a, b, c
5. a
25 individual See Appendix for rubric
Mid-semester Quiz
Short Answer Questions 1, 2, 3 1. a, b, c
2. a, c
25 individual See Appendix for rubric
Examination (2 hours)
Short Answer Questions 1, 2, 3, 4 1. a, b, c
2. a, c
50 individual See Appendix for rubric
Total 100%

These are the relevant SPMS-MAS Graduate Attributes.

1. Competence

a. Independently process and interpret mathematical theories and methodologies, and apply them to solve problems

b. Formulate mathematical statements precisely using rigorous mathematical language

c. Discover patterns by abstraction from examples

d. Use computer technology to solve problems, and to communicate mathematical ideas

2. Creativity

a. Critically assess the applicability of mathematical tools in the workplace

b. Build on the connection between subfields of mathematics to tackle new problems

c. Develop new applications of existing techniques

5. Character

a. Act in socially responsible and ethical ways in line with the societal expectations of a mathematics professional, particularly in relation to analysis of data, computer security, numerical computations and algorithms

Formative Feedback

Assignment: Feedback is given after each individual assignment is returned. Students are allowed to resubmit for higher grades.

Midterms: Feedback is given after the midterm on the common mistakes and the level of difficulty.

Learning and Teaching Approach

Lectures
(39 hours)

Derivation and demonstration:
Explains the motivation behind the symbolic enumeration method.
Presents systematic ways to solve problems related to the concepts developed. Derives generating functions and use them to obtain asymptotic estimates.

Problem solving:
Develops competence in solving a variety of problems related to combinatorics.

Tutorials
(12 hours)

Derivation and demonstration:
Explains the motivation behind the symbolic enumeration method.
Presents systematic ways to solve problems related to the concepts developed. Derives generating functions and use them to obtain asymptotic estimates.

Problem solving:
Develops competence in solving a variety of problems related to combinatorics.

Peer Instruction:
Develops communication and presentation skills and deepen understanding. You will have the opportunity to work with peers and present your solution to the class.

Reading and References

An Introduction to the Analysis of Algorithms (2nd Ed.) by Sedgewick and Flajolet.
Addison-Wesley, 2013

ISBN: 978-0321905758

Course Policies and Student Responsibilities

You are encouraged to collaborate on the assignments because peer-to-peer learning helps you understand the subject better and working in a team trains you to better communicate with others. As part of academic integrity, crediting others for their contribution to your work promotes ethical practice.
You have to submit individual assignments, and hence, do take note of this collaboration policy:
• You have to write up every solution by yourself, even if you collaborated with others to solve the problem.
• You are to explicitly identify your collaborators in the assignment. If you did not work with anyone, you should write "Collaborators: none". If you obtained a solution through research (e.g., on the web), you must acknowledge the source, but write up the solution in your own words. If no collaboration statement is made at all, you will receive a warning. In case this happens repeatedly, a penalty will be applied.
• It is a violation of this policy to submit a problem solution that you cannot orally explain.
• It is a violation of the collaboration policy for you to permit anyone other than the lecturers and tutors to see your written solutions. Ideas may be shared, but do not share your written solutions with other students.
• If you have any questions about the collaboration policy, or if you feel that you may have violated the policy, please talk to the lecturers.

Academic Integrity

Good academic work depends on honesty and ethical behaviour. The quality of your work as a student relies on adhering to the principles of academic integrity and to the NTU Honour Code, a set of values shared by the whole university community. Truth, Trust and Justice are at the core of NTU’s shared values.

As a student, it is important that you recognize your responsibilities in understanding and applying the principles of academic integrity in all the work you do at NTU. Not knowing what is involved in maintaining academic integrity does not excuse academic dishonesty. You need to actively equip yourself with strategies to avoid all forms of academic dishonesty, including plagiarism, academic fraud, collusion and cheating. If you are uncertain of the definitions of any of these terms, you should go to the Academic Integrity website for more information. Consult your instructor(s) if you need any clarification about the requirements of academic integrity in the course.

Course Instructors

Instructor Office Location Phone Email
Kiah Han Mao (Asst Prof) SPMS-MAS-05-39 6513 7185 hmkiah@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Motivation of Analysis of Algorithms, Methods of Solving Recurrences

1

1.1, 1.4, 1.5, 1.6, 2.1, 2.2, 2.4, 2.5

2

Generating Functions

1, 2

3.1, 3.2, 3.3, 3.4, 3.8

3

Generating Functions (Continued)

1, 2, 3, 4

3.1, 3.2, 3.3, 3.4, 3.8

4

Asymptotic Approximations

4

4.1, 4.2, 4.4, 4.5

5

Asymptotic Approximations (Continued)

4

4.1, 4.2, 4.4, 4.5

6

Analytic Combinatorics

1, 2, 3

5.2, 5.3, 5.4, 5.5

7

Analytic Combinatorics (Continued)

1, 2, 3

5.2, 5.3, 5.4, 5.5

8

Trees

1, 3, 4

6.1, 6.4, 6.7, 6.8, 6.12

9

Strings

1, 3, 4

8.2, 8.3

10

Permutations

1, 3, 4

7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7, 7.8

11

Permutations (Continued)

1, 3, 4

7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7, 7.8

12

Words and Mappings

1, 3, 4

9.2, 9.3, 9.4, 9.5, 9.7, 9.8

13

Words and Mappings (Continued)

1, 3, 4

9.2, 9.3, 9.4, 9.5, 9.7, 9.8

Appendix 1: Assessment Rubrics

Rubric for Tutorials: Assignment (25%)

Point-based marking

Rubric for Mid-semester Quiz: Short Answer Questions (25%)

Point-based marking

Rubric for Examination: Short Answer Questions (50%)

Point-based marking