Algorithms and Complexity

Course Code: Ν2-3030
Weekly Duty: 4 (2Th + 1E + 1L)
Typical Semester: 3rd
Course Category: Special Infrastructure Course
Prerequisites: Algorithms Design, Discrete Mathematics

Learning Outcomes

This is the fundamental course in Computer Science. The course introduces the students in the basic concepts of the analysis of algorithms and complexity theory. It also provides an introductory approach to calculation models and basic classes of problems. Therefore, the students acquire a comprehensive understanding of the theories and calculation models and train in basic techniques of analysis of algorithms and complexity theory. Moreover, the course aims in the application of theoretical techniques to real problems.

Upon successful completion of this course the student / her will be able to:

  • master the basic tools of the analysis of algorithms,
  • apply the basic algorithmic techniques and strategies,
  • to analyze the algorithmic nature problems and classify them into classes according to their difficulty,
  • apply and implement basic algorithms on graphs,
  • analyze existing algorithms on the basis of their effectiveness,
  • choose the algorithm that is most appropriate for dealing with a “real”.

Course Content

Fundamental notions of algorithms and complexity theory. Models of computation and Turing machines. Classes P, NP and NP-Complete. Recursive functions, Dynamic programming and applications. Basic algorithmic techniques: searching, sorting, selection and merging. Graph algorithms: depth-first and breadth-first search, shortest paths, minimum spanning trees, flows. Hard problems: the travelling salesman problem, clique of a specific size, coloring, etc. Introduction to algorithms with performance guarantee.

  1. Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms,, 2007
  2. Sipser Μ., Introduction to the Theory of Computation, PWS Company, 1997.
  3. Papadimitriou C., Computational Complexity, Addison-Wesley, 1994.
  4. Moret B., The Theory of Computation, Addison-Wesley, 1998.
  5. Brookshear, Theory of Computation: Formal Languages, Automata and Complexity, Benjamin-Cummings Publishing Company, 1995.
  6. Gags P., Lovasz L., Complexity of Algorithms, Lecture Notes, 1999.
  7. Christofides N., Graph Theory. An Algorithmic Approach, Academic Press, 1975.
  8. Garey R.M., Johnson S.D., Computers and Intractability. A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979.
  9. Papadimitriou C., Steiglitz K. Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.
  10. Sedgewik R., Algorithms, Addison-Welsey,1984.
  11. Wilf S. H., Algorithms and Complexity, Prentice Hall,1986.

Internationalisation I18n