CS 502 Algorithms II Fall 2013 Instructor: Ugur Dogrusoz Office, Hours: EA-522, Tue, Wed AM Classroom, Hours: EA-502, Tue, Fri AM

Announcements	Unless otherwise stated, we do not hold the following lecture hour: Fri 8:40-9:30 Check here at least once a week!
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. Credit units: 3 ECTS Credit units: 7.5.
Prerequisite	Prior knowledge of fundamentals of computer science and algorithms required. Permission from the instructor required for undergraduates.
Textbook	T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms", MIT Press and McGraw-Hill, 2009. Third Edition
Outline & Slides	Concepts / Slides Textbook Basics - Augmenting Data Structures Chapter 14 Fibonacci Heaps Chapter 19 Data Structures for Disjoint Sets Chapter 21 Elementery Graph Algorithms Chapter 22 Minimum Spaning Trees Chapter 23 Single-Source Shortest Paths Chapter 24 All-Pairs Shortest Paths Chapter 25 Maximum Flow Chapter 26 Multi-Threaded Algorithms Chapter 27
Grading	Component Weight Date/Due Attendance 05 - Midterm 1 25 Oct 22 Midterm 2 25 Nov 19 Midterm 3 25 Dec 17 Final 20 ??, EB ??
Remarks