defter*
defter / katalog / CS 502
CS 502

Algorithms II

CS 502 is the graduate continuation of the algorithms sequence, where the focus shifts from "can you code a sort" to proving correctness, bounding resources tightly, and recognizing when a new problem reduces to one you've already solved. Most of the term lives on graphs, shortest paths, spanning trees, max-flow, but you also spend serious time on amortized analysis of Fibonacci heaps and disjoint sets, plus string matching, FFT, and approximation schemes for NP-hard problems. Assessment is two midterms, a final, and three projects, with the projects pushing you to actually implement and reason about the trickier data structures. It's the backbone course that the rest of theoretical CS (complexity, cryptography, networks, ML theory) leans on.

Kredi3ECTS5FakülteFaculty of EngineeringBölümComputer EngineeringKoordinatörCevdet Aykanat

→ STARS müfredatı (resmi syllabus)

Haftalık müfredat 14 hafta

Hafta 114–20 Eyl
Veri yapılarını augment etme teknikleri
Augmenting Data Structures: augmenting red-black trees, dynamic order statistics, interval trees.
red-black treedynamic order statisticsinterval treeaugmentation
Hafta 221–27 Eyl
İleri priority queue implementation'ları
Advanced priority queue implementations: mergeable-heap operations, binomial heaps, fibonacci heaps, runtime analysis using potential method of analysis
binomial heapFibonacci heapmergeable-heap operationspotential method
Hafta 328 Eyl – 4 Eki
Disjoint Set'lerin Linked List Gösterimi
Data structures for disjoint sets: linked list representation, analysis of weighted union heuristic
disjoint setslinked listweighted union heuristic
Hafta 45–11 Eki
Disjoint Set Forest ve Path Compression
Data structures for disjoint sets: disjoint set forests, analysis of union-by-rank with path compression.
disjoint set forestsunion-by-rankpath compressionanalysis
Hafta 512–18 Eki
Graph, tree ve breadth-first search
Graphs and trees: definition, representation and notation. Breadth-First search: correctness of BFS, Breadth first trees
graphtreeBFSbreadth-first tree
Hafta 619–25 Eki
Depth First Search ve kenar sınıflandırması
Depth First search: timestamping vertices, parenthesis theorem, white-path theorem, edge classification.
Depth First Searchtimestampingparenthesis theoremwhite-path theorem
Hafta 726 Eki – 1 Kas
DAG'lerde topological sort algoritmaları
Topological sort of dags: DFS-based algorithm, proof of correctness, Kahn's algorithm
topological sortDAGDFSKahn's algorithm
Hafta 82–8 Kas
DFS ile strongly connected components
Strongly connected components, use of DFS, proof of correctness, component graph
strongly connected componentsDFSproof of correctnesscomponent graph
Hafta 99–15 Kas
Minimum spanning tree ve greedy algoritmalar
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.
minimum spanning treeKruskalPrimgreedy algorithm
Hafta 1016–22 Kas
Tek kaynaklı en kısa yollar
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.
SSSPDijkstraBellman-Forddifference constraints
Hafta 1123–29 Kas
Tüm çiftler için en kısa yollar (APSP)
All-pairs shortest paths (APSP) - two DP formulations leading to matrix multiplication and Floyd-Warshall algorithms.
all-pairs shortest pathsdynamic programmingmatrix multiplicationFloyd-Warshall
Hafta 1230 Kas – 6 Ara
Tüm çiftler için en kısa yollar
APSPs: transitive closure of a directed graph, Johnson’s algorithm for sparse graphs.
APSPtransitive closuredirected graphJohnson's algorithm
Hafta 137–13 Ara
Maximum flow: Ford-Fulkerson ve Edmonds-Karp
Maximum Flows: flow networks, Ford-Fulkerson method, residual networks, augmenting paths, max-flow mincut theorem, Edmonds-Karp algorithm
flow networkFord-Fulkersonaugmenting pathEdmonds-Karp
Hafta 1414–20 Ara
Maximum flow: bipartite matching ve push-relabel
Maximum Flows: bipartite graph matching, integrality theorem, push-relabel algorithms
bipartite matchingintegrality theorempush-relabel

Değerlendirme 100% · 4 adım

40%
30%
3%
27%
Midterm Midterm 40%
Final Final 30%
In-class attendance Attendance 3%
Project Project 27%
en büyük tek kalem %40 · sınav ağırlığı %70 · 10 dönem ortalaması 3.00 (191 öğrenci) nasıl hesaplanıyor

Önerilen kaynaklar 2 kitap

📕
Zorunlu
Introduction to Algorithms
T.H.Cormen, C.E.Leiserson and R.L. Rivest
1994 · MIT Press & McGraw-Hill
📖
Önerilen
Applied and Algorithmic Graph Theory
G. Chartrand and O. R. Oellermann
1993 · McGraw-Hill

Bu dersi alınca · 6 öğrenme çıktısı

Bilkent'in resmî syllabus'ünden. Sağdaki etiket o çıktının hangi değerlendirmeyle ölçüldüğünü söylüyor.

🤖 GenAI politikası

Any use of genAI tools in a homework/project assignment must be appropriately

Ders notları · henüz yok

CS 502 için defter ekibi henüz not yazmadı.

İlk dosyayı sen atarsan: not, slayt, geçmiş sınav, çözüm, cheat-sheet, ne varsa. defter ekibi öğrenci paylaşımlarından bu dersin notlarını yazar. Drive linki / PDF / ZIP, hepsi olur.

← katalog

Geçmiş GPA dağılımı 10 dönem · ort. 3.00

DönemCourse 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. Tüm derslerin ortalamaları →

2026-2027 Güz için şubesi henüz görünmüyor. Kayıt sistemi bu dersi bu dönem listelemiyor, ama şube girişi sürüyor: ders kaydı 15 Eylül, bölümler o güne kadar şube ekleyebiliyor. Son 4 güz döneminde açılmamış; en son 2020-2021 güz döneminde açılmış. Ön kayıt müfredat üzerinden yapılıyor, açılan şube listesi üzerinden değil; o yüzden ön kayıtta seçebildiğin bir dersin şubesi burada henüz görünmeyebilir. Kesin sonuç ders kaydında belli oluyor. kayıt tarihleri → · açık dersler

⚠️ FZ engelleyen şartlar

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

Hocalar 0 bu dönem · 3 geçmiş

Geçmişte ders veren (3 kişi)
Cevdet Aykanat, Uğur Doğrusöz, Mehmet Koyutürk