ALGORITHMS AND COMPLEXITY

Course Information
TitleΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ / ALGORITHMS AND COMPLEXITY
CodeNGE-07-01
FacultySciences
SchoolInformatics
Cycle / Level1st / Undergraduate
Teaching PeriodWinter
CoordinatorGeorgios Christodoulou
CommonYes
StatusActive
Course ID40002972

Programme of Study: PPS-Tmīma Plīroforikīs (2019-sīmera)

Registered students: 23
OrientationAttendance TypeSemesterYearECTS
GENIKĪ KATEUTHYNSĪYPOCΗREŌTIKO KATA EPILOGĪ745

Class Information
Academic Year2019 – 2020
Class PeriodWinter
Instructors from Other Categories
Weekly Hours3
Class ID
600154416
Course Type 2016-2020
  • Background
  • General Knowledge
  • Scientific Area
Course Type 2011-2015
Specific Foundation / Core
Mode of Delivery
  • Face to face
Erasmus
The course is also offered to exchange programme students.
Language of Instruction
  • Greek (Instruction, Examination)
  • English (Examination)
Prerequisites
Required Courses
  • NCO-01-04 DISCRETE MATHEMATICS
  • NCO-02-02 PROBABILITIES & STATISTICS
  • NCO-02-03 DATA STRUCTURES
  • NCO-04-03 ALGORITHMS
Learning Outcomes
Knowledge: Understand the mapping of problems to algorithmic solutions (such as graph problems). Understand the performance limitations of algorithms for specific problem categories. Understand different complexity classes (P, NP, NP hard, NP complete). Learn different techniques for solving difficult problems through the use of algorithms (such as exponential algorithms, randomized algorithms, approximation algorithms) Skills: Understand algorithm reductions (the relationship between different problems with regards to their computational demands)
General Competences
  • Adapt to new situations
  • Make decisions
  • Work autonomously
  • Design and manage projects
  • Advance free, creative and causative thinking
Course Content (Syllabus)
Linear Programming (e.g., duality, simplex method, interior point algorithms). Number-theoretic algorithms (e.g., modular arithmetic, primality testing, integer factorization). Randomized algorithms. Approximation algorithms. Probabilistic analysis. Online algorithms and competitive analysis. Local Search.
Keywords
Complexity, Algorithms
Educational Material Types
  • Notes
  • Slide presentations
  • Book
Use of Information and Communication Technologies
Use of ICT
  • Use of ICT in Course Teaching
Course Organization
ActivitiesWorkloadECTSIndividualTeamworkErasmus
Lectures39
Reading Assigment48
Written assigments60
Exams3
Other / Others
Total150
Student Assessment
Description
Written exams on the covered material (book, lecture notes, presentations, exercises). Comprehension theoretical/programming exercises whose grade is additive to the grade of the final exams.
Student Assessment methods
  • Written Exam with Short Answer Questions (Summative)
  • Written Exam with Extended Answer Questions (Summative)
  • Performance / Staging (Formative, Summative)
  • Written Exam with Problem Solving (Formative, Summative)
Bibliography
Course Bibliography (Eudoxus)
1. Michael Sipser. Εισαγωγή στην Θεωρία Υπολογισμού. Πανεπιστημιακές Εκδόσεις Κρήτης, 2007. 2. J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
Additional bibliography for study
1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein: Εισαγωγή στους Αλγόριθμους, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.
Last Update
09-12-2020