Minimum spanning trees: algorithms of Kruskal and Prim. Single-source shortest paths: Dijkstra's and Bellman-Ford algorithms, shortest paths in directed acyclic graphs. All-pairs shortest paths: Floyd-Warshall and Johnson's algorithms. Parallel algorithms: pointer jumping, CRCW versus EREW, Brent's theorem, prefix computation. Polynomials and the FFT. String matching: Rabin-Karp algorithm, string matching with finite automata, Knuth-Morris-Pratt and Boyer-Moore algorithms. Elementary computational geometry algorithms. Approximation algorithms: vertex-cover, traveling salesman and subset-sum problems.
İlk dosyayı sen ekleyebilirsin — notlar, geçmiş finaller, çözümler, cheat-sheet, ne varsa. Drive linki / PDF / ZIP / fotoğraf, hepsi olur.
Şu an: mail at, ben düzenleyip yayına alayım. Form/upload UX yakında geliyor (Kimya tasarlıyor).
| Dönem | Course CPA | |
|---|---|---|
| 2024-2025 Spring | 2.14 | 1 sec · 7 öğr |
| 2023-2024 Spring | 3.47 | 1 sec · 15 öğr |
| 2022-2023 Spring | 3.18 | 1 sec · 8 öğr |
| 2020-2021 Fall | 3.16 | 1 sec · 20 öğr |
| 2017-2018 Fall | 3.26 | 1 sec · 37 öğr |
| 2013-2014 Fall | 2.52 | 1 sec · 22 öğr |
| 2012-2013 Spring | 2.83 | 1 sec · 23 öğr |
| 2010-2011 Spring | 2.82 | 1 sec · 26 öğr |
| 2008-2009 Spring | 3.42 | 1 sec · 11 öğr |
| 2007-2008 Spring | 3.24 | 1 sec · 22 öğr |
Aggregate course GPA — Bilkent STARS'tan public data. Hoca-bazlı per-section detayı için STARS evaluation report →. Öğrenci anket cevapları KVKK kapsamında defter'de tutulmaz.
Course Learning Outcomes: Course Learning Outcome Assessment Become fluent in analyzing algorithms and data structures in terms of correctness and required computational resources. Midterm Final Comprehensively understand, use, and manipulate advanced and efficient data structures. Midterm Develop a comprehensive and in-depth understanding of common algorithm design techniques. Midterm Final Be able to design and analyze algorithms to solve new problems. Final Understand how to formulate differe
Any use of genAI tools in a homework/project assignment must be appropriately
Augmenting Data Structures: augmenting red-black trees, dynamic order statistics, interval trees. Advanced priority queue implementations: mergeable-heap operations, binomial heaps, fibonacci heaps, runtime analysis using potential method of analysis Data structures for disjoint sets: linked list representation, analysis of weighted union heuristic Data structures for disjoint sets: disjoint set forests, analysis of union-by-rank with path compression. Graphs and trees: definition, representation and notation. Breadth-First search: correctness of BFS, Breadth first trees Depth First search: timestamping vertices, parenthesis theorem, white-path theorem, edge classification. Topological sort of dags: DFS-based algorithm, proof of correctness, Kahn's algorithm Strongly connected components, use of DFS, proof of correctness, component graph Minimum Spanning Tree (MST): generic MST, proof of correctness, two famous greedy algorithms: Kruskal’s and Prim. Fast implementations of Kruskal's and Prim algorithms. Single-Source Shortest Paths (SSSP): shortest paths and relaxation, SSSP on dags, Dijkstra’s algorithm for positive edge weigths, Bellman Ford algorithm for general case. How to use Belmann Ford algorithm for a system of difference constraints for solving the feasibility problem on a system of difference constraints. All-pairs shortest paths (APSP) - two DP formulations leading to matrix multiplication and Floyd-Warshall algorithms. APSPs: transitive closure of a directed graph, Johnson’s algorithm for sparse graphs. Maximum Flows: flow networks, Ford-Fulkerson method, residual networks, augmenting paths, max-flow mincut theorem, Edmonds-Karp algorithm Maximum Flows: bipartite graph matching, integrality theorem, push-relabel algorithms ECTS - Workload Table: Activities Number Hours Workload Midterm exam 1 3 3 Course hours 14 3 42 Individual or group work 14 1 14 Homework 5 10 50 Preparation for Midterm exam 1 20 20 Preperation for Final exam 1 25 25 Final exam 1 3 3 Total Workload: 157 Total Workload / 30: 157 / 30 5.23 ECTS Credits of the Course: 5 Type of Course: Lecture Course Material: Slides - Lecture Notes - LMS (Moodle, etc) Teaching Methods: Lecture - Discussion