Syllabus from January 2005

4 Credits

Syllabus

Elementary Algorithmics, Problem and Instances, The Efficiency of algorithms, Average and worst case analyses, Some Examples, asymptotic notation , analysis of algorithms, Greedy algorithms, general characteristics of greedy algorithms, Graphs: Minimum spanning trees, Kruskal’s algorithms, Prim’s algorithms, Graphs: Shortest paths, The knapsack problem, Scheduling, Minimizing time in the system, Scheduling with deadlines, Divide and Conquer, Dynamic programming, Exploring graphs, Graphs and Games, Traversing trees, Depth-first search: Undirected graphs, Articulation points, Depth-first search: Directed graphs, Acyclic graphs: Topological sorting, Breadth-first search, Backtracking, The knapsack problem, Computational Complexity, Information-theoretic argument, Adversary argument, Linear reductions, Introduction to NP-completeness.