Spring Term 2021          COSC 545 Theory of Computations


  Instructor : Professor Bala Kalyanasundaram    TA     :  
  Office     : St. Marys, Rm 329                 Office : 
  Office hrs : Tue & Thur                        Hours  :  
               2:00 - 3:30 p.m. (or whenever I am free)
  Phone      : 687-2709                          Phone  :


  TEXT :      Materials from the Following:

          Michael Sipser, Introduction to Theory of Computation. 


  GRADING :    EXAMS                 One or Two  Midterms and a Final 
                                     (approx. 60%)      NO MAKE-UPs

	                             Many programming/written assignments. 
	       ASSIGNMENTS           Will be determined later.
                                     (approx. 40% depends on number of midterms)

           * Assignments are due before the class BEGINS on the day 
             they are due

	   * NO late submission.


  EMPHASIS :  Topics covered include finite state machines, context-free 
              grammars, context-sensitive grammar, Turing machines,
              computability theory, P, NP, NP-Completeness, BPP,
              polynomial time hierarchy, L, NL, PSPACE, and beyond.

  SYLLABUS :  (tentative)
              January      -   Automata theory
                          
              February     -   DFA, NFA, Context-free Language, Turing machine, Church Thesis.

              March        -   Computatbility Theory

              April        -   Recursion Theorem, P, NP, NP-Completeness 

              May          -   Complexity Theory.

  IMPORTANT :
           Students are responsible for all instructions, exam announcements 
           and assignments given during REGULAR CLASS hours. For assignments, you are allowed to
           collaborate, and read materials from any source.  However, you MUST understand the solution
           and MUST write the solution in your own words.  No sharing of your writeup for the assignments. 
           Please see GU policy on cheating in the course work.