
Description of Individual Course UnitsCourse Unit Code  Course Unit Title  Type of Course Unit  Year of Study  Semester  Number of ECTS Credits  9105056022008  Complexity Analysis of Algorithms  Elective  1  2  8 
 Level of Course Unit  Third Cycle  Objectives of the Course  The aim of this course is for students to design and analyze algorithms, prove correctness of algorithms, to understand the theory of complexity, NP completeness, tractability, approximation and randomized algorithms.  Name of Lecturer(s)  Prof. Dr. Mehmet Emin DALKILIÇ  Learning Outcomes  1  Ability to analyze algorithms space, time complexity and cost research under the real constraints.  2  Ability to design new algorithm in order to solve a defined problem.  3  Ability to classify the algorithms in accordance with their approaches.  4  Ability to solve a new problem by using similarities between known problems.  5  Ability to compare different algorithms on various constraints.  6  Ability to interpret algorithms’ performance outputs.  7  Having knowledge about modern solutions about Computer Science’s known algorithms.  8  Ability to analyze new algorithms with the help of comparing with the other known algorithms  9  Ability to design approximation algorithms for hard problems. 
 Mode of Delivery  Face to Face  Prerequisites and corequisities  None  Recommended Optional Programme Components  None  Course Contents  Algorithm Design and analysis: bases of algorithm analysis, computational tractability, asymptotically growth of functions, graphs: graphs connectivity and graph traversal algorithms, bipartiteness, topological order algorithm, greedy algorithms: interval scheduling, minimum spanning tree algorithms and clustering algorithms. Divide and conquer algorithms, dynamic programming algorithms and Distributed algorithms. NP and computational intractability: polynomial reductions, definition of NP, NP complete problem examples, sequencing problems, partitioning problems, graph coloring, numeric problems, coNP andthe asymmetry of NP intractability. Analysis of hard problems in Pspace, approximation algorithms and samples, Randomization algorithms and samples.  Weekly Detailed Course Contents  
1  Stable matching problem, proposeandreject algorithm, interval scheduling, analyze of bipartitematching. Computational tractability,asymptoticgrowth of functions, running time analysis.  Problem Solution   2  Graphs, graph representation, trees, breadth first search algorithm, depth first search algorithms, finding connected components, bipartite graphs, directed acyclic graphs, topologic order algorithm.  Problem Solution   3  Greedy algorithms: interval scheduling problem, optimum caching, Dijkstra's shortest path algorithm, coinchanging algorithm.  Problem Solution   4  Divideconquer algorithms: mergesort,closest pair of points, integer multiplication, Karatsuba multiplication algorithm, matrix multiplication algorithms.  Problem Solution   5  Distributed systems, distributed algorithms: broadcast, flooding, convergecast, distributes BFS algorithm, distributed DFS algorithm, Bellman Ford BFS algorithm Leader Election algorithms: Bully algorithm, LeLann’s ring algorithm.  Problem Solution   6  Network flow, maximum flow and minimum cut problems, FordFulkerson algorithm, relation between bipartitematching and FordFulkerson maximum flow problems, assignment problem.  Literature Survey   7  Definition of NP, polynomial reductions, reductions by equivalence, reductions withgadgets, 3Satisfiability, hamiltonian cycle problem. P, NP, EXP terms. NP completeness, NP complete problems,circuit satisfiability, 3SAT, coNP andasymmetry of NP.    8  Midterm    9  Sequencing problems, Hamiltonian cycle problem, graph coloring: relation between 3colorability and clique cover.    10  Clique problem, relation between independent set and vertex cover problems, NP hard concepts, NP complete problem samples: planarcircuitsat, notallequal3sat, hittingset.    11  Pspace concept, quantified satisfiability, scheduling problem, 15Puzzle problem, Pspace complete concept, Psapace complete problems    12  Extending tractability: finding minimum vertex cover,solving NP hard problems on trees: finding independent set on tree,wavelengthdivision multiplexingand relations between circular arc coloring and coloring intervals.  Problem Solution   13  Approximation algorithms to load balancing, kcenter selection problem, pricing method, vertex cover, set cover, bin packing,travelling salesman.  Literature Survey   14  Center selection problem, vertex cover, greedy vertex cover problem, greedy set cover problem, relation between travelling salesman and minimum spanning tree problems.  Problem Solution   15  Randomization algorithms, randomization algorithms,contention resolution,global minimum cut: contraction algorithm, linearity of expected value, maximum 3SAT, global hashing, Chernoff boundary, load balancing, Randomized divide and conquer.    16  Final Examination   
 Recommended or Required Reading  1. Algorithm Design by Jon Kleinberg andEva Tardos. Addison Wesley, 2006.
2. Introduction to the Design and Analysis of Algorithms by Anany Levitin, 2nd edition PearsonAddisonWesley , Michael Sipser,
3. Intro. to the Theory of Computation,2nd ed., Thompson Course Technology, 2005.  Planned Learning Activities and Teaching Methods   Assessment Methods and Criteria   Language of Instruction  Turkish  Work Placement(s)  None 
 Workload Calculation 

Midterm Examination  1  3  3  Final Examination  1  3  3  Attending Lectures  14  3  42  Report Preparation  2  5  10  Project Presentation  1  3  3  Self Study  9  6  54  Individual Study for Homework Problems  9  5  45  Individual Study for Mid term Examination  1  20  20  Individual Study for Final Examination  1  36  36  Homework  9  1  9  
Contribution of Learning Outcomes to Programme Outcomes  LO1  4  5         5      3  4      3    3  LO2  4   4  4  4  5   5  4       2    4   2     3  LO3   4         2       4      5     LO4    4  5  5  4   5  4         2  5    5    3  LO5   4         4      3      3  4     LO6   4         5   3       3    3  2   4  LO7  4  4           5     5        4   LO8  5          3         3   3  5    3  LO9     5  4  5    3            5  5    3 
 * Contribution Level : 1 Very low 2 Low 3 Medium 4 High 5 Very High 



Ege University, Bornova  İzmir / TURKEY • Phone: +90 232 311 10 10 • email: intrec@mail.ege.edu.tr 
