|
||||
| Description: | ||||
| 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. | ||||
|