UBE 602

UBE 602
Algorithm Complexity Theory

Spring 2016

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 Tip 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, Design and Analysis of Algorithms

Topics :

Part I : Design and Anaysis of Algorithms

Introduction : Some Representative Problems –
Basics of Algorithms Analysis : Computational Tractibility, Asymptotic Order of Growth
Graphs : Graph Connectivity and Graph Traversal, Biparttiteness, Topological Ordering
Greedy Algorithms : Interval Scheduling, MST, Kruskals Algorithm, Clustering
Divide and Conquer Algorithms : The Mergesort Algorithm, Recurrences, Counting Inversions, Finding the Closest Pair of Points, Integer Multiplication
Dynamic Programming : Weighted Interval Scheduling: A Recursive Procedure, RNA Secondary Structure: Dynamic Programming Over Intervals, Sequence Alignment, Shortest Paths and Distance Vector Protocols

Part II : NP Completeness

NP and Computational Intractability : Polynomial-time Reductions, Efficient Certification and the Definition of NP, NP-Complete Problems, Sequencing Problems, Partitioning Problems, Graph Coloring, Numerical Problems, co-NP and the Asymmetry of NP
PSPACE : PSPACE, Some Hard Problems in PSPACE, Solving Quantified Problems and Games in Polynomial Space, Solving the Planning Problem in Polynomial Space, Proving Problems PSPACE-Complete
Extending the Limits of Tractability : Finding Small Vertex Covers, Solving NP-hard Problem on Trees, Coloring a Set of Circular Arcs, Constructing a Tree Decomposition of a Graph
Approximation Algorithms : A Load Balancing Problem, The Center Selection Problem, Set Cover, the Pricing Method: Vertex Cover
Randomized Algorithms : Finding the Global Minimum Cut, Random Variables and their Expectations, Randomized Divide-and-Conquer: Median-Finding and Quicksort, Hashing: A Randomized Implementation of Dictionaries, Finding the Closest Pair of Points: A Randomized Approach, Randomized Caching, Load Balancing, Packet Routing

Approximate Grading

Assignments %30
Mid-term Exam : 30 %
Final Exam : 40 %

FINAL EXAM on June 6^th, 2016 at 13:15 (two hand written A4 help sheet is allowed)

Note that: 80% of the exam are from topics not covered in the midterm exam.

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 (Randomiztion)

Extra Slides 6 (Tractability)

Extra Slides 7 (ReductionsPoly)

Extra Slides 8 (np-complete)

Homework 1 (due date: March 7^th, 2016)

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) n³ d) n² e) n! f) 2ⁿ

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) (n³+1)⁶ b) (10n⁴ + 7n² + 3n)^0.5

c) 2n lg(2n + 2)³ + (n² + 2)²lg n d) 3ⁿ⁺¹ + 3^n-1

e) 2 log₂ 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 14^th, 2016)

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 21^st, 2016)

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?

4. a. Outline an algorithm for finding the smallest key in a binary search tree. Would you classify your algorithm as a variable-size decrease algorithm?

b. What is the time efficiency class of your algorithm in the worst case?

Homework #4 (Due date: March 28^th, 2016)

1. Show 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 5 (due date: April 4^th, 2016)

Problems 6.1.10, 6.4.4, 6.4.6, and 6.4.7 typedhomeork5

Homework 6 (due date: April 25^th, 2016)

1. (World Series odds) Consider two teams, A and B, playing a series of games

until one of the teams wins n games. Assume that the probability of A winning

a game is the same for each game and equal to p, and the probability of

A losing a game is q = 1− p. (Hence, there are no ties.) Let P(i, j) be the

probability of A winning the series if A needs i more games to win the series

and B needs j more games to win the series.

a. Set up a recurrence relation for P(i, j) that can be used by a dynamic

programming algorithm.

b. Find the probability of team A winning a seven-game series if the probability

of it winning a game is 0.4.

c. Write pseudocode of the dynamic programming algorithm for solving this

problem and determine its time and space efficiencies.

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 _(nW).

b. its space efficiency is _(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{c_n + F(n-2), F(n-1)} for n > 1

F(0) = 0, F(1) = c₁

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

is at least exponential.

Sample Midterm from Spring 2014

Homework 7 (due date: May 2^nd, 2016)

Problems 9.1.4, 9.2.2, 9.4.10, and an “out of the book” question typedhomework7

Homework 8 (due date: May 9^th, 2016) homework8spr2016

Homework 9 (due date: May 16^th, 2016) homework9spr2016

Homework #10 (due date: May 30th, 2016) homework10spr2016