UBE 602
Algorithm Complexity Theory

 

Spring 2024


 

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

HOMEWORK POLICY:

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 submit (upload) the homework before or on the due date to the system (EGEDERS).

IV.             Late* : Late homeworks can be submitted via system (EGEDERS) at most within a week after the due date. After a week no late homeworks will be accepted by the system.

Final Exam TBA 09:30 (Wednesday)

Makeup (Bütünleme) Exam TBA 09:30 (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)