ALGORITHMS AND COMPLEXITY

 Title ΑΛΓΟΡΙΘΜΟΙ ΚΑΙ ΠΟΛΥΠΛΟΚΟΤΗΤΑ / ALGORITHMS AND COMPLEXITY Code NGE-07-01 Faculty Sciences School Informatics Cycle / Level 1st / Undergraduate Teaching Period Winter Coordinator Georgios Christodoulou Common Yes Status Active Course ID 40002972

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

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

 Academic Year 2019 – 2020 Class Period Winter Instructors from Other Categories Weekly Hours 3 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
• 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
Lectures39
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.