The course introduces the concepts of algorithm design and analysis and presents the basic mathematical tools used to evaluate its performance. It describes the union and find technique and presents the fundamental techniques of search in graphs, BFS and DFS. The course focuses on the three basic methods of algorithm design, "divide and conquer", greedy algorithms and dynamic programming. It analyzes the characteristics of each method and highlights the practical problems that are effectively solved by each method. It defines the decision problems and the classes P and NP. It describes the concept of the reduction and identifies NP-complete and NP-hard problems.
1. Th. H. Cormen, CH. E. Leiserson, R. L. Rivest and C. Stein, Introduction to algorithms, MIT-Press, 2009, 3rd edition, MIT Press, http://mitpress.mit.edu/algorithms/ (Eudoxus).
2. Jon Kleinberg & Eva Tardos, Algorithm Design, Addison – Wesley, 2006 (Eudoxus).
3. S. Dasgupta, C. H. Papadimitriou & U. V. Vazirani, Algorithms, McGraw-Hill, 2008 (Eudoxus)
• Other material:
- notes, Algorithms and Complexity, 2016,
https://eclass.uoa.gr/modules/document/index.php?course=D469&openDir=/4c2b32c4z3e6
- slides,
https://eclass.uoa.gr/modules/document/index.php?course=D469&openDir=/4c2b32c4rt6n