Theory of Computer Science

2014/2015

SEMESTER 1

THEORY OF COMPUTER SCIENCE

Lecturer	:	PM Dr Siti Zaiton Mohd Hashim
Room No.	:	Academic Office, Level 3, N28a
Telephone No.	:	0197726248
E-mail	:	sitizaiton@utm.my
Synopsis	:	This course introduces students to formal languages and automata theory. It will emphasize on grammar, language and abstract machine such as Regular Grammar, Context Free Grammar, Finite Automata, Push Down Automata, and Turing Machine. The course will also provide practice on the acceptability of data by these machines. At the end of the course, students should be able to apply the theory in constructing this abstract machine and testing them with the right data.
Learning Outcome	:	At the end of the course, students should be able to : Describe the theory of Computer Science. Apply and explain the theory in solving the given problems. Discuss and make decision to solve problems related to computer science theory. Work collaboratively in a team to solve problems using current information related to computer science theory
Student Learning Time	:
Reminder	:	ATTENDANCE is compulsory. Students with less than 80% attendance will be prohibited from sitting the final exam. Students MUST DRESS respectably (SOPAN in malay) when attending the lecture, please follow the dress code required. Students must abide by the rules set by University at all times in the lectures, laboratories and exams. CHEATING in any form is PROHIBITED. Gred F is automatically given if the student is caught cheating during the exam. Zero mark is given if the student is found copying/plagiarizing other’s work. Quizzes and EXAMs ARE NOT REDONE unless the student is sick and certified by UTM Medical panels, to be done within a week after the exam. LATE assignment will be penalized or rejected.
TEACHING METHODOLOGY	:	Lecture and Discussion, Co-operative Learning, Independent Study
Please Download Course Outline HERE Week Topics Activities/hours  – SEM I  – Week 1 (8/9/2014) 1.0 Mathematical preliminaries 1.1 Greek Symbols Lecture 1 Tutorial 1 Assessment: Tutorial 1 Week 2-3  (15 & 22/9/2014) 2.0 Languages 2.1  Language and String 2.2  Finite specification of language 2.3  Regular set and expressions Lecture : 4 Tutorial: 2 Assessment: Tutorial 2, Tutorial 3, Quiz 1 Weeks 4-6 (29/9 & 13/10/2014)             3.0 Context Free Grammars 3.1  Grammars and languages 3.2  Derivation Trees 3.3  Regular Grammars Lecture : 4 Tutorial: 2 Assessment: Quiz 2, Tutorial 4, Tutorial 5, Assignment 1 Week 7 (19/10/2014) SEMESTER BREAK Weeks 8-10 (27 & 3/10/2014 & 10/11/2014)               4.0 Finite Automata 4.1  Deterministic Finite Automata (DFA) 4.2  State Diagram 4.3  Non Deterministic Finite Automata (NFA) 4.4  Finite automata and Regular Set 4.5  Regular grammars and automata Lecture : 4 Tutorial: 2 Assessment: Tutorial 6, Tutorial 7, Quiz 3, Assignment 2, Test (10 November 2014, 2.30pm, BK1-BK6, N28) Week 11-12(17 & 24/11/2014) 5.0 Push Down Automata (PDA) 5.1  Push Down Automata 5.2  Context Free Language (CFL) Lecture : 4 Tutorial: 2 Assessment: Quiz 4, Tutorial 8, Tutorial 9Group Assignment*New Week 13-14(1 & 8/12/2014) 6.0     Turing Machine 6.1     Standard Turing Machine 6.2     Turing machine as language acceptorVideo turing machine Lecture : 4 Tutorial: 2 Assessment: Tutorial 10,Tutorial 11 Week 15(15/12/2014) 7.0     Chomsky Hierarchy 7.1   Grammars 7.2   Language levels 0, 1, 2, 3  Lecture : 1 Tutorial: 1 Assessment: Quiz 5,Tutorial 12 Week 16(21/12/2014) 8.0   Revision (Summary) New**(18 Dis 2014) CLUE EXAM  New**(21 Dis 2014) Book Answer Completed  New**(30 Dis 2014) VIDEO ON (30 Dis 2014) Finite Deterministic Automata Non Finite Deterministic  Automata Finite  Automata Pushdown Automata Turing Machine  –

REFERENCES       :

1. Thomas Sudkamp, Language and machine, Pearson Int. Edition, Third Edition, 2006.
2. John C. Martin, Introduction to Languages and the Theory of Computation, Fourth Edition, 2011.
3. Michael Sipser, Introduction to the Theory of Computation, Cengage Learning, Third Edition, 2013.
4. Elaine Rich. Automata, Computability and Complexity. Pearson International Edition. Pearson Prentice Hall. 2009.

GRADING