Design&Analysis of Algorithms

Catalog description

This course provides a comprehensive coverage of modern computer algorithms, aiming at in-depth treatment of algorithmic design and analysis with elementary explanation while keeping mathematical rigor. Based on the textbook “Introduction to Algorithms”, this class covers the topics listed below in sequence. • Foundations. • Data Structures ‒ hash tables, binary search trees, red-black trees, B-trees. • Design and Analysis Techniques ‒ dynamic programming, greedy algorithms. • Graph Algorithms ‒ elementary graph algorithms, algorithms for shortest paths, maximum flows, minimum spanning trees. • Selected Topics ‒ NP-completeness, approximation algorithms, multithreaded algorithms. Each covered topic starts with the description of pertinent algorithms often in the pseudocode(s), followed by their careful complexity analyses.