Bilkent University Logo

Bilkent University

Online Academic Catalog

Undergraduate and Graduate Programs 2023-2024


CS 474 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, Prerequisite: CS 473.

Spring Semester (Cevdet Aykanat)

Bilkent University Main Page

Last regenerated automatically on March 28, 2024 by OAC - Online Academic Catalog Software