|
|
CSC 206 - Analysis of Algorithms and Complexity Theory
Periodically
Asymptotics, recurrence relations, lower bound theory including comparison trees
for sorting and searching. Oracles. Lower bounds on parallel computation. Combinatorial
optimization. Branch and bound: Knapsack problem, FFT and applications. Integer
and polynomial arithmetic. Analysis of divide and conquer algorithms, dynamic
programming, greedy algorithms, backtracking. Nondeterministic algorithms. The
classes P and NP. NP completeness. Complexity hierarchy.
Prerequisites & Notes
CSC 161.
Credits: 3 s.h.
Add to Personal Catalog (opens a new window)
|
|