|
Instructor: Shai Simonson
The design of algorithms is studied, according to methodology and application. Methodologies
include: divide and conquer, dynamic programming, and greedy
strategies. Applications involve: sorting, ordering and
searching, graph algorithms, geometric algorithms, mathematical
(number theory, algebra and linear algebra) algorithms, and string
matching algorithms. Analysis of algorithms is studied - worst case, average case, and amortized -
with an emphasis on the close connection between the time complexity
of an algorithm and the underlying data structures.
NP-Completeness theory is examined along with methods of coping with intractability, such as approximation and probabilistic algorithms.
Text:
Introduction to Algorithms, Cormen, Rivest, Leiserson.
Reference:
Computers and Intractability, Garey and Johnson
Requirements: Two exams, six problem sets.
|