Algorithms and Complexity
Professors George Vouros
Panagiotis Rouvelas
Course category Core
Course ID DS-101
Credits 5
Lecture hours 3 hours
Lab hours 2 hours
Digital resources View on Aristarchus (Open e-Class)

Learning Outcomes

Upon successful completion of this course, students should be able:

  • to explain and deal with fundamental concepts regarding algorithms and complexity, such as “problem” and “problem class”, algorithm, instance, computational resources and resource requirements as a function of instance’s size, asymptotic behavior, symbols for asymptotic behavior, recursive functions and methods for their resolution.
  • to analyse, select and evaluate algorithms based on the concepts and methods mentioned above.
  • to design computationally effective algorithms based on the above concepts and algorithms’ design techniques (divide and conquer, greedy, dynamic programming).
  • to communicate algorithmic ideas in a concise and formal way.

Towards constructing and evaluating computational programs and advancing their computational effectiveness.

Course Contents

  • Asymptotic notation
  • Examples of algorithms and their analysis in priority queues and heaps
  • Sorting in linear time: Union-Find
  • Divide and Conquer: examples of algorithms and their analysis (mergesort, multiplication of numbers and matrices, nearest points), master theorem and proof.
  • More on divide and conquer: quicksort and probabilistic quicksort as an example of non-deterministic algorithms and of their analysis
  • Selection algorithms and analysis
  • Greedy Algorithms, proofs fs soundness
  • Dynamic programming and examples (including graph problems)

Recommended Readings

  • Τ. Cormen, C.Leiserson, R.Rivest, C.Stein (2009): Introduction to Algorithms, The MIT Press
  • Papadimitriou C. H. & Steiglitz K. (1982): Combinatorial optimization: algorithms and complexity, Prentice Hall.
  • Knuth D. (1997): Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison-Wesley,
  • Kleinberg J. &Tardos E. (2006): Algorithm Design, (Pearson International Edition), Addison Wesley,
  • Anany V. Levitin (2007): Introduction to the Design & Analysis of Algorithms, (Pearson International Edition), Addison Wesley.

Associated scientific Journals

  • Journal of Complexity, Elsevier, ISSN: 0885-064X
  • Algorithmica, Springer, ISSN: 0178-4617 (Print) 1432-0541 (Online)
  • Theoretical Computer Science, Elsevier, ISSN: 0304-3975