UBE 602
Algorithm Complexity Theory


Spring 2019


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 30% penalty, otherwise you get 0 points for that homework.

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 (thats Gül) at most within a week after the due date. After a week no late homeworks will be accepted.

Final Exam TBA 13:15 (Monday)

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


Homework 1 (due date: March 4thth, 2019)



Homework 2 (due date: March 11thth, 2019)

1. Exercise 2.6.1, 2.6.2, Exercise 3.1.5, 3.3.4 and 3.3.5



Homework 3 (due date: March 18thth, 2019)



Homework 4 (due date: March 25th, 2019)

1. Exercise 4.4.10, Exercise 4.5.1, Exercise 4.5.6


Hint for Euclids algorithm analysis question:

a. The answer follows immediately from the formula underlying Euclids
b. Let mod n. Investigate two cases of r
s value relative to ns


Homework 5 (due date: April 1st, 2019)



Homework 6 (due date: April 15th, 2019)

Problems 6.1.10, 6.4.4, 6.4.6, and 6.4.7 typedhomework6


Homework 7 (due date: April 22th, 2019)

Problems 7.1.4, 7.1.8, 7.2.1, 7.3.5 typedhomework7


Homework 8 (due date: April 29th, 2019)

1.    (Shortest-path counting) A chess rook can move horizontally or vertically to any square in the same row or in the same column of a chessboard. Find the number of shortest paths by which a rook can move from one corner of a chessboard to the diagonally opposite corner. The length of a path is measured by the number of squares it passes through, including the first and the last squares. Solve the problem

a.      by a dynamic programming algorithm

b.       by using elementary combinatorics

2.    a. Write pseudocode of the bottom-up dynamic programming algorithm for

the knapsack problem.

b.      Write pseudocode of the algorithm that finds the composition of an optimal

subset from the table generated by the bottom-up dynamic programming

algorithm for the knapsack problem.

3. For the bottom-up dynamic programming algorithm for the knapsack problem,

prove that

a. its time efficiency is O(nW).

b. its space efficiency is O(nW).

c. the time needed to find the composition of an optimal subset from a filled

dynamic programming table is O(n).


4. a) Show that the time efficiency of solving the coin-row problem by straightforward

application of recurrence (8.3 given below) is exponential.

F(n) = max{cn + F(n-2), F(n-1)} for n > 1

F(0) = 0,F(1) = c1

b) Show that the time efficiency of solving the coin-row problem by exhaustive search

is at least exponential.


Homework 9 (due date: May 6th, 2019)

Problems 9.1.4, 9.2.2, 9.4.10, and an out of the book question typedhomework9


Homework #10 (due date: May 13nd, 2019) typedhomework10


Homework #11 (due date: May 20th, 2019) typedhomework11