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!