COURSE OUTLINE: MH1301

Course Title

Discrete Mathematics

Course Code

MH1301

Offered Study Year 1, Semester 2
Course Coordinator Chan Song Heng (Assoc Prof) chansh@ntu.edu.sg 6513 7453
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 2022/23 semester 2
Last revised 6 Jan 2023, 10:45

Course Aims

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.

Intended Learning Outcomes

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

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

Course Content

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

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Lectures
MCQ and Short Answer Questions 1, 2, 3, 4, 5, 6, 7, 8 1. a, b, c
 16 both See Appendix for rubric
Tutorials
Presentation and Participation 1, 2, 3, 4, 5, 6, 7, 8 1. a, b, c
2. a, c
3. a
 4 individual See Appendix for rubric
Mid-semester Quiz
Short Answer Questions 1, 2, 3, 4, 5, 6 1. a, b, c
2. a, c
3. a
 20 individual See Appendix for rubric
Examination (2 hours)
Short Answer Questions 1, 2, 3, 4, 5, 6, 7, 8 1. a, b, c
2. a, c
3. 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

Formative Feedback

For the rest of the OBTL article, we also use "Weekly Lecture Quizzes" when referring to the "Weekly MCQ and Short Answer Questions during Lecture".

Weekly Lecture Quizzes: feedback on common mistakes and the level of difficulty of the problems will be discussed during the lecture.

Tutorial Presentation and Participation: Any errors in the solution presented and feedback on the presentation will be given by tutor.

Mid-Semester Quiz: comments on answers and common errors are given to you after the exams are marked.

Learning and Teaching Approach

Lectures
(26 hours)

Derivation and demonstration:
Helps you understand the motivation behind mathematical notions and ideas.
Presents systematic ways to solve problems.

Problem solving:
Develops competence in solving a variety of problems related to counting, recurrence relations and graph theory.

Tutorials
(12 hours)

Derivation and demonstration:
Helps you understand the motivation behind mathematical notions and ideas.
Presents systematic ways to solve problems.

Problem solving:
Develops competence in solving a variety of problems related to counting, recurrence relations and graph theory.

Peer Instruction:
Develops communication and presentation skills and strengthens mathematical skill.

Reading and References

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

Course Policies and Student Responsibilities

Absence due to medical or other reasons

If you are sick and not able to attend the Mid-Semester Quiz, 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.

One Makeup Mid-Semester Quiz will be arranged if you have valid reasons for missing the Mid-Semester Quiz. If you are sick or are unable to attend the Makeup Mid-Semester Quiz, you must likewise perform the above two actions (1. send an email to instructor regarding absence and 2. submit original MC to an administrator). There will not be any further makeup quiz for those who missed the Makeup Mid-Semester Quiz.

For the Weekly Lectures Quizzes, there are no makeups if you did not attend lecture and missed the quiz. Also, there may not be makeups for Weekly Lecture Quizzes on lecture days that coincide with public holidays. The best 8 scores will be used to determine the total for this component. You should ensure that you are able to physically attend most, if not all the lectures conducted.

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
Chan Song Heng (Assoc Prof) SPMS-MAS-04-13 6513 7453 chansh@ntu.edu.sg

Planned Weekly Schedule

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;
Weekly Lecture Quiz 1

3

Binomial Theorem, Generalized Permutations and Combinations

 2, 3

Textbook 6.4, 6.5;
Weekly Lecture Quiz 2

4

Generalized Permutations

 2, 3

Textbook 6.5;
Weekly Lecture Quiz 3

5

Recurrence Relations, Linear Recurrence Relations

 4, 5

Textbook 8.1;
Weekly Lecture Quiz 4

6

Linear Recurrence Relations

 4, 5

Textbook 8.2;
Weekly Lecture Quiz 5

7

Graphs: Examples, Definitions, Representation

 6, 7

Textbook 10.1, 10.2, 10.3;
Weekly Lecture Quiz 6

8

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

 7, 8

Textbook 10.4, 10.5, 10.6;
Weekly Lecture Quiz 7

9

Graph Properties: Coloring, Planarity

 7, 8

Textbook 10.7, 10.8;
Weekly Lecture Quiz 8

10

Review of Counting and Recurrence Relations, Graphs

 1, 2, 3, 4, 5

Mid-Semester Quiz

11

Weighted Graphs

 7, 8

Textbook 10.1, 10.2;
Weekly Lecture Quiz 9

12

Directed Graphs

 6, 7, 8

Textbook 10.1, 10.2;
Weekly Lecture Quiz 10

13

Review of Graphs

 6, 7, 8

Weekly Lecture Quiz 11

Appendix 1: Assessment Rubrics

Rubric for Lectures: MCQ and Short Answer Questions (16%)

Point-based marking.

Note: You are allowed to discuss among yourselves if you wish to. So the quizzes can be completed based on individual or team effort. Marks are awarded based on your individual submission.

Rubric for Tutorials: Presentation and Participation (4%)

For Presentation: Participation is sufficient, students will not be assessed on the quality of presentation and solution.

For Participation: Actively involvement during tutorial, such as asking and answering questions.

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

Point-based marking

(not rubric based)

Rubric for Examination: Short Answer Questions (60%)

Point-based marking

(not rubric based)