Course Title | ## Discrete Mathematics | ||

Course Code | ## MH1301 | ||

Offered | Study Year 1, Semester 2 | ||

Course Coordinator | Guo Jian (Asst Prof) | guojian@ntu.edu.sg | 6514 8399 |

Pre-requisites | A or H2 level Mathematics or equivalent | ||

Mutually exclusive | MH1812 | ||

AU | 3 | ||

Contact hours | Lectures: 26, Tutorials: 12 | ||

Approved for delivery from | AY 2020/21 semester 1 | ||

Last revised | 13 Jun 2020, 16:49 |

This core course aims to develop your understanding of fundamental mathematical concepts such as basic counting principles, recurrence relations and basic graph theory concepts. We will cover various combinatorial aspects of graph theory and introduces some of the tools used to tackle graph theoretical questions. These concepts are essential for future mathematics courses. You will learn to understand and apply basic counting principles, and to model practical problems using graph models and apply graph algorithms to solve them.

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

- Describe basic counting rules and identify the scenarios where they are applicable
- Compare and differentiate permutations, combinations and their generalizations
- Apply appropriate counting rules to solve simple counting problems arising in other subfields of mathematics and practice
- Formulate recurrence relations from real-life counting problems
- Solve homogeneous and nonhomogeneous linear recurrence relations
- Define and relate basic notions in graph theory
- Represent real-life situations with graphs
- Apply algorithms and theorems from graph theory to analyze and solve realistic problems arising in science, engineering, business, and other disciplines

Basic of Counting, Inclusion-Exclusion Principle

Pigeonhole Principle, Permutations and Combinations

Binomial Theorem, Generalized Permutations and Combinations

Generalized Permutations

Recurrence Relations, Linear Recurrence Relations

Linear Recurrence Relations

Review of Counting and Recurrence Relations

Graphs: Examples, Definitions, Representation

Traversing Graphs: Shortest-, Euler-, Hamilton-Paths and Cycles

Graph Properties: Coloring, Planarity

Weighted Graphs

Directed Graphs

Review of Graphs

Component | Course ILOs tested | SPMS-MAS Graduate Attributes tested | Weighting | Team / Individual | Assessment Rubrics |
---|---|---|---|---|---|

Continuous Assessment | |||||

Tutorials | |||||

Homework | 1, 2, 3, 4, 5, 6, 7, 8 | 1. a, b, c3. a5. a | 20 | individual | See Appendix for rubric |

Mid-semester Quiz | |||||

Short Answer Questions | 1, 2, 3, 4, 5 | 1. a, b, c2. a, c3. a | 20 | individual | See Appendix for rubric |

Examination (2 hours) | |||||

Short Answer Questions | 1, 2, 3, 4, 5, 6, 7, 8 | 1. a, b, c2. a, c3. a | 60 | 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

## 2. Creativity

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

c. Develop new applications of existing techniques

## 3. Communication

a. Present mathematics ideas logically and coherently at the appropriate level for the intended audience

## 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

Weekly Homework: feedback on common mistakes and the level of difficulty of the problems will be discussed during the tutorial sessions

Midterm Test: comments on answers and common errors are given to you after the exams are marked.

Lectures (26 hours) | Derivation and demonstration: Problem solving: |

Tutorials (12 hours) | Derivation and demonstration: Problem solving: Peer Instruction: |

Kenneth H. Rosen: Discrete Mathematics and Its Applications, (7th edition), McGraw Hill, ISBN 978-981-4670-13-5

Absence due to medical or other reasons

If you are sick and not able to attend a midterm or missed the deadlines for your assignments, you must:

1. Send an email to the instructor regarding the absence.

2. Submit the original Medical Certificate* to an administrator.

*The Medical Certificate mentioned above should be issued in Singapore by a medical practitioner registered with the Singapore Medical Association.In this case, the missed assessment component will not be counted towards the final grade. There are no make-up quizzes or make-up midterm.

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 one of the lecturers.

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.

Instructor | Office Location | Phone | |
---|---|---|---|

Guo Jian (Asst Prof) | SPMS-MAS-05-01 | 6514 8399 | guojian@ntu.edu.sg |

Week | Topic | Course ILO | Readings/ Activities |
---|---|---|---|

1 | Basic of Counting, Inclusion-Exclusion Principle | 1, 3 | Textbook 6.1, 8.5 |

2 | Pigeonhole Principle, Permutations and Combinations | 2, 3 | Textbook 6.2, 6.3 |

3 | Binomial Theorem, Generalized Permutations and Combinations | 2, 3 | Textbook 6.4, 6.5 |

4 | Generalized Permutations | 2, 3 | Textbook 6.5 |

5 | Recurrence Relations, Linear Recurrence Relations | 4, 5 | Textbook 8.1 |

6 | Linear Recurrence Relations | 4, 5 | Textbook 8.2 |

7 | Review of Counting and Recurrence Relations | 1, 2, 3, 4, 5 | Midterm Test |

8 | Graphs: Examples, Definitions, Representation | 6, 7 | Textbook 10.1, 10.2, 10.3 |

9 | Traversing Graphs: Shortest-, Euler-, Hamilton-Paths and Cycles | 7, 8 | Textbook 10.4, 10.5, 10.6 |

10 | Graph Properties: Coloring, Planarity | 7, 8 | Textbook 10.7, 10.8 |

11 | Weighted Graphs | 7, 8 | Textbook 10.1, 10.2 |

12 | Directed Graphs | 6, 7, 8 | Textbook 10.1, 10.2 |

13 | Review of Graphs | 6, 7, 8 |

Point-based marking

(not rubric based)Point-based marking

(not rubric based)Point-based marking

(not rubric based)