Fall Term 2021          COSC 540 Algorithms


  Instructor : Professor Bala Kalyanasundaram    TA     :  
  Office     : St. Marys, Rm 329                 Office : 
  Office hrs : Mon & wed                         Hours  :  
                   p.m. (or whenever I am free)
  Phone      : 687-2709                          Phone  :


  TEXT :      Materials from the Following:

              Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein
              Algorithms by Dasgupta, Papadimitriou and Vazirani
              Algorithm Design by Kleinberg and Tardos
	      Approximation Algorithms by Vazirani


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

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

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

	   * NO late submission.


  EMPHASIS :  To learn how to design and analyze algorithms.
              Builds on basic design and analysis techniques taught in 
              undergraduate Algorithms class.  Approximation,
              parallel, online, randomization and quantum algorithms will be taught.
              Understand P and NP.

  SYLLABUS :  (tentative)

              Sequential Algorithm
               -  Revisit algorithmic techniques:  
                  Divide and Conquer Technique:  General technique, FFT, 
                       Van Emde Boas Data structure and so on.
                  Dynamic Programming:  General technique, HMM and so on. 
                  Greedy Algorithms: MST, Shortest Path and so on. 
                  Graph Algorithms:  Search, Flow, Matching
              Algorithmic problems 
               -  Geometry, Number Theory, Strings etc.
              Approximation Algorithms 
              Parallel Algorithms 
              Online Algorithms
              Randomized Algorithms
              Quantum Algorithms
              Intractable Problems

  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.