Course Title | ## Theory of Computing | ||

Course Code | ## MH4302 | ||

Offered | Study Year 4, Semester 1 | ||

Course Coordinator | Ng Keng Meng (Assoc Prof) | kmng@ntu.edu.sg | 6513 8656 |

Pre-requisites | MH1300 and MH1301 and (MH1402 or MH1403 or CZ2001) | ||

AU | 4 | ||

Contact hours | Lectures: 39, Tutorials: 13 | ||

Approved for delivery from | AY 2021/22 semester 1 | ||

Last revised | 5 Feb 2020, 10:40 |

This course aims to provide you with a basic understanding of fundamental theoretical concepts in computability and complexity and achieve a rigorous understanding of basic automata theory. You will learn the rigorous way to approach mathematical problems in these topics and to be familiar with the process of solving abstract problems related to computability, complexity and automatic theory. Through this course, you will have opportunity to sharpen your critical analytical skills in an interdisciplinary realm of computer science and mathematics, and improve your communication skills necessary to deliver technical ideas to a broad audience. As a result of this course, you will develop the necessary skills to become ready for career in computer science or mathematically related fields.

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

- Distinguish between different models of computation.
- Apply the definitions of formal languages and grammars.
- Explain the workings of a finite automata.
- Derive the relationship between finite automaton and regular expressions.
- Employ the use of the pumping lemma to tell which expressions are regular.
- Explain the workings of a pushdown automata.
- Derive the relationship between a pushdown automata and context free languages.
- Apply the pumping lemma for context free languages.
- Describe the formal model of a Turing machine.
- Distinguish between the different variations of a Turing machine.
- Perform the diagonalization argument on different problems.
- Differentiate between computable and noncomputable problems.
- State the difference between a deterministic and a nondeterministic Turing machine.
- Judge which problems are in P and which are in NP.
- List the examples of classes that are NP-complete.
- Apply Cook’s Theorem to determine if a given problem is NP-complete.
- Derive the ingredients of the complementation theorem for NP problems.

Introduction to models of computation and finitary representations.

Formal languages and Chomsky's grammars.

Finite automata, regular expressions, regular grammars, and their equivalence.

Properties of regular languages: pumping lemma for regular languages and its applications.

Pushdown automata, context free languages and context free grammars.

Properties of context free languages: pumping lemma for context free languages.

Turing machines: definition and construction for simple problems.

Church-Turing thesis and computability.

Uncountable numbers and the diagonalization argument.

Examples of non-computable problems and applications.

Computably enumerable sets and Post’s problem.

Nondeterministic Turing machines and the classes P and NP.

Polynomial-time reductions and Cook’s Theorem.

Satisfiability and other NP-complete problems.

Co-NP space.

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

Continuous Assessment | |||||

Tutorials | |||||

Project | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 | 1. a, b2. a3. a, b5. a | 15 | team | See Appendix for rubric |

Mid-semester Quiz | |||||

CA1 | 1, 2, 3, 4, 5, 6 | 1. a, b, c2. a | 25 | individual | See Appendix for rubric |

Examination (2 hours) | |||||

FInal examination | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17 | 1. a, b, c2. a, c | 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

b. Work in teams on complicated projects that require applications of mathematics, and communicate the results verbally and in written form

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

For the midterm and final exams, feedback on the common mistakes are given on NTULearn after the grades are announced. Common mistakes are often repeated and addressing this will be important for achieving the learning outcomes. For the projects, tutors will discuss and answer any questions about mistakes, and give feedback.

Lectures (39 hours) | Present the key ideas behind mathematical concepts. Present important steps used to solve different types of problems. |

Tutorials (13 hours) | Develop proficiency in problem solving skills. Reinforce concepts already covered in the lectures. Give an opportunity for weaker or more reserved students to clarify doubts. Group Project: Train the class on teamwork and cohesion, as well as to boost confidence for weaker students. Develop communications skills. Students will be able to learn the importance of teamwork. |

1. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to automata theory, languages, and computation (3rd Edition). Addison-Wesley. ISBN-13:978-0321455369

2. Harry Lewis, Christos H. Papadimitriou - Elements of the Theory of Computation (2nd Edition). Prentice Hall. ISBN-13: 978-0132624787

(1) General

You are expected to complete all assigned pre-class readings and activities, attend all tutorial classes punctually and take all scheduled assignments and tests by due dates. You are expected to participate in all tutorial discussions and activities.

(2) Absenteeism

Absence from the midterm without a valid reason will affect your overall course grade. Valid reasons include falling sick supported by a medical certificate and participation in NTU’s approved activities supported by an excuse letter from the relevant bodies. There will be no make-up opportunities for CA components.

All project assignments must be submitted on time. Failure to do so will affect your score.

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

Ng Keng Meng (Assoc Prof) | MAS-05-09 | 6513 8656 | kmng@ntu.edu.sg |

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

1 | Automata Theory | 1, 2, 3, 4, 5, 6, 7, 8 | Lewis and Papadimitriou – Chapters 1-3 |

2 | Automata Theory | 1, 2, 3, 4, 5, 6, 7, 8 | Lewis and Papadimitriou – Chapters 1-3 |

3 | Automata Theory | 1, 2, 3, 4, 5, 6, 7, 8 | Lewis and Papadimitriou – Chapters 1-3 |

4 | Automata Theory | 1, 2, 3, 4, 5, 6, 7, 8 | Lewis and Papadimitriou – Chapters 1-3 |

5 | Automata Theory | 1, 2, 3, 4, 5, 6, 7, 8 | Lewis and Papadimitriou – Chapters 1-3 |

6 | Computability | 9, 10, 11, 12 | Lewis and Papadimitriou – Chapters 4-5 |

7 | Computability | 9, 10, 11, 12 | Lewis and Papadimitriou – Chapters 4-5 |

8 | Computability | 9, 10, 11, 12 | Lewis and Papadimitriou – Chapters 4-5 |

9 | Complexity | 13, 14, 15, 16, 17 | Lewis and Papadimitriou – Chapters 6-7 |

10 | Complexity | 13, 14, 15, 16, 17 | Lewis and Papadimitriou – Chapters 6-7 |

11 | Complexity | 13, 14, 15, 16, 17 | Lewis and Papadimitriou – Chapters 6-7 |

12 | Complexity | 13, 14, 15, 16, 17 | Lewis and Papadimitriou – Chapters 6-7 |

13 | Complexity | 13, 14, 15, 16, 17 | Lewis and Papadimitriou – Chapters 6-7 |

Grading Criteria | Exceptional | Effective | Acceptable | Developing |

Accuracy | The interpretation is highly accurate, concise and precise. | The interpretation is mostly accurate. Some parts can be better explained or more succinct. | The interpretation is somewhat accurate. However, it contains some inaccuracies, missing points or ideas that are not related to the interpretation. | The interpretation are mostly inaccurate. |

Thoroughness | The literature review was comprehensive and rigorous. It includes several different perspectives, including a good spread of the first and latest ideas on the topic. | The literature review was mostly comprehensive and rigorous. It can improve in terms of the selection of the works relating to the topic. | The literature review was adequate. It covers some of the major works relating to the topic. References to primary source is largely missing. | The literature review was not thorough. It is based on a single source of information and/or inaccurate or unreliable secondary sources. |

Presentation | Very clear and organized. It is easy to follow your train of thought | Mostly clear and organized. Some parts can have better transitions. | Somewhat clear. It requires some careful reading to understand what you are writing. | Mostly unclear and messy. It is difficult to understand what you are writing as there is no clear flow of ideas. |

Originality | Evidence of extensive synthesis of ideas from different perspectives such that there is a very convincing original interpretation and that goes beyond what is already discussed in literature. | Evidence of some synthesis of ideas which lead to an original interpretation. The interpretation is good original summary of what is discussed in literature. | Evidence of an attempt to synthesise ideas. However, the attempt contains some misunderstandings. | No synthesis of ideas or originality. It is a repetition of what people have said or a laundry list of ideas with little interpretation. |