UBE 602
Algorithm Complexity Theory


Spring 2022


Instructor: Prof.Dr.Mehmet Emin DALKILIÇ


References :  

·         Introduction to the Design and Analysis of Algorithms by Anany Levitin, Pearson-Addison-Wesley  2007

·         o       Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006.

     ( The bookseller info: Izmir Tıp Kitabevi 162.Sokak No:15/D Bornova 35040 Tel: 0 232 3428361 

http://www.izmirtip.com.tr/ , e-mail: mailto:info@izmirtip.com.tr)

Goals: To design and analysis of algorithms, prove correctness of algorithms, to be exposed to the theory of complexity, NP completeness, tractability, approximation and randomized algorithms

Prerequisites: Discrete Math, Data Structures and Algorithms


Topics :



Part I : Design and Analysis of Algorithms

Part II : NP Completeness



Approximate Grading


I.                   You can discuss homework with other people (especially with your classmates). However, you must write the answers to the homework questions alone, using your OWN WORDS. Copying and sharing homeworks will be penalized severly.

II.                If you submit your homework on time* you get 20% bonus, if you submit late* you receive 20% penalty, otherwise you get 0 points for that homework. Max. you can get from any homework is 100%.

III.             On time* means you hand in the homework on the due date (or early) to the Professor (thats me) at the start of the class.

IV.             Late* : Late homeworks can be submitted only to the TA  at most within a week after the due date. After a week no late homeworks will be accepted.

Final Exam TBA 09:15 (Monday)

Makeup (Bütünleme) Exam TBA 09:15 (Tentative)


Lecture Slides

Extra Slides 1 (demo Dijkstra)

Extra Slides 2 (demo Interval Scheduling)

Extra Slides 3 (Greedy Algorithms)

Extra Slides 4 (PSPACE)

Extra Slides 5 (Randomization)

Extra Slides 6 (Tractability)

Extra Slides 7 (ReductionsPoly)

Extra Slides 8 (np-complete)