## CSE 551 Fall 2015  Foundations of Algorithms

Course Description: Advanced topics in formal algorithm design and analysis, including advanced shortest-paths algorithms, amortized analysis, network flows, NP-completeness, and selected topics in computational geometry, distributed\parallel, randomized, and approximation algorithms.

Course Objectives: The goal of this course is to give you advanced fundamental knowledge in algorithms. We describe some useful algorithms and explain how they work and why they are considered good, in order to (1) help you recognize situations in which you would be better off looking in the literature or asking someone knowledgeable for a good algorithm to solve your problem instead of just coding the first idea that comes to your mind, and (2) give you enough background so that you are able to understand and navigate the literature on algorithms. In order to achieve this, you will have to work through and understand several algorithmic techniques (e.g., divide-and-conquer, dynamic programming, greedy algorithms, network flow algorithms, self-adjusting data structures, basic randomized/approximation techniques) and the mathematical background necessary for analyzing the properties of these techniques and the algorithms based on them (e.g., amortized analysis, recurrence relations, basic graph theory, NP-completeness).

Students must have already mastered the material typically covered in a junior level CS Data Structures and Algorithms class (e.g., CSE310 at ASU) and its prerequisites such as Discrete Mathematics (e.g., MAT243 at ASU). In particular, you should know how quicksort and mergesort work (and be able to write and solve recurrence relations for those), you should be able to use the "big-Oh" notation and you should have seen the algorithms of Dijkstra and Prim and have an understanding of how and why they work. We also assume you know the definitions and basic properties of heaps and binary search trees.

This is a graduate-level Computer Science course; obviously we assume you know computer programming.