Algorithms and Complexity
|Lecture hours||3 hours|
|Lab hours||2 hours|
|Digital resources||View on Aristarchus (Open e-Class)|
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.
- 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)
- Τ. 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