SEN2212 · 14. hafta · Review.

Final tekrarı: hangi yapı, hangi algoritma, hangi Big-O

Dönemin tamamı tek sayfada: problem tipine göre yapı/algoritma seçme tablosu, bütün işlemlerin Big-O özeti ve her konudan birer karışık final sorusu.

time complexityworst caseaverage caseamortizedbinary search treeAVL treered-black treeB-treebinary heappriority queuehash tableload factorgraph traversaltopological sortshortest pathminimum spanning treegreedycomparison sort lower bound

Bu sayfa finalden önceki son tur. Konu anlatımı yok; her konunun “bunu bilmeden sınava girme” kısmını, karar tablolarını ve Big-O özetini bir araya topluyor. Her bölümün ayrıntısı kendi haftasında. Final soruları genelde iki tür: iz soruları (ağaç, heap dizisi, hash tablosu, graf sırası, Dijkstra tablosu, Huffman kodu, MST kenarları) ve seçim soruları (“bu problem için hangi yapı, neden, karmaşıklığı ne?”). Aşağıdaki 12 soru her konudan birer tane.

Altın kurallar:

İz sorusunda her adımı yaz. Ara durum puan getirir, son cevap yanlış olsa bile.
Eşitlik kuralını yaz. Soru belirtmiyorsa “ties by smallest label” gibi bir satır ekle.
Big-O sorarken en kötü mü ortalama mı, sor. BST ve hash’te ikisi çok farklı.
Dengeli/dengesiz ayrımını unutma. “BST’de arama O(log n)” sadece dengeliyse doğru.

Problem → yapı / algoritma karar tablosu

İhtiyaç	Seç	Neden
Anahtara göre ara/ekle/sil, sıra önemsiz	Hash tablosu	Ortalama $O(1)$
Sıralı tut, aralık sorgusu, min/max, k. eleman	AVL / kırmızı-siyah ağaç	En kötü $O(\log n)$ , inorder sıralı
Diskte çok büyük sıralı veri (veritabanı indeksi)	B-ağacı	Düğüm başına çok anahtar, az disk erişimi
Son erişilenlere tekrar tekrar erişim	Splay ağacı	Erişilen köke gelir, amortize $O(\log n)$
Hep en küçüğü/en acili al	Binary heap (PriorityQueue)	findMin $O(1)$ , deleteMin $O(\log n)$
n elemandan en küçük k tanesi	Boyutu k olan max-heap ya da buildHeap + k deleteMin	$O(n \log k)$ ya da $O(n + k \log n)$
Genel sıralama, kararlı	Merge sort	$O(n \log n)$ garanti
Yerinde sıralama, ortalama en hızlı	Quicksort	$O(n \log n)$ ortalama
Küçük aralıklı tam sayılar	Counting / radix sort	$O(n + k)$ , $O(d(n+b))$
Ağırlıksız en kısa yol	BFS	$O(V + E)$
Ağırlık ≥ 0 en kısa yol	Dijkstra	$O(E \log V)$
Negatif kenar olabilir	Bellman-Ford	$O(VE)$
Görev sırası, bağımlılıklar	Topolojik sıralama (Kahn / DFS)	$O(V + E)$
Tüm düğümleri en ucuza bağla	Prim / Kruskal	$O(E \log V)$
İki düğüm aynı bileşende mi	Union-find	Neredeyse $O(1)$
Metni sıkıştır	Huffman	$O(n \log n)$
Çakışmayan en çok etkinlik	Greedy: en erken biten	$O(n \log n)$

Big-O özeti

Sıralama

Algoritma	En iyi	Ortalama	En kötü	Ek bellek	Kararlı
Insertion	$n$	$n^2$	$n^2$	$1$	evet
Merge	$n \log n$	$n \log n$	$n \log n$	$n$	evet
Quick	$n \log n$	$n \log n$	$n^2$	$\log n$	hayır
Heap	$n \log n$	$n \log n$	$n \log n$	$1$	hayır
Counting	$n + k$	$n + k$	$n + k$	$n + k$	evet
Radix (LSD)	$d(n+b)$	$d(n+b)$	$d(n+b)$	$n + b$	evet

Karşılaştırmaya dayalı her sıralamanın en kötü durumu $\Omega(n \log n)$ : karar ağacının $n!$ yaprağı var, yüksekliği en az $\log_2 n! \approx n \log n$ .

Ağaçlar, heap, hash

Yapı	Arama	Ekleme	Silme	Not
BST	ort. $\log n$ , en kötü $n$	aynı	aynı	Sıralı girdide zincire döner
AVL	$\log n$	$\log n$	$\log n$	Yükseklik ≈ $1.44 \log n$
Kırmızı-siyah	$\log n$	$\log n$	$\log n$	Yükseklik ≤ $2\log(n+1)$ , daha az rotasyon
B-ağacı (derece m)	$\log_m n$ disk erişimi	aynı	aynı	Tüm yapraklar aynı seviyede
Splay	amortize $\log n$	aynı	aynı	Tek işlem $n$ olabilir
Binary heap	$n$	$\log n$	deleteMin $\log n$	findMin $1$ , buildHeap $n$
Hash tablosu	ort. $1$ , en kötü $n$	aynı	aynı	Rehash $O(n)$ , amortize $O(1)$

Graf ve greedy

Algoritma	Süre	Hatırlatma
BFS / DFS	$O(V + E)$	Matrisle $O(V^2)$
Topolojik sıralama	$O(V + E)$	Sadece DAG
Dijkstra (heap)	$O(E \log V)$	Negatif kenar yok
Bellman-Ford	$O(VE)$	V−1 tur, V. tur negatif döngü testi
Prim (heap)	$O(E \log V)$	Tek ağaç büyür
Kruskal	$O(E \log E)$	Sıralama + union-find
Huffman	$O(n \log n)$	n−1 birleştirme
Etkinlik seçimi	$O(n \log n)$	Bitişe göre sırala

TUZAK · “heap’te arama O(log n)”. Heap sadece kök için sıra garantisi verir. Rastgele bir anahtarı aramak $O(n)$ . Arama gerekiyorsa dengeli BST ya da hash.

Konu konu kontrol listesi

Ağaçlar (2-4. hafta). Preorder: kök-sol-sağ. Inorder: sol-kök-sağ, BST’de sıralı çıkar. Postorder: sol-sağ-kök. Level-order: kuyrukla. Yükseklik: boş ağaç −1, tek düğüm 0. BST silmede üç durum: yaprak (sil), tek çocuk (çocuğu bağla), iki çocuk (ardılı kopyala, ardılı sil).

Dengeli ağaçlar (5-6). AVL’de ekleme yolundaki ilk dengesiz düğümde rotasyon yap. Yeni anahtar dengesiz düğümün sol çocuğunun solundaysa LL (sağa tek rotasyon), sağ çocuğunun sağındaysa RR (sola tek), iç taraflardaysa LR/RL (çift). Kırmızı-siyah: kök siyah, kırmızının çocuğu kırmızı olamaz, her yolda eşit sayıda siyah. Amca kırmızıysa renk değiştir, siyahsa rotasyon.

Heap ve öncelik kuyruğu (7-8). Yapı özelliği: tam ağaç (complete). Sıra özelliği: ebeveyn ≤ çocuk (min-heap). Ekleme sonda başlar ve yukarı çıkar; deleteMin son elemanı köke koyar, küçük çocukla aşağı iner. buildHeap n/2’den 1’e percolateDown, $O(n)$ . Java PriorityQueue varsayılan olarak min-heap’tir.

Hashing (9). Load factor $\lambda = n / M$ . Ayrı zincirleme (separate chaining) $\lambda \approx 1$ ile iyi çalışır. Açık adreslemede (open addressing) $\lambda \le 0.5$ tut. Doğrusal yoklama birincil kümelenme, karesel yoklama ikincil kümelenme yapar. Çift hash’te ikinci fonksiyon asla 0 döndürmemeli. Tablo dolunca yaklaşık iki katı büyüklükte bir asal boyuta rehash.

Graflar (10-11). BFS kuyruk, DFS yığın/özyineleme. Dijkstra her adımda en küçük bilinmeyeni seçer. Yönlü döngü = gri düğüme kenar.

Greedy ve MST (12-13). Greedy’nin yanlışlığı tek karşı örnekle gösterilir. Kruskal döngü kuran kenarı reddeder. Prim’in tablosunda değer kenar ağırlığıdır, yol toplamı değil.

Sınav sabahı ipuçları

1. min-heap mi max-heap mi? kök 0 mı 1 mi?
2. Hash: M, h(k), yoklama türü?
3. Graf: yönlü mü? komşu sırası? başlangıç?
4. Huffman/Kruskal: eşitlik kuralı?
5. Ara durumları yaz, cevabı kutuya al

Sık yapılan hatalar

Yanlış düşünce	Doğrusu
BST’de arama her zaman $O(\log n)$	Sadece dengeliyse; en kötü $O(n)$
AVL’de kökte rotasyon yapılır	Ekleme yolundaki ilk dengesiz düğümde
deleteMin’de büyük çocukla yer değiştir	Min-heap’te KÜÇÜK çocukla
buildHeap $O(n \log n)$	Floyd yöntemi $O(n)$
Hash’te silinen hücreyi boş yap	Açık adreslemede “silindi” işareti (lazy deletion)
Dijkstra negatif kenarla çalışır	Bellman-Ford kullan
Prim tablosunda d[v] + w	Prim’de sadece w
Radix sort her geçişte herhangi bir sıralama kullanabilir	Geçişler KARARLI olmalı
Counting sort da $\Omega(n \log n)$ ile sınırlı	Karşılaştırma yapmaz, sınıra tabi değil

Kendini test et

Sınavdaki gibi İngilizce sorular. Önce kâğıt kalemle çöz, sonra cevabı aç.

Soru 1orta

Insert 50, 30, 70, 20, 40, 60, 80, 35 into an empty BST. Give the preorder traversal. Then delete 30 (two children: replace with the inorder successor) and give the new preorder.

Cevabı göster

Before: 50 30 20 40 35 70 60 80; after: 50 35 20 40 70 60 80

        50
      /    \
    30      70
   /  \    /  \
  20  40  60  80
      /
     35

30'un iki çocuğu var. Ardılı (successor) sağ alt ağacın en küçüğü: 35. 30'un yerine 35 yazılır, 35 eski yerinden silinir (yaprak). Yeni preorder: 50 35 20 40 70 60 80. Inorder her zaman sıralı: 20 35 40 50 60 70 80.

Soru 2zor

Insert 10, 20, 30, 40, 50, 25 into an empty AVL tree. Which rotations happen, and what is the final preorder traversal?

Cevabı göster

RR at 10, RR at 30, RL at 20; preorder 30 20 10 25 40 50

30 eklenince 10'un BF'si -2, sağ-sağ: 10'da sola tek rotasyon, kök 20.
50 eklenince 30'un BF'si -2, sağ-sağ: 30'da sola rotasyon, 20(10, 40(30, 50)).
25 eklenince 20'nin BF'si h(10) - h(40) = 0 - 2 = -2. 25, 40'ın SOL alt ağacına girdi: sağ-sol (RL). Önce 40'ta sağa, sonra 20'de sola rotasyon:

        30
       /  \
     20    40
    /  \     \
   10  25    50

Soru 3orta

Insert 15, 9, 12, 4, 7, 10, 2 one by one into an empty binary min-heap (array, root at index 1). Give the final array.

Cevabı göster

[2, 7, 4, 15, 9, 12, 10]

Her eklemede sona koy, ebeveyninden küçük oldukça yukarı çık (percolate up):

15          [15]
9           [9, 15]
12          [9, 15, 12]
4           [4, 9, 12, 15]
7           [4, 7, 12, 15, 9]
10          [4, 7, 10, 15, 9, 12]
2           [2, 7, 4, 15, 9, 12, 10]

Son adımda 2 indeks 7'ye girer, ebeveyn 3 (10) ile, sonra ebeveyn 1 (4) ile yer değiştirir.

Soru 4orta

On the heap [2, 7, 4, 15, 9, 12, 10], perform deleteMin twice. Give the array after each.

Cevabı göster

[4, 7, 10, 15, 9, 12] then [7, 9, 10, 15, 12]

1. deleteMin: 2 çıkar, son eleman 10 köke gelir, küçük çocukla aşağı iner: 4 ile yer değiştirir, sonra 12 ile karşılaştırılır, 10 < 12 durur. 2. deleteMin: 4 çıkar, 12 köke gelir; çocuklar 7 ve 10, 7 yukarı; 12'nin yeni çocukları 15 ve 9, 9 yukarı. Sonuç [7, 9, 10, 15, 12].

Soru 5zor

Run buildHeap (min-heap, Floyd's method, root at index 1) on [9, 4, 7, 1, 8, 2, 6]. Give the array after each percolateDown call and the final heap.

Cevabı göster

down(3): [9, 4, 2, 1, 8, 7, 6]; down(2): [9, 1, 2, 4, 8, 7, 6]; down(1): [1, 4, 2, 9, 8, 7, 6]

n/2 = 3'ten 1'e geriye doğru percolateDown. İndeks 3 (7): çocuklar 2 ve 6, 2 yukarı. İndeks 2 (4): çocuklar 1 ve 8, 1 yukarı. İndeks 1 (9): çocuklar 1 ve 2, 1 yukarı; 9 indeks 2'de, çocuklar 4 ve 8, 4 yukarı; 9 indeks 4'te yaprak. Toplam süre $O(n)$ ; tek tek eklemek $O(n \log n)$ olurdu.

Soru 6orta

Hash table of size M = 11, h(k) = k mod 11, linear probing. Insert 22, 13, 35, 4, 46, 15. At which index does each key end up?

Cevabı göster

22→0, 13→2, 35→3, 4→4, 46→5, 15→6

h değerleri: 22→0, 13→2, 35→2, 4→4, 46→2, 15→4. 35: 2 dolu, 3. 46: 2, 3, 4 dolu, 5. 15: 4, 5 dolu, 6. Doğrusal yoklama 2-6 arasında bir küme (primary clustering) oluşturdu.

Soru 7zor

Same keys and table, but quadratic probing (h(k) + i², i = 0, 1, 2, ...). Where do 46 and 15 go?

Cevabı göster

46→6, 15→5

46: 2 dolu, 2+1 = 3 dolu, 2+4 = 6 boş. 15: 4 dolu, 4+1 = 5 boş. Diğerleri doğrusal ile aynı: 22→0, 13→2, 35→3, 4→4. Karesel yoklama kümeyi dağıtır; M asal ve λ ≤ 0.5 iken boş yer bulmak garanti.

Soru 8orta

LSD radix sort (base 10) on [213, 85, 402, 77, 160, 39, 518]. Give the array after the first pass (ones digit) and after the second pass (tens digit).

Cevabı göster

Pass 1: [160, 402, 213, 85, 77, 518, 39]; pass 2: [402, 213, 518, 39, 160, 77, 85]

Her geçiş KARARLI (stable) kova dağıtımıdır. Birler: 0 (160), 2 (402), 3 (213), 5 (85), 7 (77), 8 (518), 9 (39). Onlar: 0 (402), 1 (213, 518), 3 (39), 6 (160), 7 (77), 8 (85). Üçüncü geçiş sıralı diziyi verir: 39 77 85 160 213 402 518. Süre $O(d(n + b))$ .

Soru 9orta

DAG on 0..6 with edges 0→2, 1→2, 1→3, 2→4, 3→4, 4→5, 3→6, 6→5. Run Kahn's algorithm, always removing the smallest vertex with in-degree 0. Give the topological order.

Cevabı göster

0 1 2 3 4 6 5

Başta in-degree 0 olanlar: 0, 1. 0 çıkar (2'nin derecesi 1). 1 çıkar: 2 ve 3 sıfıra iner. 2 çıkar (4 → 1). 3 çıkar: 4 ve 6 sıfır. 4 çıkar (5 → 1). 6 çıkar: 5 sıfır. 5 çıkar.

Soru 10orta

Directed graph: S→A 7, S→B 2, B→A 3, A→C 1, B→C 8, C→D 2, B→D 9. Dijkstra from S: final distances to A, B, C, D?

Cevabı göster

A=5, B=2, C=6, D=8

Sıra S, B, A, C, D. B (2) A'yı 7'den 5'e, C'yi 10, D'yi 11 yapar. A (5) C'yi 6'ya indirir. C (6) D'yi 8'e indirir. Doğrudan kenarlar (S→A 7, B→D 9) daha pahalı.

Soru 11orta

Huffman coding with frequencies 3, 5, 6, 8, 20. What is the total number of encoded bits?

Cevabı göster

Birleştirmeler: 3+5 = 8, 6+8 = 14, 8+14 = 22, 20+22 = 42. Toplam bit = iç düğüm ağırlıkları toplamı = 8+14+22+42 = 86. Eşitlikte (6 ile hangi 8 birleşir) kodlar değişebilir, toplam bit değişmez.

Soru 12kolay

Choose the best structure for each task: (a) repeatedly get the most urgent job, (b) check membership of a word in a dictionary in average O(1), (c) keep keys sorted with guaranteed O(log n) insert and search, (d) print all keys in sorted order and find the k-th smallest quickly.

Cevabı göster

(a) binary heap / priority queue, (b) hash table, (c) AVL or red-black tree, (d) balanced BST

(a) findMin $O(1)$ , deleteMin $O(\log n)$ . (b) Hash tablosu ortalama $O(1)$ ama sırayı tutmaz. (c) Düz BST sıralı girdide $O(n)$ 'e bozulur; dengeli ağaç en kötü durumda $O(\log n)$ . (d) Inorder dolaşım sıralı verir; heap ve hash sıralı çıktı vermez.

Doğrulama: Tüm iz cevapları (BST ekleme/silme dolaşımları, AVL rotasyonları, heap ekleme/deleteMin/buildHeap dizileri, doğrusal ve karesel yoklamalı hash tabloları, LSD radix geçişleri, Kahn topolojik sırası, Dijkstra mesafeleri, Huffman toplam biti) verify/SEN2212/W14.java ile çalıştırılıp çıktıdan alındı (java W14.java).

Deftere not kartı

Sıralama alt sınırı (karşılaştırma): Ω(n log n); counting/radix bu sınıra tabi değil merge O(n log n) kararlı, ek dizi | quick ort n log n, en kötü n² | heap n log n yerinde BST ort O(log n), en kötü O(n) | AVL, RB en kötü O(log n) BST silme 2 çocuk: inorder successor (sağın en küçüğü) AVL: BF = h(L) - h(R), |BF| > 1 → LL/RR tek, LR/RL çift rotasyon heap 1-indeks: çocuk 2i, 2i+1, ebeveyn i/2; insert/deleteMin O(log n), buildHeap O(n) hash ort O(1); linear → primary clustering; quadratic → M asal, λ ≤ 0.5 graf: matris O(V²) yer, liste O(V+E); BFS/DFS/topo O(V+E) Dijkstra O(E log V), ≥ 0 ağırlık | Bellman-Ford O(VE), negatif kenar Prim O(E log V), Kruskal O(E log E), MST'de V-1 kenar Huffman: en küçük iki birleşir, toplam bit = iç düğümler toplamı Greedy doğru: etkinlik (erken biten), kesirli çanta; YANLIŞ: 0/1 çanta, garip paralar