Wiki Τμήματος Μαθηματικών
Introduction to Computational Complexity (MAE542)

Introduction to Computational Complexity (MAE542)

Από Wiki Τμήματος Μαθηματικών

Undergraduate Courses Outlines - Department of Mathematics

General

School

School of Science

Academic Unit

Department of Mathematics

Level of Studies

Undergraduate

Course Code

MAE542

Semester

5

Course Title

Introduction to Computational Complexity

Independent Teaching Activities

Lectures, exercises, tutorials (Weekly Teaching Hours: 3, Credits: 6)

Course Type

Special Background

Prerequisite Courses -
Language of Instruction and Examinations

Greek

Is the Course Offered to Erasmus Students

Yes

Course Website (URL) -

Learning Outcomes

Learning outcomes

This course aims at introducing to students the concepts of time and space complexities for solving difficult problems. After successfully passing this course the students will be able to:

  • Understand complexity classes
  • Push further techniques for solving difficult problems
  • Understand difficult problems by using reductions.
General Competences
  • Search for, analysis and synthesis of data and information, with the use of the necessary technology
  • Working independently
  • Team work
  • Project planning and management

Syllabus

  • ΝΡ and Computational Intractibility
  • The class of PSPACE
  • Extending the limits of tractability
  • Approximation Algorithms
  • Local search.
  • Randomized algorithms

Teaching and Learning Methods - Evaluation

Delivery

Lectures

Use of Information and Communications Technology

Use of projector and interactive board during lectures.

Teaching Methods
Activity Semester Workload
Lectures 39
Working independently 78
Exercises-Homeworks 33
Course total 150
Student Performance Evaluation
  • Final written examination (70%)
  • Exercises / Homework (30%)

Attached Bibliography

See the official Eudoxus site or the local repository of Eudoxus lists per academic year, which is maintained by the Department of Mathematics. Additionally:

  • [Pa98] "Computational Complexity", Christos Papadimitriou.
  • [GJ77] "Computers and Intractability", M. R. Garey and D. S. Johnson.
  • [KT] J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008
  • [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.
Ανακτήθηκε από «https://wiki.math.uoi.gr/index.php?title=Introduction_to_Computational_Complexity_(MAE542)&oldid=462»