CS 502 Algorithms II
|
Minimum spanning trees: algorithms of Kruskal and Prim. Single-source shortest paths: Dijkstra's and Bellman-Ford algorithms, shortest paths in directed acyclic graphs. All-pairs shortest paths: Floyd-Warshall and Johnson's algorithms. Parallel algorithms: pointer jumping, CRCW versus EREW, Brent's theorem, prefix computation. Polynomials and the FFT. String matching: Rabin-Karp algorithm, string matching with finite automata, Knuth-Morris-Pratt and Boyer-Moore algorithms. Elementary computational geometry algorithms. Approximation algorithms: vertex-cover, traveling salesman and subset-sum problems.
Credit units: 3 ECTS Credit units: 5.
|
|
|
Bilkent University Main Page
Last regenerated automatically on November 8, 2024 by OAC - Online Academic Catalog Software
|
|