UBE 602
Algorithm Complexity Theory

 

Spring 2017


 

Instructor: Prof.Dr.Mehmet Emin DALKILI«

 

References :

         Introduction to the Design and Analysis of Algorithms by Anany Levitin, Pearson-Addison-Wesley2007

         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

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 6th, 2017)

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 13th, 2017)

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

homework2typed

 

Homework 3 (due date: March 20th, 2017)

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

            else

            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

            else

            for iŖ1 to n do

            HeapPermute(n-1)

            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?

 

Homework 4 (due date: March 27th, 2017)

1. Exercise 4.4.10, Exercise 4.5.1, Exercise 4.5.6

homework4typed

Hint for Euclidís algorithm analysis question:

a. The answer follows immediately from the formula underlying Euclidís
algorithm.
b. Let
r = m mod n. Investigate two cases of rís value relative to nís
value.

 

Homework #5 (Due date: April 3rdth, 2017)

1. Show (prove) that QuickSort runs in O(n log n) time in average for random arrays.

2. ALGORITHM Height(T )

//Computes recursively the height of a binary tree

//Input: A binary tree T

//Output: The height of T

if T =  return 1

else return max{Height(Tlef t ), Height(Tright)} + 1

Analyze the best-case, worst-case and average case time efficiency of the above recursive algorithm.

3. a. For the one-dimensional version of the closest-pair problem, i.e., for the

problem of finding two closest numbers among a given set of n real numbers,

design an algorithm that is directly based on the divide-and-conquer

technique and determine its efficiency class.

b. Is it a good algorithm for this problem?

 

Homework 6 (due date: April 17th, 2017)

Problems 6.1.10, 6.4.4, 6.4.6, and 6.4.7 typedhomework6

 

Homework 7 (due date: April 24th, 2017)

Problems 7.1.4, 7.1.8, 7.2.1, 7.3.5 typedhomework7

Homework 8 (due date: May 8th, 2017)

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 15th, 2017)

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

Homework #10 (due date: May 22nd, 2017) homework10spr2017

Homework #11 (due date: May 29th, 2017) homework11spr2017