CS 4245 Analysis of Algorithms (4) 					2005

Catalog Description
     Design, analysis and implementation of algorithms. Methods of algorithm
     design, including recursion, divide and conquer, dynamic programming,
     backtracking. Time and space complexity analyses in the best, worst, 
     average cases. NP-completeness; computationally hard problems. 
     Applications from several areas of Computer Science. 
     Prerequisites: MATH 2101, MATH 2304, CS 3240
     CROSS-LISTED: MATH 4245

Course Outline
  I.  Growth rate of functions: O, o, theta, other notations

 II.  Methods of Algorithm Design: recursion, divide and conquer, backtracking,
      and others

III.  Applications to algorithms
      Sorting and searching (e.g., quicksort, mergesort, heapsort)
      Set and Graph Theoretic (e.g.,depth-/breadth-first search, min. spanning tree,
		shortest paths)
      String Matching (e.g., KMP, Boyer-Moore)
      Polynomial and Matrix (e.g., Strassen's method)

 IV.  Introduction to complexity: brief overview of P and NP

Recommended Text:
  Baase & Van Gelder, Computer algorithms, Addison-Wesley
  Levitin, Anany, Intro to the Design and Analysis of Algorithms,
	Addison Wesley