Algorithms and Theory of Computation

This course is opened by School of Mathematical and Physical Science and it is the core course of PhD students in Nanyang Technological University. The course is taught by English.

Although it is an audited course for me, I followed the lecture in the whole semester and finished the assignments.

Syllabus

Algorithm Design

• graph algorithm
• greedy algorithm
• divide and conquer
• dynamic programming
• linear programming
• network flow

Automata Theory

• regular language
• finite state machine

Computability Theory

• Turing machines
• undecidability
• P and NP
• NP-completeness

Assignment

Homework 1: question & solution

Homework 2: question & solution

Homework 3: question & solution

Homework 4: question & solution