WEB PAGE: 
http://www.eecs.uottawa.ca/~lucia/courses/310414/
UOttawa Blackboard Learn web site is where most material is available 
PROFESSOR: 
Lucia Moura
tel: 5625800 ext. 6678
email: lucia@eecs.uottawa.ca 
OFFICE HOURS: 
Office: SITE 5027
Tuesdays 9:3010:30 (tentative, check for changes)
Wednesdays 9:3010: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
 ContextFree Grammars, Grammatical Format  Chapters 12, 13
 Pushdown Automata, ContextFree Grammars = Pushdown Automata  Chapters 14, 15
 NonContextFree Languages, ContextFree 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 710

 Ch 1,2,3

Jan 1417
 A1 out
 Ch 4, 5

Jan 2124
 A1 due, A2 out
 Ch 6,7

Jan 2831
 A2 due, A3 out
 Ch 8,9

Feb 47

 Ch 10,11

Feb 1114
 A3 due, A4 out
 Ch 12, review

Feb 1821
 study break

Feb 2528
 Fri Feb 28 Midterm Test 1
 midterm, Ch 13

Mar 4
(Mar 7 no class)
 A4 due, A5 out
Time madeup For Mar 7 by midterm 2 outside class time.
 Ch 14

Mar 1114
Mar 15 (Sat)
 A5 due, A6 out
Sat Mar 15 Midterm Test 2
 Ch 15/review

Mar 1821

 Ch 16, 17

Mar 2528
 A6 due, A7 out
 Ch 18,19

April 14
 A7 due
 Ch 23/review

