Faculty of Engineering and Natural Sciences · Software Engineering (English) · Undergraduate
ECTS: 5 T+P+L: 3+0+0 Departmental Elective
Coordinator: Dr. Öğr. Üyesi ARTRIM KJAMILJI
Course Objective
The main aim of this course is to design and analysis of algorithms, cover several advanced topics.
Course Content
The development of a sound theoretical understanding of advanced algorithms and practical problem-solving skills using them. Advanced algorithm topics are chosen from Trees, Graphs, Dynamic Programming, Linear Programming, Max Flow / Min Cut, Approximation Algorithms.
Course Learning Outcomes
- Develop a sound theoretical understanding of advanced algorithms and practical problem-solving skills using them.
- Develop a basic knowledge of a wide range of advanced algorithm design techniques including dynamic programming, linear programming, approximation algorithms, and Max Flow algorithms.
- Learn basic advanced algorithm analysis skills for analyzing the approximation ratio of approximation algorithms.
- Gain a good understanding of a wide range of advanced algorithmic problems, their relations, variants, and application to real-world problems.
- Use a suitable analysis method for any given algorithm.
- To be able prove correctness and running-time bounds.
- Design new algorithms for variations of problems studied in class.
Core Area Distribution
(46) Mathematics and Statistics%40 (48) Computing%30 (52) Engineering and Engineering Trades%30
Teaching Methods
ExpressionQuestion-AnswerDiscussionExercise and PracticeBrain StormingProblem Solving
Assessment & Evaluation
HomeworkTesting (Essay / Tests: True-Falls, multiple-choice, short answer, matching)
ECTS / Workload
| Activity | Quantity | Duration (h) | Total Workload |
|---|---|---|---|
| Course Duration (Including Exam Week) | 14 | 3 | 42 |
| Out of Class Study Period | 14 | 3 | 42 |
| Midterm | 1 | 16 | 16 |
| Quiz | 0 | 0 | 0 |
| Assignment | 2 | 10 | 20 |
| Practice | 0 | 0 | 0 |
| Final | 1 | 21 | 21 |
Course Schedule
| Week | Subject | Preparation |
|---|---|---|
| 1 | Introduction and motivation for the advanced algorithms | Lecture Notes |
| 2 | Asymptotic Notation and analysis | Lecture Notes |
| 3 | Divide and Conquer Paradigm. Recurrences | Lecture Notes |
| 4 | Solving Recurrences | Lecture Notes |
| 5 | Comparison based sorting. Quicksort. Sorting in linear time | Lecture Notes |
| 6 | Binary search trees | Lecture Notes |
| 7 | Red-Black trees | Lecture Notes |
| 8 | Midterm Exam | Midterm Exam |
| 9 | Augmenting data structures | Lecture Notes |
| 10 | Dynamic programming | Lecture Notes |
| 11 | Greedy algorithms | Lecture Notes |
| 12 | Amortized Analysis | Lecture Notes |
| 13 | Graph algorithms. Network flows | Lecture Notes |
| 14 | Sorting Networks | Lecture Notes |
| 15 | NP-Completeness | Lecture Notes |
| 16 | Final Exam | Lecture Notes |