**UBE 602
Algorithm Complexity Theory**

**Spring 2019**

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

**HOMEWORK POLICY:**

**I.**** ****You can discuss homework with other people
(especially with your classmates). However, you must write the answers to the
homework questions alone, using your OWN WORDS. Copying and sharing homeworks will be penalized severly.**

**II.**** ****If you submit your homework on time* you
get 20% bonus, if you submit late* you receive 30% penalty, otherwise you get 0
points for that homework.**

**III.**** ****On time***** means you hand in the homework on the due date (or early)
to the Professor (that****’****s me) at the start of the class.**

**IV.**** ****Late***** :**** Late homeworks
can be submitted only to the TA (that****’****s G****ü****l) at most within a week after the due
date. After a week no late homeworks will be
accepted.**

Final Exam TBA 13:15 (Monday)

Makeup (Bütünleme)
Exam TBA 13:15
(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: March 4th ^{th}, 2019)**

**Homework 2 (due date: March 11th ^{th}, 2019)**

1. Exercise 2.6.1, 2.6.2, Exercise 3.1.5, 3.3.4
and 3.3.5

**Homework 3 (due date: March 18th ^{th}, 2019)**

**Homework 4 (due date: March 25 ^{th}, 2019)**

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 1 ^{st}, 2019)**

**Homework 6 (due date: April 15 ^{th}, 2019)**

Problems 6.1.10, 6.4.4, 6.4.6,
and 6.4.7 typedhomework6

**Homework 7** (due
date: April 22th, 2019)

Problems 7.1.4, 7.1.8, 7.2.1, 7.3.5 typedhomework7

**Homework 8 (due date: April 29 ^{th}, 2019)**

**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 6 ^{th}, 2019)**

Problems 9.1.4, 9.2.2, 9.4.10,
and an out of the book question typedhomework9

**Homework #10** (due date: May 13nd, 2019) **typedhomework10**

**Homework #11** (due date: May 20th,
2019) **typedhomework11**