CENG 511 – Advanced Algorithms 

Semester: Fall 2015
Schedule: Monday 18:00-20:50 A-301  
                  
Instructor: Assist. Prof. Dr. Emre SERMUTLU  
Office Hours: Tuesday 13:20 – 15:30 L-222
E-mail: sermutlu@cankaya.edu.tr                                                                                
                                                                                                
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:
Attendance (%10)
Midterm      (%40) (Open book, closed notes)   November 16
Final           (%50) (Open book, closed notes)

Resources: MIT, Introduction to Algorithms, complete set of lecture notes and videos:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/