Algorithms and Complexity

Semester:
4th
Course Type:
Compulsory courses (YM)
Track:
-
Code:
Κ17
ECTS:
8
TEACHING HOURS per week
Theory:
4
Seminar:
2
Laboratory:
0
Specializations
Foundations of Computer Science (S1):
-
Data and Knowledge Management (S2):
-
Software (S3):
-
Hardware and Architecture (S4):
-
Communications and Networking (S5):
-
Signal and Information Processing (S6):
-
Related Courses
Course Content

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.

LITERATURE AND STUDY MATERIALS - READING LIST

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