Jun 25, 2024  
2020-2021 Graduate Studies Bulletin 
    
2020-2021 Graduate Studies Bulletin [ARCHIVED BULLETIN]

Add to Personal Catalog (opens a new window)

CSC 206 - Analysis of Algorithms and Complexity Theory


Semester Hours: 3
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.

Prerequisite(s)/Course Notes:
CSC 204 . Course open to graduate students in computer science, others need permission from computer science graduate director.





Add to Personal Catalog (opens a new window)