This course is no longer offered
20395 Complexity of Algorithms
Credits: 4 advanced credits in Computer Science
Prerequisites: Students must fulfill all English requirements and take bibliographic instruction in the Library.
Required: Infinitesimal Calculus I, Linear Algebra I, Discrete Mathematics,1 Data Structures and Introduction to Algorithms (or Data Structures)
Recommended: Algorithms
The course is based on Algorithms and Complexity, by H.S. Wilf (Prentice Hall, 1986).
The course discusses algorithms for solving various problems and the analysis of their complexity. One of the important questions asked when presenting an algorithm to solve a specific problem relates to time complexity. The course deals with this concept and with the development of mathematical tools to analyze it. These tools are applied in analyzing several algorithms.
Topics: Mathematical preliminaries; Recursive algorithms; Number theory algorithms; NP-completeness.
1or the previous version of Discrete Mathematics (20276), which is no longer offered.