| WEB PAGE: |
http://www.eecs.uottawa.ca/~lucia/courses/3104-14/
UOttawa Blackboard Learn web site is where most material is available |
| PROFESSOR: |
Lucia Moura
tel: 562-5800 ext. 6678
email: lucia@eecs.uottawa.ca |
| OFFICE HOURS: |
Office: SITE 5-027
Tuesdays 9:30-10:30 (tentative, check for changes)
Wednesdays 9:30-10:30 (tentative, check for changes)
|
| LECTURES: |
Lecture 1: Tuesday 2:30 - 4:00 VNR 3075
Lecture 2: Friday 4:00 - 5:30 VNR 3075 |
|
| TEXTBOOK: |
Introduction to Computer Theory, Daniel Cohen, Wiley, 2nd edition.
Textbook will be available at Agora bookstore
(The textbook is required)
|
COURSE
OBJECTIVES: |
- To understand the power and limitations of today's computers and computers of the future.
- To become familiar with data structures that can be used as input, and to understand the meaning of output.
- To acquire a good understanding of three main components of the theory of computers and computation: finite automata, formal languages, and Turing machines.
- To understand the fundamental concepts of decidability and computability.
|
COURSE OUTLINE:
|
- Introduction, Languages, Recursive Definitions - Chapters 1, 2, 3
- Regular Expressions - Chapter 4
- Finite Automata, Transition Graphs - Chapters 5, 6
- Kleene's Theorem, Nondeterministic Finite Automata - Chapter 7
- Finite Automata with Output, Regular Languages - Chapters 8, 9
- Nonregular Languages, Decidability - Chapters 10, 11
- Context-Free Grammars, Grammatical Format - Chapters 12, 13
- Pushdown Automata, Context-Free Grammars = Pushdown Automata - Chapters 14, 15
- Non-Context-Free Languages, Context-Free Languages - Chapters 16, 17
- Decidability, Parsing, Turing Machines - Chapters 18, 19
- Recursively Enumerable Languages - Chapter 23
|
|
| MARKING SCHEME: |
20 marks (A) 7 Assignments
30 marks (M) 2 Midterm tests
50 marks (F) Final Exam
100 marks (G) Grade
if (M+F)/80 >= 50% then G= A+M+F
else G=(M+F)*10/8
|
|
IMPORTANT
DATES&TASKS: |
| dates |
Important tasks (tentative) |
Lectures(tentative) |
| Jan 7-10
|
| Ch 1,2,3
|
| Jan 14-17
| A1 out
| Ch 4, 5
|
| Jan 21-24
| A1 due, A2 out
| Ch 6,7
|
| Jan 28-31
| A2 due, A3 out
| Ch 8,9
|
|
Feb 4-7
|
| Ch 10,11
|
Feb 11-14
| A3 due, A4 out
| Ch 12, review
|
| Feb 18-21
| study break
|
|
Feb 25-28
| Fri Feb 28 Midterm Test 1
| midterm, Ch 13
|
Mar 4
(Mar 7 no class)
| A4 due, A5 out
Time made-up For Mar 7
by midterm 2 outside class time.
| Ch 14
|
Mar 11-14
Mar 15 (Sat)
| A5 due, A6 out
Sat Mar 15 Midterm Test 2
| Ch 15/review
|
Mar 18-21
|
| Ch 16, 17
|
Mar 25-28
| A6 due, A7 out
| Ch 18,19
|
|
April 1-4
| A7 due
| Ch 23/review
|
|