School of Engineering \ Computer Engineering
Course Credit
ECTS Credit
Course Type
Instructional Language
Programs that can take the course
Computer Engineering
Artificial Intelligence Engineering
This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times. Topics include sorting and selection, algorithm design techniques: divide-and-conquer, greedy algorithms, dynamic programming, graph algorithms (minimum spanning trees, shortest paths, connectivity problems), proofs of intractability and NP-completeness.
Textbook and / or References
Introduction to Algorithms. Third Edition. By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. McGraw-Hill.
Algorithm Design. By Jon Kleinberg and Eva Tardos. Addison Wesley.
The aim of this course is to teach major algorithmic design paradigms and well known example problems that employ these paradigms. The course emphasizes proving the correctness of algorithms, and analyzing their running times.
1. Solve problems that involve sorting and selection.
2. Design a divide-and-conquer algorithm to solve an appropriate problem when an algorithmic design situation calls for it.
3. Design a greedy algorithm to solve an appropriate problem when an algorithmic design situation calls for it.
4. Use dynamic programming to solve an appropriate problem when an algorithmic design situation calls for it.
5. Solve problems using the fundamental graph algorithms, including single-source and all-pairs shortest paths, topological sort, and minimum spanning tree algorithms.
Week 1: Review of Asymptotics, Summations, Recurrences, Insertion Sort
Week 2: Divide-and-Conquer (Mergesort, Inversion Counting, Closest Pair)
Week 3: Quicksort, Analysis of Randomized Quicksort
Week 4: Randomized Selection and Analysis, Deterministic Selection
Week 5: Linear Sorting via Counting Sort, Radix Sort
Week 6: Greedy Algorithms (Exchange Argument, Interval Scheduling, Fractional Knapsack, Minimizing Maximum Lateness, Huffmann Coding)
Week 7: Graph Representations, Elementary Graph Algorithms (DFS, BFS)
Week 8: DFS applications (Articulation Points and Bridges, Strongly Connected Components, Topological Sorting)
Week 9: Minimum Spanning Tree Algorithms (Kruskal, Prim) Shortest Paths with Dijkstra
Week 10: Dynamic Programming I (Weighted Interval Sch. , Memoization, Iteration over Subproblems, Longest Common Subsequnce, Matrix Chain Multiplication)
Week 11: Dynamic Programming II (0-1 Knapsack, All-pairs Shortest Paths via Floyd-Warshall)
Week 12: NP-Completeness
Tentative Assesment Methods
• Midterm 40 %
• Final 45 %
• Homeworks 15 %
|
Program Outcome
*
|
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
Course Outcome
|
|---|
| 1 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 2 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 3 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 4 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|
| 5 |
C, D
|
A, B
|
|
|
|
C
|
B
|
|
|
|
|