Course Title | ## It's a Discreetly Discrete World: Mathematics in Real-life Applications | ||

Course Code | ## MH8300 | ||

Offered | Study Year X, Semester 2 | ||

Course Coordinator | Kiah Han Mao (Asst Prof) | hmkiah@ntu.edu.sg | 6513 7185 |

Pre-requisites | AO or H1 Level Mathematics or equivalent | ||

AU | 3 | ||

Contact hours | Tutorials: 22, Technology-enhanced Learning: 13, Lectures: 6 | ||

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

Last revised | 9 Jun 2020, 09:06 |

This general education mathematics course demonstrates the influence of mathematics in our everyday life. The course aims to introduce tools in discrete mathematics, in particular, modular arithmetic and graph theory, and allows you (students both inside and outside the mathematics program) to explore real-life applications of these mathematical tools. Applications include error-correcting codes, cryptography, DNA sequence assembly, traveling salesperson problem, and Google's PageRank.

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

- Describe basic concepts in modular arithmetic and graph theory
- Apply modular arithmetic algorithms to solve problems in coding theory and cryptography
- Apply a variety of graph algorithms to solve certain graph theoretical problems

Modular arithmetic: addition, multiplication, inverses, exponentiation

Coding theory: repetition, single parity check, Hamming, Reed-Solomon codes

Cryptography: Caesar, affine, monoalphabetic ciphers, Diffie-Hellman key exchange protocol, RSA public key encryption

Graph theory: Eulerian graphs, maximum matching, shortest path problems, minimum spanning tree, traveling salesperson problem, PageRank computation

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

Continuous Assessment | |||||

Tutorials | |||||

Assignment | 1, 2, 3 | 1. a, c2. b3. a4. a5. a | 20 | team | See Appendix for rubric |

Mid-semester Quiz | |||||

Short Answer Questions | 1, 2 | 1. a, c2. b3. a4. a5. a | 30 | individual | See Appendix for rubric |

Examination (2 hours) | |||||

Short Answer Questions | 1, 2, 3 | 1. a, c2. b3. a4. a5. a | 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

c. Discover patterns by abstraction from examples

## 2. Creativity

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

## 3. Communication

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

## 4. Civic-mindedness

a. Develop and communicate mathematical ideas and concepts relevant in everyday life for the benefits of society

## 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 will be provided in the following manner.

1. During each tutorial, you will (in groups) work on a worksheet that covers material taught in the videos. Tutors will facilitate group discussions and guide the groups during the weekly sessions. After the tutorial, you will submit the worksheet and the tutors will grade the worksheets and provide feedback.

2. Feedback is given after the midterm on the common mistakes.

Tutorials (22 hours) | There will be 11 weeks of tutorials (2 hours each). During each tutorial, you will be assigned to groups that comprise students from various programs. As a group, you will apply concepts taught in the videos and use them to solve hypothetical problems. Open-ended questions will also be posed. In groups and drawing knowledge from the various academic disciplines, you will discuss and critique the mathematical techniques you learnt. |

Technology-enhanced Learning (13 hours) | Every week, you will watch short videos covering the relevant content. |

Lectures (6 hours) | There will be 3 lectures (2 hours each): 1. The first lecture provides an overview of the course. |

This is a general education course where elementary concepts from a variety of areas are introduced. Therefore, most texts and technical papers are beyond the scope of the course.

Nevertheless, we recommend the following readings for interested students. Readings are listed in the order of appearance.

[1] V. Guruswami, A. Rudra, M. Sudan. Essential Coding Theory. Draft available at https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf (Chapters 1, 2, 5)

[2] J. Holden. The Mathematics of Secrets: Cryptography from Caesar Ciphers to Digital Encryption. ISBN: 9780691141756. (Chapters 1, 6, 7)

[3] W. J. Cook. In Pursuit of the Traveling Salesman. ISBN: 9780691163529 (Chapters 3, 4)

[4] K. Bryan, T. Leise. The $25,000,000,000 Eigenvector: The Linear Algebra behind Google. SIAM Review. Vol. 48 (3), pp. 569–581

(1) General

You are expected to diligently watch all online videos and attempt the practice questions. While you are not expected to complete the tutorials prior to class, please be aware of the topic that will be covered and participate wholeheartedly in discussions with your group mates. A general observation: students who struggle together do well in the course together.

(2) Absenteeism

Missing a tutorial without a valid reason will mean an automatic zero for the tutorial marks awarded for that week. Presenting an valid reason confers on you the *right* to make up the grade for your missed class, but it does not automatically make up for the missed class. If you miss a tutorial, you must inform your tutor via email and the tutor will provide instructions on how to make up the grade. Past data demonstrates a strong correlation between in-class participation and the final course grade.

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

Kiah Han Mao (Asst Prof) | SPMS-MAS-05-39 | 6513 7185 | hmkiah@ntu.edu.sg |

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

1 | At the end of this topic, you should be able to: | 1, 2 | |

2 | At the end of this topic, you should be able to: | 1, 2 | |

3 | At the end of this topic, you should be able to: | 1, 2 | |

4 | At the end of this topic, you should be able to: | 1, 2 | |

5 | At the end of this topic, you should be able to: | 1, 2 | |

6 | At the end of this topic, you should be able to: | 1, 2 | |

7 | At the end of this topic, you should be able to: | 1, 3 | |

8 | At the end of this topic, you should be able to: | 1, 3 | |

9 | At the end of this topic, you should be able to: | 1, 3 | |

10 | At the end of this topic, you should be able to: | 1, 3 | |

11 | At the end of this topic, you should be able to: | 1, 3 | |

12 | At the end of this topic, you should be able to: | 1, 3 | |

13 | At the end of this topic, you should be able to: | 1, 3 |

Point-based marking.

In principle, you will receive the same marks as your teammates; however, if there is sufficient evidence or feedback from your peers, your marks may vary according to your level of contribution to the team.