# COURSE OUTLINE: MH8300

Course Title

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

### Course Aims

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.

### Intended Learning Outcomes

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

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

### Course Content

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

### Assessment

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

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.

### Learning and Teaching Approach

 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. You are to attempt the online practice questions immediately after the video to reinforce your learning. Lectures (6 hours) There will be 3 lectures (2 hours each): 1. The first lecture provides an overview of the course. 2. The second lecture is conducted during week 7 and provides formative feedback to you. 3. The final lecture is conducted during week 13 and reviews the content covered in 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

### Course Policies and Student Responsibilities

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

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

At the end of this topic, you should be able to:
- describe modular arithmetic,
-perform simple operations like addition, subtraction and multiplication,
- apply properties of modular arithmetic
- relate modular arithmetic to simple activities in real-life.

1, 2
2

At the end of this topic, you should be able to:
- describe modular arithmetic,
-perform simple operations like addition, subtraction and multiplication,
- apply properties of modular arithmetic
- relate modular arithmetic to simple activities in real-life.

1, 2
3

At the end of this topic, you should be able to:
- describe a code and determine its length, dimension, redundancy and rate
- describe the repetition code, the single parity code, the Hamming code
- perform simple encoding and decoding.

1, 2
4

At the end of this topic, you should be able to:
- describe the Reed-Solomon code
- perform simple encoding and decoding for Reed-Solomon codes.

1, 2
5

At the end of this topic, you should be able to:
- understand the concept of encryption and decryption,
- perform encryption and decryption for the Caesar, affine and monoalphabetic cipher.

1, 2
6

At the end of this topic, you should be able to:
- describe how Public Key Encryption works,
- understand the Diffie-Hellman key exchange protocol and RSA cryptosystem.
- perform modular exponentiation efficiently.

1, 2
7

At the end of this topic, you should be able to:
- define undirected and directed graphs
- define connected or strongly connected graphs

1, 3
8

At the end of this topic, you should be able to:
- define an Eulerian graphs
- determine if a graph is Eulerian and find an Eulerian path if the graph is Eulerian
- construct a de Bruijn graph and use it to solve a sequence assembly problem.

1, 3
9

At the end of this topic, you should be able to:
- define a matching
- determine the size of a maximum matching in bipartite graphs using the augmenting path algorithm
- determine a matching is of maximum size.

1, 3
10

At the end of this topic, you should be able to:
- find the length of a shortest path in a graph by applying either Dijkstra's or Bellman-Ford algorithm.

1, 3
11

At the end of this topic, you should be able to:
- define the Minimum Spanning Tree (MST) of a graph
- find the MST of a graph by applying either Kruskal's or Prim's algorithm
- apply cut optimality theorem to determine if a tree is a MST.

1, 3
12

At the end of this topic, you should be able to:
- find a TSP tour using the nearest neighbour heuristic
- derive lower bounds on the length of a shortest TSP tour

1, 3
13

At the end of this topic, you should be able to:
- Describe how PageRank aids in Google search
- Find an importance vector for an arbitrary webgraph and determine if it is unique
- Find the PageRank vector for an arbitrary webgraph using the Power Iteration Method.

1, 3

### Appendix 1: Assessment Rubrics

#### Rubric for Tutorials: Assignment (20%)

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.

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

Point-based marking.

#### Rubric for Examination: Short Answer Questions (50%)

Point-based marking.