COMP 3803: INTRODUCTION TO THE THEORY OF COMPUTATION

Instructor:  Professor John OOMMEN
Office:  School of Computer Science, Carleton University, Ottawa, Canada K1S 5B6 Room 5372,  Herzberg Physics Building.
Phone: (613) 520-4358, Fax: (613) 520-4334.

Class Hours: Monday/Wednesday: 08:35 Hours to 09:55 Hours. There will be no class on Monday January 5, 2015.

Office Hours:  Monday/Wednesday 11:30 Hours - 12:30 Hours.                    

News Items:  I will constantly post news items for the course at COMP3803News2015.htm.                    

E-mail: oommen@scs.carleton.ca, WWW:http://www.scs.carleton.ca/~oommen

Term: Winter 2015.
Venue: Tory Building; Room: 240.
Important Note: This course replaces COMP2805 and precludes additional credit. If a student has completed COMP2805, s/he cannot get additional credit for COMP3803.
Course TA(s):  
Name
 E-mail Address Office Hours
Tommy Reddad
 tommyreddad@cmail.carleton.ca
 Monday 10:00 Hours to 12:00 Hours

Place: 1175 HP
Course Objectives: A second course in the theoretical aspects of computer science.
Topics will include:
Formal languages and automata theory (regular languages, finite automata, context-free languages, pushdown automata).
Computability theory (Turing machines, Church-Turing Thesis, decidability, Halting Problem).
Course Prerequisites:  COMP 1805
Please review this course material quickly - especially  proof by induction, proof by contradiction etc.
We will go through Cantor's proof to show why real numbers are uncountable, and general graph theory - paths, cycles, connectedness etc.
Course Notes:
The course notes for the entire course are due to Prof. Maheswari and Prof. Smid from the School of Computer Science. They will be posted on the web. 
Please note that these notes could be possibly modified during the term. 
Please let me know if you find errors or typos, or if some parts of the notes "need improvement".
Besides reading the course notes, please look at some of the excellent reference textbooks.
Reference Books:
Course Evaluation:
Assignments (4 Assignments):  25%
Mid-Term Exam:  25%
Final Examination: 50%
Important Dates and Policies:
Late assignments will not be accepted.
Assignments have to be dropped off in the Assignment Box in Room 3115 Herzberg on the due date (before the lecture starts). 
Please write neatly.
In case you think that your handwriting is not that great, please submit a typed copy (although this could take a significant amount of time).
 

Please check for the last date to withdraw with full fee adjustment...

Details Regarding the Final Exam:
Venue etc.: Please check the date, time and place!
Material: Final exam includes all the material covered in the class, corresponding sections in the notes, and all the material covered in the assignments and Mid-term.
This material includes numerous theorems, proofs,definitions, and exercises. Expect to prove theorems, state definitions and to solve some straightforward problems in the Final Exam.
Marking: The final exam will be marked in a fairly strict and straighforward manner.

Some Common-Sense Information:
A wrong proof is worth 0 marks, but I will give credit for the parts that are correct.
A wrong definition is worth 0 marks.
A wrong use of a theorem is worth 0 marks.
A wrong formulation of a problem is worth 0 marks.
Missing states, or transitions, or rules, in a DFA, NFA, RE, CFG, PDAs and Turing Machines will cost a reasonable deduction of marks.

Important Notes:

Mails:
  • This is a large class. So, please minimize e-mails.  
  • If you send them, please send them only from carleton.ca accounts.  
  • I will usually respond to the non-emergency e-mails verbally in class or during my office hours.  
  • I promise that I will respond to emergency mails as promptly as possible!  
Submissions:
  • All assignments and Mid-term are compulsory. Missed/Late assignments and Mid-term exams are worth 0%.  
  • In case a student misses the Mid-term due to medical reasons (doctor's note required), her/his Mid-term marks will be the equivalent of the Final exam.  
  • In order to pass the course, you need to pass in each of the components: (a) Sum total of 4 Assignments, (b) Mid-term and (c) Finals, individually.  
  • All marked assignments and Mid-term should be retained by students as proof of completion. Sometimes assignments are marked and handed back but the mark fails to get recorded.  
  • Students are encouraged to collaborate on assignments, but at the level of discussion only. When writing down the solutions, they must do so in their own words.
  • Past experience has shown that those who do not put adequate effort into the assignments do not learn the material and have extremely high chances of failing the exams.
  • Copying of assignments is not tolerated. Such cases will be referred to the Director of School of Computer Science and the Dean of Science for proper action.  This policy will be strictly enforced.
  • The assignments will be normally marked in one week's time. They will be brought to the class for pickup. After that they will be available from my office during my Office Hours.
Accommodation of special needs students:
  • Students with disabilities requiring academic accommodations in this course are encouraged to contact a coordinator at the Paul Menton Centre for Students with Disabilities (PMC).
  • They must complete the necessary letters of accommodation.
  • After registering with the PMC, make an appointment to meet and discuss your needs with me at least two weeks prior to the Mid-term exam.
  • This is necessary in order to ensure sufficient time to make the necessary arrangements.
  • Please check the deadline for submitting completed forms to the PMC for accommodations for formally scheduled exams.