Spring Term 2005 COSC 385 Theoretical Computer Science
Instructor : Bala Kalyanasundaram TA :
Office : Reiss Science Hall, Rm 232 Office :
Office hrs : MW 1-2:30 (or whenever I am Hours : free)
Phone : 687-2709 Phone :
TEXTS : 1. Introduction to the Theory of Computation,
by Michael Sipser
2. Introduction to Automata Theory, Languages and
Computation by Hopcroft, Motwani and Ullman
3. Computational Complexity by Papadimitriou
GRADING : EXAMS Midterm and a Final
(30%,30%) NO MAKE-UPs
WRITTEN There are 5 written
ASSIGNMENTS assignments (40%)
* All assignments are due before the class BEGINS on the day
they are due
* 15% penalty per day for late submission.
EMPHASIS : Understand what can and cannot be solved using computers.
Topics include finite automata, context-free languages,
Turing machines, undecidability and complexity theory.
SYLLABUS : (tentative)
January - Automata theory and Regular languages.
February - Grammars (Context free, Context sensitive)
March - Computability Theory: Turing Machine and
undecidability
April - Complexity Theory
PREPARATION: Discrete Mathematics and interests in solving puzzles!
IMPORTANT :
This is a fuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuun course.
Many written assignments will be given during the semester.
Exact deadline will be specified in the assignment sheet. For late
submission, you will lose 15% of the grade for each day after the
deadline.
Collaboration is NOT allowed. Cheating of any form will
NOT be tolerated. Any form of cheating, copying or collaboration
will be reported to the honor council. However, students are
allowed to discuss assignments among themselves as long as they
do not share solutions.
Each written assignment should be legible. I use the rule
"If I can't read and understand it then it must be wrong".
Whenever possible, please type and submit a printout.
Students are responsible for all instructions, exam
announcements and assignments given during REGULAR CLASS hours.
Tentatively, first exam is scheduled on Feb 23, 2005 (Wednesday).
They will be held during regular class hours in the scheduled meeting
place. Makeup exams will NOT be given. If you have trouble in
taking the exam you must tell the instructor well in advance - not
a week before the exam.
Feel free to ask questions in the class, and
during regular office hours of the instructor/TA. If you can not
meet during regular office hours then set an appointment.
Enjoy the material and have fun!