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-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
Extra Slides 1 (demo Dijkstra)
Extra Slides 2 (demo Interval
Scheduling)
Extra Slides 3 (Greedy Algorithms)
Extra Slides 5 (Randomization)
Extra Slides 7 (ReductionsPoly)
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)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 n - 2 do
for j ¬ i + 1 to n - 1 do
for k ¬ i to n 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
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
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