COURSE OUTLINE: MH4302

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

Course Aims

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.

Intended Learning Outcomes

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

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

Course Content

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.

Assessment

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, b
2. a
3. a, b
5. a
15 team See Appendix for rubric
Mid-semester Quiz
CA1 1, 2, 3, 4, 5, 6 1. a, b, c
2. 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, c
2. 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

Formative Feedback

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.

Learning and Teaching Approach

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.

Reading and References

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

Course Policies and Student Responsibilities

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

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
Ng Keng Meng (Assoc Prof) MAS-05-09 6513 8656 kmng@ntu.edu.sg

Planned Weekly Schedule

Week Topic Course ILO Readings/ Activities
1

Automata Theory

1, 2, 3, 4, 5, 6, 7, 8

Lewis and Papadimitriou – Chapters 1-3
Hopcroft, Motwani and Ullman – Chapters 1-7

2

Automata Theory

1, 2, 3, 4, 5, 6, 7, 8

Lewis and Papadimitriou – Chapters 1-3
Hopcroft, Motwani and Ullman – Chapters 1-7

3

Automata Theory

1, 2, 3, 4, 5, 6, 7, 8

Lewis and Papadimitriou – Chapters 1-3
Hopcroft, Motwani and Ullman – Chapters 1-7

4

Automata Theory

1, 2, 3, 4, 5, 6, 7, 8

Lewis and Papadimitriou – Chapters 1-3
Hopcroft, Motwani and Ullman – Chapters 1-7

5

Automata Theory

1, 2, 3, 4, 5, 6, 7, 8

Lewis and Papadimitriou – Chapters 1-3
Hopcroft, Motwani and Ullman – Chapters 1-7

6

Computability

9, 10, 11, 12

Lewis and Papadimitriou – Chapters 4-5
Hopcroft, Motwani and Ullman – Chapters 8-9

7

Computability

9, 10, 11, 12

Lewis and Papadimitriou – Chapters 4-5
Hopcroft, Motwani and Ullman – Chapters 8-9

8

Computability

9, 10, 11, 12

Lewis and Papadimitriou – Chapters 4-5
Hopcroft, Motwani and Ullman – Chapters 8-9

9

Complexity

13, 14, 15, 16, 17

Lewis and Papadimitriou – Chapters 6-7
Hopcroft, Motwani and Ullman – Chapters 10, 11.1

10

Complexity

13, 14, 15, 16, 17

Lewis and Papadimitriou – Chapters 6-7
Hopcroft, Motwani and Ullman – Chapters 10, 11.1

11

Complexity

13, 14, 15, 16, 17

Lewis and Papadimitriou – Chapters 6-7
Hopcroft, Motwani and Ullman – Chapters 10, 11.1

12

Complexity

13, 14, 15, 16, 17

Lewis and Papadimitriou – Chapters 6-7
Hopcroft, Motwani and Ullman – Chapters 10, 11.1

13

Complexity

13, 14, 15, 16, 17

Lewis and Papadimitriou – Chapters 6-7
Hopcroft, Motwani and Ullman – Chapters 10, 11.1

Appendix 1: Assessment Rubrics

Rubric for Tutorials: Project (15%)

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.

Please Note: In principle, students in the same group share the same group marks. However, there can be some individual variation within a group, depending on the evaluation of the tutor and the feedback from the peers. Students may be awarded more marks for showing exemplary contribution to other team members’ learning that goes beyond what is required, whereas students who have not contributed sufficiently may receive lower marks than the rest of the team members.

Rubric for Mid-semester Quiz: CA1 (25%)

Point-based marking 

Rubric for Examination: FInal examination (60%)

Point-based marking