Description of Individual Course Units
Course Unit CodeCourse Unit TitleType of Course UnitYear of StudySemesterNumber of ECTS Credits
9105056022008Complexity Analysis of AlgorithmsElective128
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
1Ability to analyze algorithms space, time complexity and cost research under the real constraints.
2Ability to design new algorithm in order to solve a defined problem.
3Ability to classify the algorithms in accordance with their approaches.
4Ability to solve a new problem by using similarities between known problems.
5 Ability to compare different algorithms on various constraints.
6Ability to interpret algorithms’ performance outputs.
7Having knowledge about modern solutions about Computer Science’s known algorithms.
8Ability to analyze new algorithms with the help of comparing with the other known algorithms
9Ability 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
WeekTheoreticalPracticeLaboratory
1Stable matching problem, propose-and-reject algorithm, interval scheduling, analyze of bipartitematching. Computational tractability,asymptoticgrowth of functions, running time analysis.Problem Solution
2Graphs, graph representation, trees, breadth first search algorithm, depth first search algorithms, finding connected components, bipartite graphs, directed acyclic graphs, topologic order algorithm.Problem Solution
3Greedy algorithms: interval scheduling problem, optimum caching, Dijkstra's shortest path algorithm, coin-changing algorithm.Problem Solution
4Divide-conquer algorithms: mergesort,closest pair of points, integer multiplication, Karatsuba multiplication algorithm, matrix multiplication algorithms.Problem Solution
5Distributed 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
6Network flow, maximum flow and minimum cut problems, Ford-Fulkerson algorithm, relation between bipartitematching and Ford-Fulkerson maximum flow problems, assignment problem.Literature Survey
7Definition 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.
8Midterm
9Sequencing problems, Hamiltonian cycle problem, graph coloring: relation between 3-colorability and clique cover.
10Clique problem, relation between independent set and vertex cover problems, NP hard concepts, NP complete problem samples: planarcircuitsat, notallequal3sat, hittingset.
11Pspace concept, quantified satisfiability, scheduling problem, 15-Puzzle problem, Pspace complete concept, Psapace complete problems
12Extending 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
13Approximation algorithms to load balancing, k-center selection problem, pricing method, vertex cover, set cover, bin packing,travelling salesman.Literature Survey
14Center selection problem, vertex cover, greedy vertex cover problem, greedy set cover problem, relation between travelling salesman and minimum spanning tree problems.Problem Solution
15Randomization 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.
16Final 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 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 ActivitiesQuantityWeight
SUM0
End Of Term (or Year) Learning ActivitiesQuantityWeight
SUM0
SUM0
Language of Instruction
Turkish
Work Placement(s)
None
Workload Calculation
ActivitiesNumberTime (hours)Total Work Load (hours)
Midterm Examination133
Final Examination133
Attending Lectures14342
Report Preparation2510
Project Presentation133
Self Study9654
Individual Study for Homework Problems9545
Individual Study for Mid term Examination12020
Individual Study for Final Examination13636
Homework919
TOTAL WORKLOAD (hours)225
Contribution of Learning Outcomes to Programme Outcomes
PO
1
PO
2
PO
3
PO
4
PO
5
PO
6
PO
7
PO
8
PO
9
PO
10
PO
11
PO
12
PO
13
PO
14
PO
15
PO
16
PO
17
PO
18
PO
19
PO
20
PO
21
PO
22
PO
23
PO
24
LO145       5    34    3  3
LO24 4445 54     2  4 2   3
LO3 4       2     4    5   
LO4  4554 54       25  5  3
LO5 4       4    3    34   
LO6 4       5 3     3  32 4
LO744         5   5      4 
LO85        3       3 35  3
LO9   545  3          55  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 • e-mail: intrec@mail.ege.edu.tr