This course describes the techniques for the design and analysis of efficient algorithms, giving emphasis on methods useful in practice. Topics include graph algorithms; divide-and-conquer algorithms and recurrences; dynamic programming; greedy algorithms; amortized analysis; network flow; randomized and approximation algorithms.

To Know Classical Algorithms
To understand techniques for the design and analysis of efficient algorithms
To be able to analyse correctness and complexity of given algorithm
To be able to design algorithms for new problems

1. Basics of Algorithms Analysis - Computational Tractability - Asymptotic Order of Growth Notation - A Survey of Common Running Times. Graphs - Basic Definitions and Applications- Graph Connectivity and Graph Traversal – Implementation - Connectivity in Directed Graphs - Directed Acyclic Graphs and Topological Ordering - Shortest Paths in a Graph - The Minimum Spanning Tree Problem – Clustering - Huffman Codes and the Problem of Data Compression

2. Divide and Conquer - Recurrence Relations - Counting Inversions - Integer Multiplication - Convolutions and the Fast Fourier Transform Dynamic Programming - Weighted Interval Scheduling - Subset Sums and Knapsacks- Sequence Alignment

3. Network Flow - Maximum Flow Problem - Maximum Flows and Minimum Cuts in a Network - The Bipartite Matching Problem - Extensions to the Maximum Flow Problem
NP and Computational Intractability - Polynomial-time Reductions - NP-Complete Problems - Sequencing Problems - Partitioning Problems - Graph Coloring - co-NP and the Asymmetry of NP

4. Approximation Algorithms - The Center Selection Problem - The Pricing Method - Arbitrarily Good Approximations
Local Search - The Landscape of an Optimization Problem - Maximum Cut Approximation via Local Search - Best-Response Dynamics and Nash Equilibria

5. Randomized Algorithms - Contention Resolution - Random Variables and their Expectations - A Randomized Implementation of Dictionaries - Randomized Caching - Chernoff Bounds

1. Introduction to Algorithms, Thomas H. Cormen,Charles E. Leiserson, Ronald L. Rivest, Clifford Stein The MIT Press; (2nd Ed),2001
2. Algorithm Design: Jon Kleinberg and Eva Tardos, AW (2005)
3. Anany V. Levitin. Introduction to the Design & Analysis of Algorithms (2nd Ed): A W (2006)
4. The Algorithm Design Manual(2nd Ed): Steven S. Skiena, Springer(2008)
5. Computer Algorithms: Introduction to Design and Analysis (3rd Ed): Sara Baase and Allen Van Gelder. AW (1999)
6. Fundamentals of Computer Algorithms: Ellis Horowitz, Sartaj Sahni and Rajasekaran Sanguthevar Galgotia (2008)