|
|
home · studies

Algorithms and Complexity |
Module Type: |
Special Foundation |
Module Code: |
421 |
Syllabus: |
Asymptotic symbolism and analysis of algorithms (sequencing, for/while/repeat loops, recursive calls).
Analysis of ‘search and sort’ algorithms. Greedy algorithms (e.g. Kruskal, Prim algorithms). Design techniques:
Top-down technique, Bottom-up technique. Probabilistic algorithms (e.g. Monte Carlo, Las Vegas algorithms).
Elements of parallel algorithms. Elements of complexity. Classes P and NP. |
Module Aims-Objectives: |
The aims of this module, which is the continuity of ‘Data structures and Algorithms’ module, are towards the
introduction and elaboration on more complex and specialised algorithms (such as parallel and probabilistic algorithms),
along with the establishment of concepts like the complexity analysis of algorithms and the importance of well-founded
estimation of the algorithm’s realisation time.
Upon completing this module students should be in a position to assess the complexity of an algorithm and be familiar
with the design techniques employed for its implementation. They should also be in a position to develop complex algorithms and
estimate the time required for its elaboration. |
Bibliography: |
• John Chatziligeroudis, «Data Structures, Introducrion to Computer Science, Volume III», Hellenic Open University, Patra, 2000
• Colin Reeves (Edited), “Modern Heuristic Techniques for Combinatorial
Problems�, McGraw Hill Book Company, UK, 1995
• Herbert S. Wilf, “Algorithms And Complexity�, Prentice Hall Inc., USA,
1986
• Robert Sedgewick, “Algorithms In C�, Addison – Wesley Publishing
Company, USA, 1998
• Michael R. Garey, David S. Johnson,“Computers And Intractability, A
Guide To The Theory Of NP-Completeness�, W.H. Freeman And Company,
New York, USA, 1979
|
|
|
|
|
|