UBE 602

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

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

Extra Slides 6 (Tractability)

Extra Slides 7 (ReductionsPoly)

Extra Slides 8 (np-complete)

Homework 1 (due date: March 4th^th, 2019)

homework1typed

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

homework2typed

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

homework3typed

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

1. Exercise 4.4.10, Exercise 4.5.1, Exercise 4.5.6

homework4typed

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)

homework5typed

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