UBE 602

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