Spring Term 2009          COSC 330 Algorithms


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


  TEXT :      Introduction to Algorithms (second edition)
	      by Cormen, Leiserson, Rivest and Stein


  GRADING :    EXAMS                 One Midterm and a Final 
                                     (25%, 40%)      NO MAKE-UPs

	                             Many programming/written assignments. 
	       ASSIGNMENTS           Will be determined later.
                                     (35%)

           * 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.
              Topics covered are data structures,
              algorithm analysis (worst-case, average-case), 
	      divide and conquer approach, greedy approach, dynamic programming,
	      graph algorithms, shortest path problem, max-flow problem,
	      matching problem, FFT, data compression, cryptography,
              problems in computational geometry and NP-completeness.
              We will also cover some basic algorithmically 
              unsolvable problems.  All subject to time constraints!!! 

  SYLLABUS :  (tentative)
              January   -  Algorithm analysis, quick review of sorting and 
                           searching.  Order statistics, Recursion, Divide and 
                           Conquer Techniques.  Chapters 1,2,3,4,6,7,8 and 9.

              February  -  Dynamic Programming, Greedy Algorithms and Amortized 
                           Analysis.  Chapters 15, 16 and 17.

              March     -  Graph Algorithms (Searching, Shortest Path, Max-flow
                           Matching) Chapters 22, 23, 24 and 26.

              April     -  NP-Completeness, Unsolvability Misc. Problems, 
		           Approximation and Online Algorithms.  
                           Chapters 30, 32, 33, 34 and 35

  IMPORTANT :
           Students are responsible for all instructions, exam announcements 
           and assignments given during REGULAR CLASS hours.  Collaboration 
           and/or copying solution (partial or full) among students or 
           from any external source is not allowed.  Please see GU policy on
           cheating in the course work.