Algorithm Analysis and Complexity
Information Systems Engineering
Faculty of Technology
First Cycle (Bachelor's Degree)
| Course Unit Title | Course Unit Code | Type of Course Unit | Level of Course Unit | Year of Study | Semester | ECTS Credits |
|---|---|---|---|---|---|---|
| Algorithm Analysis and Complexity | TBL343 | Elective | Bachelor's degree | 3 | Fall | 5 |
Name of Lecturer(s)
Associate Prof. Dr. Süleyman EKEN
Research Assistant Seda BALTA
Learning Outcomes of the Course Unit
1) Defines basic data structures (such as tree, list, stack, queue, graph)
2) Compares the main algorithmic design paradigms (such as divide-and-conquer, decrease-and-conquer, transform-and-conquer)
3) Solves common types of algorithmic problems
4) Applies basic algorithms and data structures to real-world problems
5) Analyzes the accuracy of the algorithm
6) Implements algorithms, data structures and program relationships
Program Competencies-Learning Outcomes Relation
| Program Competencies | ||||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | ||
| Learning Outcomes | ||||||||||||
| 1 | No relation | No relation | No relation | High | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 2 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 3 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 4 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 5 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
| 6 | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | No relation | |
Mode of Delivery
Face to Face
Prerequisites and Co-Requisites
None
Recommended Optional Programme Components
Not Required
Course Contents
Background: Discrete mathematics; Data structures. Introduction to Algorithms: What is an algorithm; Various problems. Algorithm Analysis: Algorithm complexity; My impression asks. Recursive Functions and Solution Methods: Substitution method; Characteristic equation method; Master theorem. Direct Algorithm Design with Brute Force Method: Sorting algorithms; Search algorithms; Sequence analogy problem; Closest binary problem; Convex envelope problem; Complete and detailed search method. Break-Solve Method: Sorting algorithms; Search algorithms; Strassen matrix multiplication algorithm; Closest binary problem; Convex envelope problem; Integer multiplication problem. Reduce-Solve Method: Sorting algorithms; Graph traversal algorithms, depth first and propagation first; Topological ordering; Algorithms for creating combinatorial objects; Counterfeit money problem; Selection problem. Change-Solve Method: Solving by sorting; Gauss elimination algorithm; Balanced search trees; Sorting by stack and heap; Horner's rule and double exponent; Problem analogy. Dynamic Programming Method: 0/1 Backpack problem; Shortest paths (all pairs); Optimal binary search tree; Sequence analogy; Matrix chain multiplication. Ambitious Programming Method: Backpack problem; Minimum covering tree; Shortest paths (single source); Terminated job sorting; Huffman tree; Activity selection problem. Incremental Development Method; The simplex method; Maximum current problem. Complexity Classes; Basic definitions; P, NP and NP-Complete classes; NP- Complete problems.
Weekly Schedule
1) Intro2) Analysis
3) Elementary sorting
4) Merge sort
5) Recurrence
6) Quick sort
7) Elementary search
8) Binary search
9) Midterm exam
10) Hashing
11) Graphs
12) MST
13) Shortest path alg
14) Trees
15) Data compression
16) Final exam
Recommended or Required Reading
Planned Learning Activities and Teaching Methods
Assessment Methods and Criteria
Contribution of Semester Studies to Course Grade |
60% |
|||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||
Contribution of Final Examination to Course Grade |
40% |
|||||||||||
Total | 100% | |||||||||||
Language of Instruction
Turkish
Work Placement(s)
Not Required