CS 502 Algorithms II

Minimum spanning trees: algorithms of Kruskal and Prim. Singlesource shortest paths: Dijkstra's and BellmanFord algorithms, shortest paths in directed acyclic graphs. Allpairs shortest paths: FloydWarshall and Johnson's algorithms. Parallel algorithms: pointer jumping, CRCW versus EREW, Brent's theorem, prefix computation. Polynomials and the FFT. String matching: RabinKarp algorithm, string matching with finite automata, KnuthMorrisPratt and BoyerMoore algorithms. Elementary computational geometry algorithms. Approximation algorithms: vertexcover, traveling salesman and subsetsum problems.
Credit units: 3 ECTS Credit units: 5.



Bilkent University Main Page
Last regenerated automatically on August 11, 2022 by OAC  Online Academic Catalog Software

