**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**** **

**Introduction :**Some Representative Problems –**Basics of Algorithms Analysis :**Computational Tractibility, Asymptotic Order of Growth**Graphs :**Graph Connectivity and Graph Traversal, Bipartiteness, Topological Ordering**Greedy Algorithms :**Interval Scheduling, MST, Kruskal’s 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- A
**pproximation 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 % Sample Final Exam

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 6 ^{th}, 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) **n^{3}** d)** n^{2}** e) **n!** f) **2^{n}

**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^{3}+1)^{6} b)
(10n^{4} + 7n^{2} + 3n)^{0.5}

c)
2n lg(2n
+ 2)^{3} + (n^{2} + 2)^{2 }lg n d)
3^{n+1} + 3^{n-1}

e) 2
log_{2} 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 **

//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 13 ^{th}, 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 20 ^{th}, 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 27 ^{th}, 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 3rd ^{th},
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 17 ^{th}, 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 8 ^{th}, 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 15 ^{th}, 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**