Course info

This course will consist of a short review of some preliminary material, including asymptotic s, summations, and recurrences and sorting. There will be discussions on approaches to designing optimization algorithms, including dynamic programming and greedy algorithms. There will be focus on graph algorithms, minimum spanning trees, shortest paths, and network flows. We will discuss algorithmic problems arising from geometric settings, that is, computational geometry. Finally, we will discuss methods to approximate NP-hard problems, and how to prove how close these approximations are to the optimal solutions. At the end we will: Present a clear, simple and unambiguous description of the algorithm (in pseudo-code, for example): Present a justification or proof of the algorithm’s correctness: Present a worst-case analysis of the algorithm’s efficiency, typically it running time (but also its space, if space is an issue).