Algorithms and Advanced Data Structures

Course Aim and Objectives:

The aim of this course is to cover key techniques for designing and analyzing algorithms. Specifically, the main objectives are:

  • Equipping students with mathematical preliminaries, general tools and techniques for analyzing
  • Familiarizing students with important techniques for designing algorithms as well as with specific algorithms for a number of important computational problems.
  • Enabling students to study and follow the research developments in the area of the design and analysis of algorithms and advanced data structures.

Course Description:

The need for efficient algorithms arises in almost every area of computer science, though the type of problem to be solved, the meaning of which algorithm is effective and the computational model may vary from sector to sector. This course presents algorithm design and analysis techniques and advanced data structures, and illustrates them using a number of well-known problems and applications. Specifically:

  • it discusses recurrence relations, and their role in asymptotic and probabilistic analysis of algorithms;
  • it studies in detail greedy strategies, divide and conquer techniques, dynamic programming and linear programming;
  • it presents the application of the above approaches to problems such as sorting, scheduling, graph traversal, set covering;
  • it covers popular graph (shortest paths and flows) and basics of randomized algorithms and computational complexity.

Bibliography

  • Aho A.V., J.E. Hopcroft and J.D. Ullman. The Design and Analysis of Computer Algorithms, Addison Wesley, 2008.
  • Bazaraa M.S., Jarvis J.J, Sherali H. D., Linear programming and network flows, 2nd, J. Wiley 1990.
  • H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, 3rd ed, The MIT Press, 2009.
  • H. Cormen, C.E. Leiserson , R.L. Rivest and C. Stein. Εισαγωγή στους Αλγορίθµους, Ελληνική Έκδοση, Πανεπιστηµιακές Εκδόσεις Κρήτης, 2012.
  • Peter Brass. Advanced Data Structures. Cambridge University Press, 2008.
  • Kleinberg και E. Tardos, Σχεδιασμός Αλγορίθμων, Εκδόσεις Κλειδάριθμος, 2008.
  • Dasgupta, C. Papadimitriou και U. Vazirani. Αλγόριθμοι, Εκδόσεις  Κλειδάριθμος.
  • Ahuja, T. Magnanti, and J. Orlin, Network Flows, Prentice-Hall, 1993.
  • E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
  • Mehlhorn and S. Naeher, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, 1999.
  • Mueller-Hannemanni and S. Schirra, Algorithm Engineering – Bridging the Gap between Algorithm Theory and Practice, Springer 2010.