COURSE OUTLINE: MH3400

Course Title

Algorithms for the Real World

Course Code

MH3400

Offered Study Year 3, Semester 2
Course Coordinator Thomas Peyrin (Assoc Prof) thomas.peyrin@ntu.edu.sg 6513 2027
Pre-requisites {MH1201, MH1301, MH1402, MH2500}OR{MH1201, MH1301, MH1403, MH2500}
AU 4
Contact hours Lectures: 39, Laboratories: 26
Approved for delivery from AY 2019/20 semester 2
Last revised 10 Dec 2019, 09:03

Course Aims

With the development of digitalization, algorithms have become more and more pervasive in our lives, and this trend is likely to accelerate in the future. Almost all industries are now widely embracing the possibilities offered by efficient algorithms. How can companies with a huge amount of data search in their database? How can your map application find the shortest path from your location to a certain destination? How can Internet packets be routed to maximize the efficiency of the network? How can you render electricity distribution more efficient? How booking websites manage to find for you the best hotels according to several criterions? Etc.

The aim of this course is to show you some crucial algorithmic paradigms, while using strong connections to real-world applications as examples. This will allow you to learn new problem-solving techniques and very important algorithms, while developing your general knowledge in where and how algorithms are actually used in real-world applications.

Intended Learning Outcomes

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

  1. Formulate a problem and express its solution in such a way that a computer can effectively carry it out
  2. Code efficient algorithms in Python for sorting or searching into large amount of data
  3. Represent certain real-life problem as a graph instance
  4. Apply efficient algorithms to solve realistic problems related to graphs
  5. Identify what algorithmic paradigm to use for various classical types of problems

Course Content

Complexity

Divide and Conquer

(balanced) Binary search trees

Advanced sorting

Dynamic programming

Linear programming

Integer programming

Graphs

Shortest path

Minimum spanning trees

Network flow

Assessment

Component Course ILOs tested SPMS-MAS Graduate Attributes tested Weighting Team / Individual Assessment Rubrics
Continuous Assessment
Laboratories
Assignment 1, 2, 3, 4 1. a, d
2. a
4. a
5. a
 25 individual See Appendix for rubric
Mid-semester Quiz
Midterm exam 1, 3, 4, 5 1. a
2. a
 25 individual See Appendix for rubric
Examination (2 hours)
Final exam 1, 3, 4, 5 1. a
2. 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

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

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

Feedback on common mistakes and the level of difficulty of the problems will be discussed during the tutorial/lab sessions (LO 1,2,3,4,5)

Comments on answers and common errors are given to you after the midterm/final exams are marked (LO 1,3,4,5)

For laboratory assignments, individual feedback will be provided to you through the evaluation of your submissions (LO 1,2,3,4,5)

Learning and Teaching Approach

Lectures
(39 hours)

Lectures will serve to introduce the algorithmic concepts necessary for the course, as well as examples to illustrate these concepts (LO 1,3,4,5).

Laboratories
(26 hours)

Practice is really key to this course and tutorials/lab sessions play a central role. During the tutorials/lab sessions, the students are expected to try to solve the tutorial exercises by themselves using Python, and only check the solutions provided after having spent some efforts solving the problem. This will develop the ability of the students to understand a problem and design algorithms to solve it. Tutors will help the students by guiding them in finding the solution by themselves. (LO 1,2,3,4,5)

Reading and References

Algorithm Design and Applications, Michael T. Goodrich and Roberto Tamassia, WILEY, 1st Edition, ISBN-13 978-1118335918

Course Policies and Student Responsibilities

As a student of the course, you are expected to attend the lectures and the tutorial/lab sessions, and to take all scheduled assignments by due dates. Not submitting a lab assignment before the corresponding deadline will be counted as no submission. Students are expected to take responsibility to follow up with course notes, assignments and course related announcements they have missed.

As a student of the course, you are required to abide by both the University Code of Conduct and the Student Code of Conduct. The Codes provide information on the responsibilities of all NTU students, as well as examples of misconduct and details about how you can report suspected misconduct. The university also has the Student Mental Health Policy. The Policy states the University’s commitment to providing a supportive environment for the holistic development of students, including the improvement of mental health and wellbeing. These policies and codes concerning students can be found in the following link.
http://www.ntu.edu.sg/SAO/Pages/Policies-concerning-students.aspx

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
Thomas Peyrin (Assoc Prof) SPMS-MAS-05-14 6513 2027 thomas.peyrin@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Complexity

 1

Presentation slides are lecture notes.

2

Divide and Conquer

 1, 2, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

3

(balanced) Binary search trees

 1, 2, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

4

Advanced sorting

 1, 2, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

5

Dynamic programming

 1, 2, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

6

Linear programming

 1, 2, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

7

Midterm

 5

No lecture (midterm), no lab session/tutorial.

8

Integer programming

 1, 2, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

9

Graphs

 1, 2, 3, 4, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

10

Shortest path

 1, 2, 3, 4, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

11

Minimum spanning trees

 1, 2, 3, 4, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

12

Network flow

 1, 2, 3, 4, 5

Presentation slides are lecture notes. Programming assignment related to the week's course.

13

Revision

 5

Revision lecture, no lab session/tutorial.

Appendix 1: Assessment Rubrics

Rubric for Laboratories: Assignment (25%)

Description: You will have to submit a programming assignment in Python, relative to the lecture topic of the week. This assignment is an individual assessment.

Assessment: 

  • Understanding of the problem and solution targeted (40% - LO 1,3,4,5). A good understanding means that all different subcases of the problem are taken into account and planned for in the solution. A medium understanding means that most subcases of the problem are taken into account and planned for in the solution. A poor understanding means that many subcases of the problem are not taken into account nor planned for in the solution.
  • Validity of the implementation (40% - LO 2). A valid implementation must run without errors for valid inputs, and return the proper solution all the time. 
  • Clarity of the code produced (20% - LO 2). The code must be well organized and commented.

You will have to analyze given problems, propose and analyze a solution, implement it and test it. It is important that the solution is properly explained and justified, and that the code is clear and tested. 

Rubric for Mid-semester Quiz: Midterm exam (25%)

Description: midterm exam. This exam is closed book, on-paper, and will consist of various parts (from simple knowledge questions to more complex problem-solving exercises).

Assessment: valid answers are required for simple knowledge questions, while comprehension of the problem and quality of the solution will be more important for problem-solving questions - LO 1,3,4,5

Rubric for Examination: Final exam (50%)

Description: final exam. This exam is closed book, on-paper, and will consist of various parts (from simple knowledge questions to more complex problem-solving exercises).

Assessment: valid answers are required for simple knowledge questions, while comprehension of the problem and quality of the solution will be more important for problem-solving questions - LO 1,3,4,5