Algorithms and Complexity

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 of 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.