UBE 518

UBE 602
Algorithm Complexity Theory

Spring 2013

Instructor: Prof.Dr.Mehmet Emin DALKILIÇ

=

References :

·      =    Introduction to the Design and Analysis of Algorit= hms by Anany= Levitin, Pearson-Addison-Wesley 2007

·      =    o       Algorithm Design by Jon Kleinberg and Eva Tardos. Addison Wesley, 2006.
    ( The bookseller info: Izmir Tip = Kitabevi 162.Sokak No:15/D Bornova 35040 Tel: 0 232 3428361

h= ttp://www.izmirtip.com.tr/ , e-mail: info@izmirtip.com.tr)=

Goals: To design and analysis of algorithms, prove correctness of alg= orithms, to be exposed to the theory of complexity, NP completeness, tractability, approximation and randomized algorithms

Prerequisites: Discrete Math, Data Structures and Algorithms, Design and Analysis of Algorithms

Topics :

Part I : Design and Anaysis of Algorithm= s

Introduct= ion : Some Representative Problems –

Basics of Algorithms Analysis : Computational Tractibility, Asymptotic Order of Growth <= /span>

Graphs : Graph Connectivity and Graph Traversal, Biparttiteness<= /span>, Topological Ordering

Greedy Algorithms : Interval Scheduling, MS= T, Kruskals 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 PSPA= CE, 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 Al= gorithms : A Load Balancing Problem, The Center Selection Problem, Set Cover, t= he Pricing Method: Vertex Cover

Randomized Algorithms : Finding the Global M= inimum 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

<= o:p>

Approximate Grading

Assignments %30

Mid-term Exam : 30 %

Final Exam : 40 % =