Bilkent University Logo

Bilkent University

Online Academic Catalog

Undergraduate and Graduate Programs 2018-2019


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 May 23, 2019 by OAC - Online Academic Catalog Software