UBE 602
Algorithm Complexity Theory


Spring 2018


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


Final Exam June 6th, 2018 13:15 (Monday)

Makeup (Bütünleme) Exam June 27th, 2018 13:15 (Wednesday) (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: Feb 26th, 2018)

1.      For each of the following functions, indicate how much the function’s value will change if its argument is increased threefold.


a)      n log 2n   b) n    c) n3     d) n2     e) n!     f) 2n


2.      For each of the following functions, indicate the class θ(g(n)) the function belongs to. (Use the simplest g(n) possible in your answer.) Prove your assertions.


a)     (n3+1)6                                                 b) (10n4 + 7n2 + 3n)0.5

c) 2n lg(2n + 2)3 + (n2 + 2)lg n                d) 3n+1 + 3n-1

e) 2 log2 n


3. You are facing a wall that stretches infinitely in both directions. There is a door in the wall, but you know neither how far away nor in which direction. You can see the door only when you are right next to it.

a) Design an algorithm that enables you to reach the door by walking at most O(n) steps where n is the (unknown to you) number of steps between your initial position and the door.

b) Prove that the time efficiency (complexity) of your algorithm is O(n).


4. Algorithm GaussianElimination(A[0..n-1,0..n])

//Implements Gaussian elimination of an n-by-(n+1) matrix A

for i ¬ 0 to - 2 do
for j 
¬ i + 1 to - 1 do 
for k 
¬ i to do

A[j,k¬ A[j,k- A[i,k* A[j,i] / A[i,i]

Find the efficiency class and a constant factor improvement.


Homework 2 (due date: March 5thth, 2018)

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



Homework 3 (due date: March 12th, 2018)

1. Design a decrease-by-one algorithm for finding all the factors of a given number n. Also design a decrease-by-one algorithm for finding all the prime factors of a given number n.


 2.Consider the following algorithm to check connectivity of a graph defined by its adjacency matrix.

            ALGORİTHM Connected(A[0..n-1,0..n-1])

            // Input: Adjacency matrix A[0..n-1,0..n-1] of an undirected graph G

            // Output: 1 (true) if G is connected and 0 (false) if it is not

            if n=1 return 1                       // one-vertex graph is connected by definition


            if not Connected(A[0..n-2,0..n-2]) return 0

            else for jß0 to n-2 do

                        if A[n-1,j] return 1

                        return 0

Does this algorithm work correctly for every undirected graph with n>0 vertices? If you answer yes, indicate the algorithm’s efficiency class in the worst case; if you answer no, explain why.


 3.Consider the following implementation of the algorithm for generating permutations discovered by B. Heap.

            ALGORİTHM HeapPermute(n)

            // Implements Heap’s algorithm for generating permutations

            // Input: A positive integer n and a global array A[1..n]

            // Output: All permutations of elements A

            if n=1

            write A


            for iß1 to n do


            if n is odd

            swap A[1] and A[n]

            else swap A[i] and A[n]

a. Trace the algorithm by hand for n = 2, 3 and 4.

b. Prove the correctness of Heap’s algorithm.

c. What is the time efficiency of HeapPermute?