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

• Growth rate of functions: O, o, theta, other notations
• Methods of Algorithm Design: recursion, divide and conquer, backtracking, and others
• 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)
• 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