          Description of Individual Course Units
 Course 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 co-requisities
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, co-NP andthe asymmetry of NP intractability. Analysis of hard problems in Pspace, approximation algorithms and samples, Randomization algorithms and samples.
Weekly Detailed Course Contents
 Week Theoretical Practice Laboratory 1 Stable matching problem, propose-and-reject 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, coin-changing algorithm. Problem Solution 4 Divide-conquer 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, Ford-Fulkerson algorithm, relation between bipartitematching and Ford-Fulkerson maximum flow problems, assignment problem. Literature Survey 7 Definition of NP, polynomial reductions, reductions by equivalence, reductions withgadgets, 3-Satisfiability, hamiltonian cycle problem. P, NP, EXP terms. NP completeness, NP complete problems,circuit satisfiability, 3-SAT, co-NP andasymmetry of NP. 8 Midterm 9 Sequencing problems, Hamiltonian cycle problem, graph coloring: relation between 3-colorability 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, 15-Puzzle 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,wavelength-division multiplexingand relations between circular arc coloring and coloring intervals. Problem Solution 13 Approximation algorithms to load balancing, k-center 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 3-SAT, global hashing, Chernoff boundary, load balancing, Randomized divide and conquer. 16 Final Examination
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 Pearson-Addison-Wesley , 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
 Term (or Year) Learning Activities Quantity Weight SUM 0 End Of Term (or Year) Learning Activities Quantity Weight SUM 0 SUM 0
Language of Instruction
Turkish
Work Placement(s)
None 