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

Autumn Semester (Mehmet Koyut├╝rk)

  | Bilkent University Main Page |

  Last regenerated automatically on September 22, 2017 by OAC - Online Academic Catalog Software.