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

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.

Extra Slides 1 (demo Dijkstra)

Extra Slides 2 (demo Interval
Scheduling)

Extra Slides 3 (Greedy Algorithms)

Extra Slides 7 (ReductionsPoly)

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

**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_{1}

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