**UBE 602
Algorithm Complexity Theory**

**Spring 2018**

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

Final Exam June 6^{th}, 2018 13:15
(Monday)

Makeup (Bütünleme)
Exam June 27^{th}, 2018 13:15 (Wednesday) (Tentative)

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: Feb 26th, 2018)**

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 5th ^{th}, 2018)**

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 12 ^{th},
2018)**

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