CENG 511 – Advanced Algorithms 

Semester: Fall 2017
Schedule: Thursday18:00-20:50 A-302
                  
Instructor: Assist. Prof. Dr. Engin DEMÄ°R
Office: L-215
                                                                              
Description: 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.

Text Book: T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, MIT Press and McGraw-Hill, 3. Edition, 2009. 

Grading:
Seminar (%30)
Midterm (%30)
Final (%40)