**UBE 602
Algorithm Complexity Theory**

**Spring 2023**

**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 Tractability, 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 20% penalty, otherwise you get 0
points for that homework. Max. you can get from any homework is 100%.**

**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 at most
within a week after the due date. After a week no late homeworks
will be accepted.**

Final Exam TBA 13:15 (Wednesday)

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)