CS341 – Complexity Theory
Bachelor of Science in Computing and Business Technologies
Core Course
CS341 – Complexity Theory
Course Unit Code: CS341
Type Of Unit: Core
Level of Course Unit: First cycle
Year of Study: Third year
Semester: Core
Number of ECTS Credits: 7.5
Class Contact Hours: 36
Mode of Delivery
Face to Face
Prerequisites
Course Objectives
The objective of this course is to introduce students to the theory of computational complexity. The students will learn how to analyse the complexity of algorithms, and important concepts in this area, like the P=NP problem and the master theorem.
Learning Outcomes
- Understand basic notions in computational complexity theory: turing machines and the halting problem.
- Understand the different complexity classes, like NP and P.
- Understand how to analyse the complexity of algorithms.
- Understand how to analyse divide and conquer algorithms and learn how to use the master theorem.
- Introduction to graph theory and algorithms.
Course Content
Course Features
Planned learning activities and teaching methods
Lectures; in-class discussion and debates; in-class exercises; problem sets; team work; video case studies, team presentations, interactive online learning via Moodle (quizzes, assignments, forums)
Assessment methods and criteria
10% Class Participation
90% Final Examination
Language of Instruction
English
Readings
Textbooks:
1. Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009
Optional textbook:
2. Richard Wilson (2010). Introduction to Graph Theory
3. Miklos Bona (2011) A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory: An Introduction to Enumeration and Graph Theory (Third Edition)
English (UK) 
Ελληνικά