---
title: "Quiz 1 Gözden Geçirme"
subtitle: "Ders 1-12 toplu tekrar — büyük dört (çöz/kanıtla/verimli/anlat), iki çözüm yolu (sıfırdan vs İNDİRGE), üç problem tipi (white-box/black-box/modification), tuzaklar (rasyonel-radix-augmentation) ve iki gerçek sınav problemi (Criminal Seafood + Rainy Research)"
---
::: {.callout-note title="Oturum bilgisi"}
- **Ku'nun videosu:** [YouTube — Quiz 1 Review](https://www.youtube.com/watch?v=e98MPnMHLxE) (≈85 dk — normal dersten uzun!)
- **OCW sayfası:** [MIT 6.006 Quiz 1 Review](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/quiz-1-review/)
- **Seri:** MIT 6.006 — Introduction to Algorithms (Spring 2020) — Ders 14 (Quiz 1 Review)
- **Hoca:** Jason Ku
- **Okuma süresi:** ≈28 dk
> Bu **normal bir ders değil** — Quiz 1 öncesi **toplu tekrar** oturumudur. Kursun ilk yarısını (Ders 1-12) tek çatı altında toparlar ve sınavda nasıl düşünüleceğini öğretir.
:::
## Bu Quiz Review Ne Hakkında? {#sec-bu-quiz-review-ne-hakkinda-d14}
Bu, Jason Ku ile **Quiz 1 öncesi toplu tekrar** oturumudur. Kursun **ilk yarısını** (Ders 1-12: hesaplama modeli, asimptotikler, özyineleme/master teoremi, sıralama, hashing, ikili ağaçlar/AVL, ikili yığın) tek çatı altında toparlar ve **sınavda nasıl düşünüleceğini** öğretir. İçerik üç eksende ilerler: (1) quiz neyi ölçer, (2) konu tekrarı (veri yapıları + sıralama bloğu), (3) iki gerçek sınav problemi çözümü.
> *"What are we trying to test you in this class? ... Algorithms. ... Also data structures."* — Ku, 0:40
Ku'nun **"büyük dört"** hedefi (kursun ve quiz'in özü): bir hesaplama problemini (1) **çöz**, (2) **doğru** olduğunu kanıtla, (3) **verimli** olduğunu göster, (4) bunu başkalarına **anlat**.
> *"part of this class is about communication. If your thing is correct but we can't tell what you're saying, then it's not correct."* — Ku, 33:24
```{mermaid}
%%| label: fig-concept-map
%%| echo: false
%%| fig-cap: "Ders 14'ün (Quiz 1 Review) kavram haritası: kök = Quiz 1 Review. Beş dal — (1) büyük dört: çöz / kanıtla / verimli yap / anlat (iletişim de puana dahil). (2) iki çözüm yolu: sıfırdan tasarla (zor, nadiren istenir) vs bilinen kara kutuya İNDİRGE (esas beklenen). (3) üç problem tipi: white-box (içyapı) / black-box (reduction) / modification (augmentation). (4) tuzaklar: rasyonel hesabı (çapraz çarp), her şeye radix, subtree-property olmayan augmentation. (5) konu tabloları: sıralama (heap/radix özel), sequence (doubly-linked O(1) uç), set (augmented AVL ⊃ sorted array). Sonuç: Quiz 1 = icat değil SEÇİM sınavı."
flowchart TD
A["Ders 14: Quiz 1 Review"] --> B["Büyük dört<br/>çöz · kanıtla · verimli · anlat"]
A --> C["İki çözüm yolu"]
C --> C1["sıfırdan tasarla (zor)<br/>İNDİRGE (esas beklenen)"]
A --> D["Üç problem tipi"]
D --> D1["white-box · black-box<br/>modification"]
A --> E["Tuzaklar"]
E --> E1["rasyonel hesabı (çapraz çarp)<br/>her şeye radix · sahte augmentation"]
A --> F["Konu tabloları"]
F --> F1["sıralama · sequence · set + PQ"]
classDef root fill:#fef3c7,stroke:#b45309,stroke-width:3px,color:#1f2937
classDef branch fill:#f3f4f6,stroke:#374151,stroke-width:2px,color:#1f2937
classDef leaf fill:#ffffff,stroke:#9ca3af,stroke-width:1px,color:#1f2937
class A root
class B,C,D,E,F branch
class C1,D1,E1,F1 leaf
```
::: {.callout-tip title="Builder Notu — Bu = İlk-Yarı Midterm"}
Quiz 1, kursun ilk-yarı sınavıdır: veri yapıları + sıralama bloğunu kapsar. Çizge ve dinamik programlama, Quiz 2-3'e kalır.
- **Bu = midterm.** OMSCS CS 6515 (Graduate Algorithms) ekseninde Quiz 1, "veri yapısı + sıralama refleksi" yani lisansüstü dersin giriş varsayımıdır.
- **Reduction = mühendisliğin kalbi.** "Bilinen bir kara kutuya indirge" disiplini, hem graduate algoritma dersinin hem de gerçek sistem tasarımının temel refleksidir.
- **İleriye → graduate algorithms:** burada öğrenilen "önce arayüz (correctness), sonra implementasyon (efficiency)" ayrımı, DP ve NP-tamlıkta birebir tekrar eder.
Tek cümle: *Quiz 1, "yeni algoritma icat et" demez; "doğru kara kutuyu seç, neye indirgediğini ve neyi sakladığını net söyle, sonra verimliliği optimize et" der.*
:::
```{python}
#| echo: false
# ============================================================================
# SETUP — 6.006 Ders 14 (Quiz 1 Review, Ku) motoru INLINE (_engine_QR1.py +
# gereken AVL altyapısı _engine.py'den) + Slate+Amber viz (_viz.py COL_*).
# Bu hücre gizlidir (#| echo: false). Aşağıdaki figür hücreleri bu hücrede
# tanımlanan CrossLinkedWaitlist / build_time_tree / peak_rainfall / brute_peak
# + build_avl + COL_*'ı IMPORT ETMEDEN kullanır.
#
# NOT: matplotlib.use("Agg") ÇAĞRILMAZ — Quarto'nun inline figür-yakalama
# backend'ini ezer (plt.show() 0 figür üretir). Quarto render'da jupyter inline
# backend'i ayarlar. Yalnız QR1 gerekenler gömülür.
# ============================================================================
import matplotlib.pyplot as plt
from matplotlib.patches import (
Circle, FancyBboxPatch, FancyArrowPatch, Polygon, Rectangle,
)
# ---------------------------------------------------------------------------
# _viz.py — Slate+Amber stil sabitleri (HEX birebir)
# ---------------------------------------------------------------------------
COL_PRIMARY = "#374151" # slate-700 — birincil çizgi/çerçeve
COL_ACCENT = "#f59e0b" # amber-500 — vurgu
COL_TEXT = "#1f2937" # slate-800 — metin
COL_BG = "#f3f4f6" # slate-100 — arka plan / kutu dolgusu
COL_AMBER_700 = "#b45309" # bağlantı/okunur kontrast
COL_AMBER_600 = "#d97706" # koyu amber
COL_AMBER_300 = "#fcd34d" # açık amber
COL_AMBER_100 = "#fef3c7" # en açık amber (dolgu)
COL_SLATE_500 = "#6b7280" # orta slate — ikincil metin
COL_SLATE_400 = "#9ca3af" # soluk slate — pasif kenar / izgara
COL_WHITE = "#ffffff"
# ---------------------------------------------------------------------------
# _engine.py — AVL altyapısı (Ders 10 / L7). Quiz P2 (Rainy Research) için
# build_avl gerekir; rebalance zinciri (rotasyonlar) bağımlılık olarak gömülür.
# height = 1 + max(çocuk yükseklikleri), boş = −1; size = sol+sağ+1.
# ---------------------------------------------------------------------------
class AVLNode:
"""AVL düğümü (L7): item + iki alt-ağaç özelliği (height, size)."""
__slots__ = ("item", "left", "right", "parent", "height", "size")
def __init__(self, item):
self.item = item
self.left = None
self.right = None
self.parent = None
self.height = 0
self.size = 1
def _h(node):
"""Boş alt-ağaç yüksekliği −1 (yaprak = 0)."""
return node.height if node is not None else -1
def _s(node):
"""Boş alt-ağaç boyutu 0."""
return node.size if node is not None else 0
def update_node(node):
"""Güncelleme kuralı (O(1)): çocuklardan height + size."""
node.height = 1 + max(_h(node.left), _h(node.right))
node.size = 1 + _s(node.left) + _s(node.right)
def skew(node):
"""skew(node) = height(sağ) − height(sol)."""
return _h(node.right) - _h(node.left)
def _replace_child(parent, old, new):
"""parent'ın old çocuğunu new ile değiştir (new None olabilir)."""
if parent is not None:
if parent.left is old:
parent.left = new
else:
parent.right = new
if new is not None:
new.parent = parent
def right_rotate(y):
"""x = y.left yukarı, y aşağı; traversal korunur. O(1) + augmentation."""
x = y.left
_replace_child(y.parent, y, x)
b = x.right
y.left = b
if b is not None:
b.parent = y
x.right = y
y.parent = x
update_node(y)
update_node(x)
return x
def left_rotate(x):
"""Simetrik: y = x.right yukarı, x aşağı."""
y = x.right
_replace_child(x.parent, x, y)
b = y.left
x.right = b
if b is not None:
b.parent = x
y.left = x
x.parent = y
update_node(x)
update_node(y)
return y
def rebalance_node(x):
"""skew(x) = ±2 olan düğümü onar. Durum 3 = çift rotasyon (özel durum)."""
if skew(x) == 2:
y = x.right
if skew(y) < 0:
right_rotate(y)
return left_rotate(x)
if skew(x) == -2:
y = x.left
if skew(y) > 0:
left_rotate(y)
return right_rotate(x)
return x
def maintain_up(node):
"""Yaprak değişiminden köke: update + gerekirse rebalance. O(log n)."""
last = node
while node is not None:
update_node(node)
if abs(skew(node)) == 2:
node = rebalance_node(node)
last = node
node = node.parent
return last
def avl_insert(root, k):
"""Set-AVL insert: BST inişiyle yaprak ekle + ata yolunda maintain_up."""
new = AVLNode(k)
if root is None:
return new
node = root
while True:
if k < node.item:
if node.left is None:
node.left = new
new.parent = node
break
node = node.left
else:
if node.right is None:
node.right = new
new.parent = node
break
node = node.right
return maintain_up(new)
def build_avl(keys):
"""Anahtar listesinden (sırayla avl_insert) AVL kur — deterministik."""
root = None
for k in keys:
root = avl_insert(root, k)
return root
def avl_to_list(root):
"""In-order item listesi (doğrulama)."""
if root is None:
return []
return avl_to_list(root.left) + [root.item] + avl_to_list(root.right)
# ---------------------------------------------------------------------------
# _engine_QR1.py P1 — Criminal Seafood: çiftli bağlı liste + hash cross-link
# (Ku 1:06:04). add/remove/seat hepsi O(1).
# ---------------------------------------------------------------------------
class _DNode:
"""Çiftli bağlı liste düğümü (ortadan silerken iki komşu O(1) dikilir)."""
__slots__ = ("name", "prev", "next")
def __init__(self, name):
self.name = name
self.prev = None
self.next = None
class CrossLinkedWaitlist:
"""Sıra = çiftli bağlı liste C; isim araması = hash tablosu M (isim →
C'deki DÜĞÜME işaretçi — indeks DEĞİL: indeks kayar, düğüm kaymaz)."""
def __init__(self):
self.head = None
self.tail = None
self.index = {}
def __len__(self):
return len(self.index)
def add(self, name):
"""Müşteriyi sıranın SONUNA ekle + hash'e işaretçi koy. O(1)."""
node = _DNode(name)
if self.tail is None:
self.head = self.tail = node
else:
node.prev = self.tail
self.tail.next = node
self.tail = node
self.index[name] = node
def remove(self, name):
"""Sıradan ayrıl: hash'ten düğümü bul, iki komşuyu dik. O(1)."""
node = self.index.pop(name)
if node.prev is not None:
node.prev.next = node.next
else:
self.head = node.next
if node.next is not None:
node.next.prev = node.prev
else:
self.tail = node.prev
def seat(self):
"""Sıranın BAŞINDAKİNİ oturt (listeden + hash'ten çıkar). O(1)."""
node = self.head
self.head = node.next
if self.head is not None:
self.head.prev = None
else:
self.tail = None
del self.index[node.name]
return node.name
def to_list(self):
"""Doğrulama: baştan sona sıra (O(n))."""
out, cur = [], self.head
while cur is not None:
out.append(cur.name)
cur = cur.next
return out
# ---------------------------------------------------------------------------
# _engine_QR1.py P2 — Rainy Research: alt-ağaç-max + one-sided range query.
# ---------------------------------------------------------------------------
def build_time_tree(measurements):
"""Zaman-anahtarlı set AVL + her düğüme ALT-AĞAÇ MAX YAĞIŞ anotasyonu.
submax[node] = max(rain[node], sol.submax, sağ.submax) — subtree-property
(çocuklardan O(1)). Döndürür: (root, submax, rain)."""
rain = dict(measurements)
root = build_avl(sorted(rain.keys()))
submax = {}
def rec(node):
if node is None:
return 0
left = rec(node.left)
right = rec(node.right)
submax[id(node)] = max(rain[node.item], left, right)
return submax[id(node)]
rec(root)
return root, submax, rain
def peak_rainfall(root, submax, rain, t):
"""One-sided range query (Ku 1:24:47): t'den BÜYÜK-EŞİT zamanlardaki max
yağış, O(log n) — tek iniş yolu; her düğümde bir taraf TOPTAN halledilir.
İki durum (BST sıra garantisiyle):
v.time < t → v VE tüm SOL alt-ağaç (< v.time < t) aralık DIŞI → sağa in.
v.time ≥ t → tüm SAĞ alt-ağaç (> v.time ≥ t) aralık İÇİ → sağın
submax'ını O(1) OKU; belirsiz kalan SOLA in.
Döndürür: (değer, ziyaret_yolu)."""
path = []
def rec(v):
if v is None:
return 0
path.append(v.item)
if v.item < t: # v + tüm sol alt-ağaç aralık DIŞI
return rec(v.right)
# v aralıkta: SAĞ alt-ağacın tamamı da aralıkta → submax O(1) oku
right_max = submax[id(v.right)] if v.right is not None else 0
return max(rain[v.item], right_max, rec(v.left))
return rec(root), path
def brute_peak(rain, t):
"""Bağımsız tanık: max(r : time ≥ t), yoksa 0. O(n)."""
vals = [r for tm, r in rain.items() if tm >= t]
return max(vals) if vals else 0
```
## 1. Büyük Dört ve İki Çözüm Yolu {#sec-buyuk-dort}
Sınav, algoritma **icat etmeni** beklemez. Bir hesaplama problemini çözmenin iki yolu vardır:
1. **Sıfırdan tasarla** (zor yol): brute force veya böl-yönet gibi bir paradigmaya başvur. Bu, 6.046'nın işidir; 6.006'da nadiren istenir.
2. **Bilinen bir şeye indirge** (kolay yol, esas beklenen): derste öğretilen bir algoritmaya/arayüze **reduction**.
> *"reduce to a known thing — an algorithm that we've taught you."* — Ku, 5:25
Esas oyun: sana öğretilen sıralama ve sequence/set arayüzlerini **kara kutu** olarak kullanmak; mühendis olarak "ne zaman hangisini" seçeceğini söylemek. "Büyük dört" hedef bunun çerçevesidir: çöz, doğru olduğunu kanıtla, verimliliğini göster, **anlat** — son adım (iletişim) de puana dahildir.
## 2. Üç Problem Tipi: White-box / Black-box / Modification {#sec-uc-problem-tipi}
Ku, quiz problemlerini üç sınıfa ayırır:
> *"there's three different types of problems."* — Ku, 7:02
- **(a) İçyapı / white-box:** veri yapısının içini bilmen gerekir — bir AVL ağacında rotasyon nasıl yapılır, bir max-yığında en üst $k$ öğe nerede. Kara kutu **değil**; içine bakman şart.
- **(b) Reduction / black-box:** sadece API'yi bilmen yeter; çekirdek malzemeyi *uygula*. "Kütüphane import etmek" gibi — içine bakmazsın, sözleşmesine güvenirsin.
- **(c) Modification / augmentation:** hem API'yi hem içyapıyı bilmen gerekir — bir AVL'ye yeni bir özellik (augmentation) eklemek, dinamik diziyi ortadan büyütmek, böl-yönet'i uyarlamak. En zoru.
> *"Use as a black box... you import a library into your code... It's opaque to me."* — Ku, 6:17
Bir problemi bu üç tipten birine yerleştirebilmek, "ne kullanmalıyım?" sorusunu hızlandırır.
@fig-problem-types üç tipi yan yana koyar: kapağı açık kutu (white-box, içyapı görünür), kapalı/opak kutu + API fişi (black-box, amber vurgu — quiz'in esas beklediği), yarı açık kutu + anahtar (modification, hem API hem içyapı).
```{python}
#| label: fig-problem-types
#| fig-cap: "Quiz 1'in üç problem tipi (QR1 §2, İMZA figür): bir problemle karşılaşınca onu üç tipten birine yerleştir — tip, 'ne kullanmalıyım?' sorusunu hızlandırır (Ku 7:02). (a) WHITE-BOX / içyapı — kapağı AÇIK kutu, iç dişli görünür: yapının içini elle yürütmen gerekir (AVL rotasyonunu elle yürüt; yığında en üst k öğe nerede). Rozet: İÇİNE BAKMAN ŞART. (b) BLACK-BOX / reduction (AMBER çerçeve = quiz'in ESAS beklediği, Ku 6:17) — kapalı/opak kutu + API fişi: içine bakmadan yalnız sözleşmeye güvenirsin (problemi SIRALAMAYA indirge, kütüphaneyi import et). Rozet: SÖZLEŞMEYE GÜVEN. (c) MODIFICATION / augmentation (en zoru) — yarı açık kutu + anahtar: var olan yapıyı değiştirip yeni alan/davranış eklersin (AVL'ye yeni alan ekle; dinamik diziyi ORTADAN büyüt). Rozet: HEM API HEM İÇYAPI. Motor tanığı: CrossLinkedWaitlist black-box örneği — add(Ali,Bora,Can) → seat() = Ali → [Bora, Can], içine bakmadan sözleşme."
#| fig-width: 11.0
#| fig-height: 6.6
# fig-problem-types (QR1 §2): üç problem tipi kutu-ikonu metaforuyla.
# Motor tanığı: CrossLinkedWaitlist black-box sözleşmesi (içine bakmadan add/seat).
def _pt_type_panel(ax, x, y, w, h, *, ec, lw):
ax.add_patch(FancyBboxPatch(
(x, y), w, h, boxstyle="round,pad=0.04,rounding_size=0.14",
fc=COL_WHITE, ec=ec, linewidth=lw, zorder=2))
def _pt_badge(ax, cx, y, text, *, fc, ec, tcol):
bw, bh = 2.95, 0.50
ax.add_patch(FancyBboxPatch(
(cx - bw / 2, y), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.22",
fc=fc, ec=ec, linewidth=2.0, zorder=5))
ax.text(cx, y + bh * 0.5, text, ha="center", va="center",
fontsize=9.0, color=tcol, weight="bold", zorder=6)
def _pt_open_box(ax, cx, cy, *, s=0.60):
bx, by = cx - s, cy - s * 0.55
bw, bh = 2 * s, s * 1.15
ax.add_patch(Rectangle((bx, by), bw, bh, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=2.0, zorder=4))
lid = Polygon([(bx, by + bh), (bx + bw, by + bh),
(bx + bw - s * 0.5, by + bh + s * 0.65),
(bx - s * 0.5, by + bh + s * 0.65)],
closed=True, facecolor=COL_SLATE_400, edgecolor=COL_PRIMARY,
linewidth=1.8, alpha=0.85, zorder=5)
ax.add_patch(lid)
for gx, gr in ((cx - s * 0.42, s * 0.30), (cx + s * 0.40, s * 0.22)):
ax.add_patch(Circle((gx, cy - s * 0.02), gr, facecolor=COL_AMBER_300,
edgecolor=COL_AMBER_700, linewidth=1.6, zorder=6))
ax.add_patch(Circle((gx, cy - s * 0.02), gr * 0.38, facecolor=COL_WHITE,
edgecolor=COL_AMBER_700, linewidth=1.0, zorder=7))
ax.text(cx, by - s * 0.34, "kapak açık · iç dişli görünür",
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=6)
def _pt_closed_box(ax, cx, cy, *, s=0.60):
bx, by = cx - s, cy - s * 0.55
bw, bh = 2 * s, s * 1.15
ax.add_patch(FancyBboxPatch(
(bx, by), bw, bh, boxstyle="round,pad=0.01,rounding_size=0.06",
facecolor=COL_PRIMARY, edgecolor=COL_AMBER_700, linewidth=2.4, zorder=4))
ax.text(cx, cy, "API", ha="center", va="center", fontsize=11,
color=COL_WHITE, weight="bold", zorder=6)
plug_y = cy
ax.add_patch(Rectangle((bx - s * 0.55, plug_y - s * 0.10), s * 0.55, s * 0.20,
facecolor=COL_AMBER_600, edgecolor=COL_AMBER_700,
linewidth=1.4, zorder=5))
for dy in (-s * 0.05, s * 0.05):
ax.plot([bx - s * 0.80, bx - s * 0.55], [plug_y + dy, plug_y + dy],
color=COL_AMBER_700, linewidth=1.8, zorder=5,
solid_capstyle="round")
ax.text(cx, by - s * 0.34, "kapalı/opak · yalnız API fişi",
ha="center", va="center", fontsize=7.6, color=COL_AMBER_700,
style="italic", zorder=6)
def _pt_half_box(ax, cx, cy, *, s=0.60):
bx, by = cx - s, cy - s * 0.55
bw, bh = 2 * s, s * 1.15
ax.add_patch(Rectangle((bx, by), bw, bh, facecolor=COL_BG,
edgecolor=COL_PRIMARY, linewidth=2.0, zorder=4))
lid = Polygon([(bx, by + bh), (bx + bw, by + bh),
(bx + bw, by + bh + s * 0.50), (bx, by + bh)],
closed=True, facecolor=COL_SLATE_400, edgecolor=COL_PRIMARY,
linewidth=1.8, alpha=0.85, zorder=5)
ax.add_patch(lid)
ax.add_patch(Circle((cx + s * 0.10, cy), s * 0.26, facecolor=COL_AMBER_100,
edgecolor=COL_AMBER_700, linewidth=2.0, zorder=6))
ax.add_patch(Circle((cx + s * 0.10, cy), s * 0.10, facecolor=COL_WHITE,
edgecolor=COL_AMBER_700, linewidth=1.2, zorder=7))
ax.add_patch(Rectangle((cx + s * 0.10, cy - s * 0.055), s * 0.62, s * 0.11,
facecolor=COL_AMBER_600, edgecolor=COL_AMBER_700,
linewidth=1.2, zorder=6))
for tx in (cx + s * 0.58, cx + s * 0.72):
ax.add_patch(Rectangle((tx, cy + s * 0.05), s * 0.05, s * 0.10,
facecolor=COL_AMBER_600, edgecolor=COL_AMBER_700,
linewidth=0.8, zorder=6))
ax.text(bx + bw - s * 0.18, by + bh - s * 0.05, "+", ha="center",
va="center", fontsize=13, color=COL_AMBER_700, weight="bold",
zorder=8)
ax.text(cx, by - s * 0.34, "yarı açık · anahtarla genişlet",
ha="center", va="center", fontsize=7.6, color=COL_SLATE_500,
style="italic", zorder=6)
# --- motor tanığı: black-box (içine bakmadan add/seat sözleşmesi) ---
_pt_w = CrossLinkedWaitlist()
_pt_w.add("Ali")
_pt_w.add("Bora")
_pt_w.add("Can")
assert _pt_w.to_list() == ["Ali", "Bora", "Can"], _pt_w.to_list()
_pt_seated = _pt_w.seat()
assert _pt_seated == "Ali", _pt_seated
assert _pt_w.to_list() == ["Bora", "Can"], _pt_w.to_list()
fig, ax = plt.subplots(figsize=(11.0, 6.6))
fig.patch.set_facecolor(COL_WHITE)
panel_w, panel_h, gap = 3.05, 3.35, 0.55
xs = [0.0, panel_w + gap, 2 * (panel_w + gap)]
panel_y = 1.55
centers_x = [px + panel_w / 2 for px in xs]
_pt_type_panel(ax, xs[0], panel_y, panel_w, panel_h, ec=COL_PRIMARY, lw=2.2)
ax.text(centers_x[0], panel_y + panel_h - 0.34, "(a) WHITE-BOX",
ha="center", va="center", fontsize=12, color=COL_PRIMARY,
weight="bold", zorder=6)
ax.text(centers_x[0], panel_y + panel_h - 0.70, "içyapı", ha="center",
va="center", fontsize=9.5, color=COL_SLATE_500, style="italic", zorder=6)
_pt_open_box(ax, centers_x[0], panel_y + panel_h - 1.62, s=0.60)
ax.text(centers_x[0], panel_y + 0.92, "AVL rotasyonunu ELLE yürüt",
ha="center", va="center", fontsize=8.4, color=COL_TEXT, zorder=6)
ax.text(centers_x[0], panel_y + 0.60, "yığında en üst k öğe nerede?",
ha="center", va="center", fontsize=8.4, color=COL_TEXT, zorder=6)
_pt_badge(ax, centers_x[0], panel_y - 0.78, "İÇİNE BAKMAN ŞART",
fc=COL_BG, ec=COL_PRIMARY, tcol=COL_PRIMARY)
_pt_type_panel(ax, xs[1], panel_y, panel_w, panel_h, ec=COL_ACCENT, lw=3.2)
ax.text(centers_x[1], panel_y + panel_h - 0.34, "(b) BLACK-BOX",
ha="center", va="center", fontsize=12, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(centers_x[1], panel_y + panel_h - 0.70, "reduction (indirgeme)",
ha="center", va="center", fontsize=9.5, color=COL_AMBER_600,
style="italic", zorder=6)
_pt_closed_box(ax, centers_x[1], panel_y + panel_h - 1.62, s=0.60)
ax.text(centers_x[1], panel_y + 0.92, "SIRALAMAYA indirge",
ha="center", va="center", fontsize=8.4, color=COL_TEXT, zorder=6)
ax.text(centers_x[1], panel_y + 0.60, "kütüphaneyi import et",
ha="center", va="center", fontsize=8.4, color=COL_TEXT, zorder=6)
_pt_badge(ax, centers_x[1], panel_y - 0.78, "SÖZLEŞMEYE GÜVEN",
fc=COL_AMBER_100, ec=COL_ACCENT, tcol=COL_AMBER_700)
ax.text(centers_x[1], panel_y + panel_h + 0.32,
"★ quiz'in ESAS beklediği (Ku 6:17)", ha="center", va="center",
fontsize=8.6, color=COL_AMBER_700, weight="bold", zorder=7)
_pt_type_panel(ax, xs[2], panel_y, panel_w, panel_h, ec=COL_PRIMARY, lw=2.2)
ax.text(centers_x[2], panel_y + panel_h - 0.34, "(c) MODIFICATION",
ha="center", va="center", fontsize=12, color=COL_PRIMARY,
weight="bold", zorder=6)
ax.text(centers_x[2], panel_y + panel_h - 0.70, "augmentation (genişletme)",
ha="center", va="center", fontsize=9.5, color=COL_SLATE_500,
style="italic", zorder=6)
_pt_half_box(ax, centers_x[2], panel_y + panel_h - 1.62, s=0.60)
ax.text(centers_x[2], panel_y + 0.92, "AVL'ye yeni alan ekle",
ha="center", va="center", fontsize=8.4, color=COL_TEXT, zorder=6)
ax.text(centers_x[2], panel_y + 0.60, "dinamik diziyi ORTADAN büyüt",
ha="center", va="center", fontsize=8.4, color=COL_TEXT, zorder=6)
_pt_badge(ax, centers_x[2], panel_y - 0.78, "HEM API HEM İÇYAPI (en zoru)",
fc=COL_BG, ec=COL_AMBER_700, tcol=COL_AMBER_700)
strip_y = -0.20
strip_left = xs[0] - 0.10
strip_w = (xs[2] + panel_w) - strip_left + 0.10
ax.add_patch(FancyBboxPatch(
(strip_left, strip_y - 0.62), strip_w, 0.78,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_SLATE_400, linewidth=1.6, zorder=1))
ax.text(strip_left + strip_w * 0.5, strip_y - 0.05,
"bir problemi TİPİNE yerleştir → "
"\"ne kullanmalıyım?\" sorusunu hızlandırır (Ku 7:02)",
ha="center", va="center", fontsize=10.0, color=COL_AMBER_700,
weight="bold", zorder=4)
ax.text(strip_left + strip_w * 0.5, strip_y - 0.42,
"white-box = içini yürüt · black-box = sözleşmeye güven (indirge) · "
"modification = ikisini birden",
ha="center", va="center", fontsize=8.2, color=COL_SLATE_500,
style="italic", zorder=4)
fig.suptitle(
"Quiz 1: üç problem tipi — hangi soruyu bekliyorum, hangi araca uzanırım?",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.975)
ax.set_xlim(xs[0] - 0.35, xs[2] + panel_w + 0.35)
ax.set_ylim(strip_y - 0.95, panel_y + panel_h + 0.62)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
## 3. Reduction Disiplini: Önce Arayüz, Sonra Verimlilik {#sec-reduction-disiplini}
Kilit teknik: bir algoritma/veri yapısı yerine bir **probleme veya arayüze** indirge.
> *"a lot of times it's useful to reduce it to a problem or an interface rather than an algorithm or a data structure."* — Ku, 9:43
Neden? "Sıralamaya indirgedim" dersen **doğruluğu** hemen savunursun (sıralama kara kutusu doğru); *hangi* sıralama algoritması olduğu yalnızca **verimliliği** etkiler. Böylece correctness ile efficiency'yi ayırırsın (decouple).
> *"approach these things by solving these problems just in terms of the interfaces first."* — Ku, 28:14
Veri yapıları probleminde altın kural: **ne sakladığını ve neye anahtarlandığını (keyed on)** söyle, sonra **değişmezleri (invariants)** belirt. Doğruluk kanıtı, "işlemden önce değişmezler geçerliyse, işlemden sonra da geçerli kalır" tümevarımına dayanır.
> *"based on the assumption that those invariants held before my operation... I can prove that an operation is correct."* — Ku, 31:56
## 4. Sınav Stratejisi ve Kısmi Puan {#sec-sinav-stratejisi-d14}
- **Önce tüm sınavı oku**, sana en kolay gelenleri seç, güven sırasına göre çöz.
> *"read through the entire exam before you start."* — Ku, 11:27
- Ortalama genelde **60-80** arası; problemlerin %50'sini iyi yapmak, hepsini yarım yapmaktan iyidir.
- **Kısmi puan:** doğru ama verimsiz bir algoritma puan alır. Exponential ise %10-20 ile sınırlı; log/linear faktör kadar yavaşsa daha çok puan. Ama verimsiz algoritmayı *hedef* karmaşıklıkmış gibi analiz etmek **iki kat** hata.
- Çoklu-parça problemler **bağımsızdır**: A'yı çözmeden B çözülebilir.
- **Kod yazmazsın, kod okursun** (Python/pseudocode parçacıkları).
> *"If you're stuck, write down a correct algorithm that's inefficient."* — Ku, 19:23
## 5. Kaçınılacak Tuzaklar (Downsides) {#sec-tuzaklar}
Üç refleks "yanlış yoldasın" işaretidir:
1. **Ondalık / rasyonel / reel sayı hesabı.** Bu kurs yalnızca **tamsayı** öğretti. İki kesri karşılaştırman gerekiyorsa bölme yapma — **çapraz çarpım** ile $O(1)$'de karşılaştır.
2. **Her şeye Radix sort.** Yalnızca tamsayılar polinom-sınırlıysa ($u = n^c$) doğrusal olur. Sınır yoksa exponential olabilir; comparison gereken yerde merge sort ($n \log n$) kullan.
3. **Subtree-property olmayan augmentation.** Bir düğümün augmentation'ı, **iki çocuğunun augmentation'larından $O(1)$'de** hesaplanabilmelidir. "Tüm ağaçtaki indeksim" veya "sol alt-ağacımın boyutu" doğrudan tutulamaz (rotasyonda logaritmik yürüyüş gerekir); doğrusu **alt-ağaç boyutunu** tutup soldakini çocuğundan okumaktır.
> *"if you're trying to augment a binary tree with something that's not a subtree property... you're doing something bad."* — Ku, 24:32
Augmentation tanımlarken: formülü ver **ve** $O(1)$'de bakım yapıldığını göster.
> *"Max can be computed as the max between me and my left and right subtree."* — Ku, 27:49
## 6. Konu Tekrarı — Sıralama Algoritmaları {#sec-siralama-tekrari}
Neden bu kadar çok sıralama algoritması? Çünkü farklı senaryolar farklı algoritma ister.
> *"Why do we show you so many sorting algorithms?"* — Ku, 36:45
- **Insertion sort:** $k$-yakın dizide (öğeler en fazla $k$ uzak) $O(n \cdot k)$ — $k$ küçükse iyi; ama ikili yığınla $O(n \log k)$'ya inilir.
- **Selection sort:** okuma ucuz, **yazma pahalıysa** iyi (doğrusal sayıda swap).
- **Merge sort / AVL sort:** $O(n \log n)$, asimptotik olarak denk; genel amaçlı.
- **Heap sort:** **worst-case** $O(n \log n)$ ve **yerinde (in-place)**. Anahtar: diziyi bir **tam ikili ağaç (complete binary tree)** olarak görmek — dizi $\leftrightarrow$ ağaç birebir eşleşir (tamlık benzersizliği verir).
- **Radix sort:** tamsayılar polinom-sınırlıysa ($u = n^c$) **doğrusal**; hatta $u = n^c \cdot \log \log n$ gibi durumda merge sort'tan hızlı. Sınır yoksa kötü.
> *"this correspondence between arrays and binary trees."* — Ku, 40:17
## 7. Konu Tekrarı — Sequence Veri Yapıları {#sec-sequence-tekrari}
Üç temel: **bağlı liste (linked list)**, **dinamik dizi (dynamic array)**, **sequence AVL**.
- Derste sunulan **tekli bağlı liste (singly-linked)** — sonu bulmak/silmek $O(n)$.
- **Çiftli bağlı liste (doubly-linked):** önceki işaretçiyle, uçta ekleme/silme $O(1)$.
- Uçlarda (ön + arka) $O(1)$ için **üç** yol gösterildi: (1) çiftli bağlı liste, (2) sırt sırta iki dinamik dizi (double-ended queue), (3) **hash tablosu + en küçük indeksi saklama** (sequence'i set'le taklit etmek).
- **Sequence AVL:** ortaya $O(\log n)$ ekleme; pratikte nadir, ama teorik olarak dengeli sınırlar verir.
> *"I call this a linked data structure, because I'm linking between two data structures."* — Ku, 1:04:22
## 8. Konu Tekrarı — Set Veri Yapıları ve Öncelik Kuyruğu {#sec-set-pq-tekrari}
- **Sıralı dizi (sorted array):** iyi find (ikili arama), ama dinamik değil.
- **Set AVL:** iyi find + dinamik; $O(n \log n)$ build (özünde sıralama).
- **Hash tablosu / direct access array:** sözlük işlemleri (find/insert/delete) çok hızlı; ama **sıra (order)** işlemleri kötü.
- Teori sorusunda set AVL'yi **alt-ağaç max/min** ile zenginleştirirsen, sıralı diziden **her açıdan üstün** olur.
- **Öncelik kuyruğu (priority queue):** ikili yığın; *veya* max/min augmentation'lı sequence AVL (amortizasyonsuz aynı sınırlar).
> *"augment by the max... I can make this one strictly better than this one."* — Ku, 53:38
## Bu Quiz Review'in Özeti {#sec-ozet-d14}
1. **Quiz = veri yapıları + sıralama bloğu** (Ders 1-12); "büyük dört": çöz, kanıtla, verimli yap, anlat.
2. **İki yol**: sıfırdan tasarla (zor) vs **bilinen kara kutuya indirge** (esas beklenen).
3. **Üç problem tipi**: white-box (içyapı) / black-box (reduction) / modification (augmentation).
4. **Reduction disiplini**: önce arayüz (correctness), sonra implementasyon (efficiency); ne sakladığını + neye anahtarlandığını + değişmezleri söyle.
5. **Strateji**: tüm sınavı oku, kolayı seç; sıkışınca doğru-ama-verimsiz yaz.
6. **Tuzaklar**: rasyonel hesabı (çapraz çarp), her şeye radix, subtree-property olmayan augmentation.
7. **Tablolar**: sorting (heap/radix özel), sequence (doubly-linked $O(1)$ uç), set (augmented AVL $\supset$ sorted array).
::: {.callout-important title="Tek Bir Cümle"}
Quiz 1, icat değil **seçim** sınavıdır: doğru kara kutuyu seç, neye indirgediğini ve neyi sakladığını açıkça yaz, correctness'i invariant'larla kanıtla, sonra verimliliği optimize et.
:::
## Quiz-tarzı Problemler {#sec-quiz-problemleri-d14}
Aşağıda dört quiz-tarzı problem var; her birinin çözümünü açmadan önce kendin dene. İlk ikisi motorla doğrulanmıştır (gerçek sınav problemleri); son ikisi mekanik kontrol soruları.
@fig-crosslink-seafood Problem 1'in iki bileşenli yapısını gösterir: çiftli bağlı liste C (sıra) + hash tablosu M (isim → düğüm işaretçisi); `remove` ve `seat` her ikisi de $O(1)$.
```{python}
#| label: fig-crosslink-seafood
#| fig-cap: "Criminal Seafood (QR1 Problem 1, Ku 1:06:04): çiftli bağlı liste + hash cross-link → add / remove / seat hepsi O(1). İki bileşen: C = çiftli bağlı liste (sıra ali ↔ banu ↔ cem ↔ didem, her düğüm prev+next), M = hash tablosu (isim → C'deki DÜĞÜME işaretçi — İNDEKS DEĞİL DÜĞÜM: indeks kayar, düğüm kaymaz). Cross-link neden düğüm işaretçisi: bir müşteri ortadan ayrılınca önündeki herkesin indeksi azalır (indeks saklamak O(n) güncelleme); düğüm işaretçisiyle silme O(1) (hash'ten düğümü bul, iki komşuyu dik). Zaman çizgisi MOTORDAN: add ali,banu,cem,didem → [ali,banu,cem,didem]; remove(banu) → ali↔cem dikilir → [ali,cem,didem]; seat() = ali (baş) → [cem,didem]. Tüm işlemler O(1) (hash beklenen, liste worst-case)."
#| fig-width: 11.0
#| fig-height: 7.0
# fig-crosslink-seafood (QR1 P1): çiftli liste + hash cross-link, motordan.
def _cl_list_node(ax, x, y, w, h, name, *, faded=False):
if faded:
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.4
else:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.9
ax.add_patch(FancyBboxPatch(
(x - w * 0.5, y - h * 0.5), w, h,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=lw, zorder=4, alpha=0.45 if faded else 1.0))
ax.text(x, y, name, ha="center", va="center", fontsize=11.5,
color=tcol, weight="bold", zorder=6, alpha=0.5 if faded else 1.0)
return (x, y), (x - w * 0.5, y), (x + w * 0.5, y)
def _cl_double_arrow(ax, p0, p1, *, color, lw, z=3, gap=0.06, alpha=1.0):
ax.add_patch(FancyArrowPatch(
(p0[0] + gap, p0[1]), (p1[0] - gap, p1[1]),
arrowstyle="<|-|>", mutation_scale=12, color=color,
linewidth=lw, zorder=z, alpha=alpha, shrinkA=0, shrinkB=0))
# --- motor verisi (figür yalnız bunu çizer) ---
_cl_wl = CrossLinkedWaitlist()
for _nm in ("ali", "banu", "cem", "didem"):
_cl_wl.add(_nm)
_cl_start = _cl_wl.to_list()
assert _cl_start == ["ali", "banu", "cem", "didem"], _cl_start
_cl_wl.remove("banu")
assert _cl_wl.to_list() == ["ali", "cem", "didem"], _cl_wl.to_list()
_cl_seated = _cl_wl.seat()
assert _cl_seated == "ali", _cl_seated
_cl_after_seat = _cl_wl.to_list()
assert _cl_after_seat == ["cem", "didem"], _cl_after_seat
fig, ax = plt.subplots(figsize=(11.0, 7.0))
fig.patch.set_facecolor(COL_WHITE)
names = list(_cl_start)
node_w, node_h = 1.55, 0.78
list_y = 5.35
xs = [1.4, 3.7, 6.0, 8.3]
node_xy, node_left, node_right = {}, {}, {}
for nm, x in zip(names, xs):
faded = (nm == "banu")
c, lft, rgt = _cl_list_node(ax, x, list_y, node_w, node_h, nm, faded=faded)
node_xy[nm], node_left[nm], node_right[nm] = c, lft, rgt
for i in range(len(names) - 1):
a, b = names[i], names[i + 1]
faded = (a == "banu" or b == "banu")
_cl_double_arrow(ax, node_right[a], node_left[b],
color=COL_SLATE_400 if faded else COL_PRIMARY,
lw=1.4 if faded else 2.0, alpha=0.4 if faded else 1.0)
ax.text((xs[0] + xs[1]) * 0.5, list_y + node_h * 0.5 + 0.30, "prev ↔ next",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=6)
hx, hy = node_xy["ali"]
ax.text(hx, list_y + node_h * 0.5 + 0.62, "head (sıranın önü)", ha="center",
va="center", fontsize=9.0, color=COL_AMBER_700, weight="bold", zorder=7)
ax.add_patch(FancyArrowPatch(
(hx, list_y + node_h * 0.5 + 0.48), (hx, list_y + node_h * 0.5 + 0.06),
arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700, linewidth=1.8, zorder=7))
tx, ty = node_xy["didem"]
ax.text(tx, list_y + node_h * 0.5 + 0.62, "tail (yeni gelen)", ha="center",
va="center", fontsize=9.0, color=COL_AMBER_700, weight="bold", zorder=7)
ax.add_patch(FancyArrowPatch(
(tx, list_y + node_h * 0.5 + 0.48), (tx, list_y + node_h * 0.5 + 0.06),
arrowstyle="-|>", mutation_scale=12, color=COL_AMBER_700, linewidth=1.8, zorder=7))
ax.text(-0.05, list_y + node_h * 0.5 + 0.95, "C · çiftli bağlı liste (sıra)",
ha="left", va="center", fontsize=11.0, color=COL_TEXT, weight="bold", zorder=7)
hash_x, hash_w = 0.0, 2.55
row_h = 0.66
rows = list(names)
hash_top = 3.35
hash_h = row_h * len(rows) + 0.34
hash_bottom = hash_top - hash_h
ax.add_patch(FancyBboxPatch(
(hash_x, hash_bottom), hash_w, hash_h,
boxstyle="round,pad=0.02,rounding_size=0.10",
fc=COL_BG, ec=COL_PRIMARY, linewidth=2.0, zorder=2))
ax.text(hash_x + hash_w * 0.5, hash_top + 0.20, "M · hash tablosu", ha="center",
va="bottom", fontsize=11.0, color=COL_TEXT, weight="bold", zorder=6)
hash_row_y = {}
for r, nm in enumerate(rows):
ry = hash_top - 0.17 - (r + 0.5) * row_h
hash_row_y[nm] = ry
faded = (nm == "banu")
rcol = COL_SLATE_400 if faded else COL_TEXT
ax.text(hash_x + 0.26, ry, nm, ha="left", va="center", fontsize=10.0,
color=rcol, weight="bold", zorder=6, alpha=0.5 if faded else 1.0)
ax.text(hash_x + 1.18, ry, "→", ha="center", va="center", fontsize=10,
color=COL_SLATE_500, zorder=6, alpha=0.5 if faded else 1.0)
ax.text(hash_x + hash_w - 0.22, ry, "•düğüm", ha="right", va="center",
fontsize=9.0, color=COL_AMBER_700 if not faded else COL_SLATE_400,
weight="bold", zorder=6, family="monospace", alpha=0.5 if faded else 1.0)
ax.text(hash_x + hash_w * 0.5, hash_bottom - 0.26, "isim → C'deki DÜĞÜME işaretçi",
ha="center", va="center", fontsize=8.0, color=COL_SLATE_500,
style="italic", zorder=6)
for nm in rows:
ry = hash_row_y[nm]
nx, ny = node_xy[nm]
faded = (nm == "banu")
ax.add_patch(FancyArrowPatch(
(hash_x + hash_w + 0.02, ry), (nx, ny - node_h * 0.5 - 0.02),
arrowstyle="-|>", mutation_scale=10,
color=COL_SLATE_400 if faded else COL_AMBER_600,
linewidth=1.0 if faded else 1.4, linestyle=(0, (3, 2)), zorder=1,
alpha=0.4 if faded else 0.95, connectionstyle="arc3,rad=-0.12"))
ax.add_patch(FancyBboxPatch(
(3.05, 1.78), 3.85, 0.92, boxstyle="round,pad=0.04,rounding_size=0.08",
fc=COL_WHITE, ec=COL_AMBER_300, linewidth=1.2, zorder=5, alpha=0.95))
ax.text(4.97, 2.45, "cross-link: hash → DÜĞÜM işaretçisi (indeks DEĞİL)",
ha="center", va="center", fontsize=8.6, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(4.97, 2.05,
"indeks kayar (silmede O(n) güncelleme) · düğüm kaymaz → silme O(1)\n"
"(Ku 1:06:04)", ha="center", va="center", fontsize=7.9,
color=COL_SLATE_500, style="italic", zorder=6, linespacing=1.25)
tl_x = 9.55
tl_y0, tl_y1 = 0.55, 5.85
ax.plot([tl_x, tl_x], [tl_y0, tl_y1], color=COL_SLATE_400, linewidth=1.6, zorder=1)
ax.text(tl_x, tl_y1 + 0.22, "işlemler", ha="center", va="bottom", fontsize=10.0,
color=COL_TEXT, weight="bold", zorder=6)
def _cl_tl_event(cy, title, body, badge, *, accent=True):
col = COL_AMBER_700 if accent else COL_PRIMARY
ax.add_patch(Circle((tl_x, cy), 0.08, facecolor=col, edgecolor=COL_WHITE,
linewidth=1.3, zorder=4))
ax.text(tl_x + 0.22, cy, title, ha="left", va="center", fontsize=9.8,
color=col, weight="bold", zorder=5)
ax.text(tl_x + 0.22, cy - 0.40, body, ha="left", va="center", fontsize=8.2,
color=COL_TEXT, zorder=5, linespacing=1.2)
ax.add_patch(FancyBboxPatch(
(tl_x + 0.22, cy - 1.02), 1.18, 0.34,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=1.6, zorder=4))
ax.text(tl_x + 0.81, cy - 0.85, badge, ha="center", va="center",
fontsize=8.4, color=COL_AMBER_700, weight="bold", zorder=5)
_cl_tl_event(4.85, "① remove(banu)",
"hash'ten düğümü bul → iki\nkomşuyu dik (ali.next↔cem.prev)", "O(1)")
_cl_tl_event(2.85, "② seat()", "baştaki (ali) oturur →\nhead ileri kayar", "O(1)")
_cl_tl_event(1.05, "sonuç", "[%s]" % ", ".join(_cl_after_seat), "hepsi O(1)")
for y0, y1 in ((4.55, 3.35), (2.55, 1.35)):
ax.add_patch(FancyArrowPatch(
(tl_x, y0), (tl_x, y1), arrowstyle="-|>", mutation_scale=12,
color=COL_SLATE_400, linewidth=1.4, zorder=2))
al_r = node_right["ali"]
ce_l = node_left["cem"]
mid_x = (al_r[0] + ce_l[0]) * 0.5
relink_y = list_y - node_h * 0.5 - 0.42
ax.add_patch(FancyArrowPatch(
(al_r[0], al_r[1] - node_h * 0.5 + 0.04),
(ce_l[0], ce_l[1] - node_h * 0.5 + 0.04),
arrowstyle="<|-|>", mutation_scale=11, color=COL_ACCENT,
linewidth=2.4, zorder=5, connectionstyle="arc3,rad=-0.55"))
ax.text(mid_x, relink_y - 0.30, "remove(banu): ali ↔ cem yeni dikiş (O(1))",
ha="center", va="center", fontsize=8.2, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.add_patch(FancyArrowPatch(
(node_xy["ali"][0] - node_w * 0.5 + 0.05, list_y - node_h * 0.5 - 0.02),
(node_xy["ali"][0] - 1.18, list_y - node_h * 0.5 - 0.55),
arrowstyle="-|>", mutation_scale=14, color=COL_ACCENT,
linewidth=2.2, zorder=6, connectionstyle="arc3,rad=0.30"))
ax.text(node_xy["ali"][0] - 1.28, list_y - node_h * 0.5 - 0.78,
"seat(): ali\noturur (çıkar)", ha="center", va="top", fontsize=8.2,
color=COL_AMBER_700, weight="bold", zorder=6, linespacing=1.2)
fig.suptitle(
"Criminal Seafood: çiftli bağlı liste + hash cross-link → "
"add / remove / seat hepsi O(1)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ax.plot([0.95, 9.0], [3.95, 3.95], color=COL_SLATE_400, linewidth=1.0,
linestyle=(0, (3, 3)), zorder=0)
ax.text(4.35, 0.30,
"remove: hash O(1) bulur · iki komşu O(1) dikilir (çiftli liste şart) · "
"indeks değil DÜĞÜM saklandığı için kayma yok",
ha="center", va="center", fontsize=8.5, color=COL_SLATE_500,
style="italic", zorder=6)
ax.set_xlim(-0.6, 11.3)
ax.set_ylim(0.0, 6.95)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-note collapse="true" title="Problem 1 (Criminal Seafood — bekleme listesi): build/add/remove/seat işlemlerinin hepsi O(1). Hangi veri yapıları?"}
**Çözüm.**
İki ihtiyaç var: (i) **sıra (extrinsic order)** — önce gelen önce oturur; (ii) **isimle arama** — bir müşteriyi adından bul. Bu, "iki anahtarlı" bir problem → iki veri yapısı + **cross-linking**.
- **Sequence:** **çiftli bağlı liste (doubly-linked list)** C — müşterileri sırada tutar. (Çiftli, çünkü ortadan silerken iki komşuyu $O(1)$'de dikmek gerekir.)
- **Set:** **hash tablosu** M — ismi, o müşterinin C'deki **düğümüne işaretçisine** eşler.
Kritik incelik: indeks değil **işaretçi** sakla. İndeks saklarsan, biri oturunca tüm indeksler kayar ve M'yi baştan güncellemen gerekir ($O(n)$); düğüm işaretçisi ise öğe çıkana dek değişmez.
> *"store a pointer... to the node... because the node isn't changing."* — Ku, 1:06:04
İşlemler: **add x** → x'i C'nin sonuna ekle (düğüm v), M'ye x → v koy. **remove x** → M'den v'yi bul, C'den v'yi çıkar (çiftli bağlantıyla dik), M'den sil. **seat** → C'nin başını sil, o müşterinin adını M'den çıkar. Hepsi $O(1)$ (hash beklenen, liste worst-case).
**Karmaşıklık.** Tüm işlemler $O(1)$ (hash işlemleri *beklenen*; liste işlemleri *worst-case*).
:::
@fig-onesided-range Problem 2'nin imza fikrini gösterir: alt-ağaç-max ile zenginleştirilmiş zaman-AVL'de tek taraflı aralık sorgusu — her düğümde bir taraf toptan halledilir, tek iniş yolu $O(\log n)$.
```{python}
#| label: fig-onesided-range
#| fig-cap: "Tek taraflı aralık sorgusu (QR1 Problem 2, İMZA figür, Ku 1:24:47): alt-ağaç-max zenginleştirme → peak_rainfall O(log n). Zaman-anahtarlı AVL (5 düğüm): kök 20, çocukları 10 ve 40, 40'ın çocukları 30 ve 50; her düğümde zaman + yağış r + amber submax kutusu (alt-ağaç max, MOTORDAN). Sorgu t=25 ('t'den beri en yüksek yağış', zaman ≥ 25). İmza fikir: her düğümde aralığın BİR tarafı TOPTAN halledilir → tek iniş yolu. 20 < 25 → SOL alt-ağaç (10) TOPTAN DIŞARI (soluk + X), sağa in; 40 ≥ 25 → SAĞ alt-ağaç (50) TOPTAN İÇERİDE → submax(50) O(1) OKU (inilmez), sola in; 30 ≥ 25 → r=1 al, dur. Sonuç MOTORDAN: peak = max(r(30)=1, submax(50)=2, r(40)=7) = 7 = brute tanığı; yol = [20, 40, 30]. Her seviyede yalnız BİR çocuğa inilir → O(log n)."
#| fig-width: 10.5
#| fig-height: 7.0
# fig-onesided-range (QR1 P2 İMZA): alt-ağaç-max + one-sided range query, motordan.
_OR_POS = {20: (3.6, 4.2), 10: (1.2, 2.6), 40: (6.0, 2.6),
30: (4.7, 1.0), 50: (7.3, 1.0)}
_OR_TREE_EDGES = [(20, 10), (20, 40), (40, 30), (40, 50)]
_OR_R = 0.50
def _or_node_circle(ax, t, rain, *, state="normal"):
x, y = _OR_POS[t]
if state == "path":
fc, ec, tcol, lw = COL_AMBER_100, COL_ACCENT, COL_AMBER_700, 3.2
elif state == "discarded":
fc, ec, tcol, lw = COL_WHITE, COL_SLATE_400, COL_SLATE_400, 1.4
else:
fc, ec, tcol, lw = COL_BG, COL_PRIMARY, COL_TEXT, 1.8
ax.add_patch(Circle((x, y), _OR_R, facecolor=fc, edgecolor=ec,
linewidth=lw, zorder=5))
ax.text(x, y + 0.10, f"{t}", ha="center", va="center", fontsize=14,
color=tcol, weight="bold", zorder=6)
ax.text(x, y - 0.24, f"r={rain}", ha="center", va="center", fontsize=8,
color=COL_SLATE_500, zorder=6, style="italic")
if state == "discarded":
d = _OR_R * 0.66
ax.plot([x - d, x + d], [y - d, y + d], color=COL_SLATE_500,
linewidth=2.2, zorder=7, alpha=0.85, solid_capstyle="round")
ax.plot([x - d, x + d], [y + d, y - d], color=COL_SLATE_500,
linewidth=2.2, zorder=7, alpha=0.85, solid_capstyle="round")
return x, y
def _or_submax_badge(ax, t, value, *, read=False):
x, y = _OR_POS[t]
bx, by, bw, bh = x + _OR_R + 0.12, y + 0.02, 1.12, 0.46
if read:
fc, ec, lw = COL_AMBER_300, COL_AMBER_700, 2.4
else:
fc, ec, lw = COL_AMBER_100, COL_AMBER_600, 1.4
ax.add_patch(FancyBboxPatch(
(bx, by - bh * 0.5), bw, bh, boxstyle="round,pad=0.02,rounding_size=0.06",
fc=fc, ec=ec, linewidth=lw, zorder=4))
ax.text(bx + bw * 0.5, by, f"submax={value}", ha="center", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
if read:
ax.text(bx + bw * 0.5, by - bh * 0.5 - 0.18, "O(1) oku", ha="center",
va="center", fontsize=7.5, color=COL_AMBER_700, weight="bold",
style="italic", zorder=6)
# --- motor verisi (figür yalnız bunu çizer) ---
_or_root, _or_submax, _or_rain = build_time_tree({10: 3, 20: 9, 30: 1, 40: 7, 50: 2})
_or_t = 25
_or_got, _or_path = peak_rainfall(_or_root, _or_submax, _or_rain, _or_t)
_or_brute = brute_peak(_or_rain, _or_t)
assert _or_got == 7 == _or_brute, (_or_got, _or_brute)
assert _or_path == [20, 40, 30], _or_path
assert _or_root.item == 20 and _or_root.left.item == 10 and _or_root.right.item == 40
assert _or_root.right.left.item == 30 and _or_root.right.right.item == 50
_or_sm = {}
def _or_collect(node):
if node is None:
return
_or_sm[node.item] = _or_submax[id(node)]
_or_collect(node.left)
_or_collect(node.right)
_or_collect(_or_root)
assert _or_sm[50] == 2 and _or_sm[20] == 9, _or_sm
_or_path_set = set(_or_path)
fig, ax = plt.subplots(figsize=(10.5, 7.0))
fig.patch.set_facecolor(COL_WHITE)
_or_path_edges = {frozenset((_or_path[i], _or_path[i + 1]))
for i in range(len(_or_path) - 1)}
for parent, child in _OR_TREE_EDGES:
px, py = _OR_POS[parent]
cx, cy = _OR_POS[child]
e_key = frozenset((parent, child))
if e_key in _or_path_edges:
col, lw, z, al = COL_ACCENT, 3.4, 4, 1.0
elif child not in _or_path_set and child in (10, 50):
col, lw, z, al = COL_SLATE_400, 1.5, 2, 0.55
else:
col, lw, z, al = COL_SLATE_400, 1.8, 2, 0.85
ax.plot([px, cx], [py, cy], color=col, linewidth=lw, zorder=z,
alpha=al, solid_capstyle="round")
_or_node_state = {20: "path", 40: "path", 30: "path",
10: "discarded", 50: "normal"}
for tk in (10, 50, 30, 40, 20):
_or_node_circle(ax, tk, _or_rain[tk], state=_or_node_state[tk])
_or_submax_badge(ax, 50, _or_sm[50], read=True)
_or_submax_badge(ax, 10, _or_sm[10], read=False)
_or_submax_badge(ax, 30, _or_sm[30], read=False)
_or_submax_badge(ax, 40, _or_sm[40], read=False)
kx, ky = _OR_POS[20]
ax.add_patch(FancyBboxPatch(
(kx - _OR_R - 1.24, ky - 0.23), 1.12, 0.46,
boxstyle="round,pad=0.02,rounding_size=0.06",
fc=COL_AMBER_100, ec=COL_AMBER_600, linewidth=1.4, zorder=4))
ax.text(kx - _OR_R - 0.68, ky, f"submax={_or_sm[20]}", ha="center", va="center",
fontsize=8, color=COL_AMBER_700, weight="bold", zorder=6)
xs = [p[0] for p in _OR_POS.values()]
th_x_left = min(xs) - 1.55
th_x_right = max(xs) + 1.55
th_y = 3.45
ax.plot([th_x_left, th_x_right], [th_y, th_y], color=COL_AMBER_700,
linewidth=1.6, linestyle=(0, (5, 3)), zorder=1, alpha=0.7)
ax.text(th_x_left + 0.05, th_y + 0.16, "sorgu eşiği t = 25", ha="left",
va="bottom", fontsize=10, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(th_x_right - 0.05, th_y - 0.18,
"“t = 25'ten beri en yüksek yağış?” (zaman ≥ 25)",
ha="right", va="top", fontsize=8.3, color=COL_SLATE_500,
style="italic", zorder=6)
ax.text(kx + 0.62, ky + 0.30,
"20 < 25\n→ sol alt-ağaç (10) TOPTAN DIŞARI\n→ sağa in",
ha="left", va="center", fontsize=7.8, color=COL_AMBER_700,
weight="bold", zorder=7, linespacing=1.25)
fx, fy = _OR_POS[40]
ax.text(fx - 0.62, fy + 0.62,
"40 ≥ 25\n→ sağ alt-ağaç (50) TOPTAN İÇERİDE\n→ submax O(1) oku, sola in",
ha="right", va="bottom", fontsize=7.8, color=COL_AMBER_700,
weight="bold", zorder=7, linespacing=1.25)
tx2, ty2 = _OR_POS[30]
ax.text(tx2 - 0.10, ty2 - _OR_R - 0.20, "30 ≥ 25\n→ yağış r=1 al · dur",
ha="center", va="top", fontsize=7.8, color=COL_AMBER_700,
weight="bold", zorder=7, linespacing=1.25)
dx, dy = _OR_POS[10]
ax.text(dx, dy - _OR_R - 0.24, "tüm zamanları < 25\nbakılmaz", ha="center",
va="top", fontsize=7.5, color=COL_SLATE_500, style="italic",
zorder=6, linespacing=1.2)
res_x, res_y, res_w, res_h = 7.75, 4.55, 2.75, 1.65
ax.add_patch(FancyBboxPatch(
(res_x, res_y), res_w, res_h, boxstyle="round,pad=0.04,rounding_size=0.12",
fc=COL_AMBER_100, ec=COL_ACCENT, linewidth=3.0, zorder=3))
ax.text(res_x + res_w * 0.5, res_y + res_h - 0.20, "sonuç", ha="center",
va="center", fontsize=9.5, color=COL_AMBER_700, weight="bold", zorder=6)
ax.text(res_x + res_w * 0.5, res_y + res_h * 0.56, f"peak = {_or_got}",
ha="center", va="center", fontsize=22, color=COL_AMBER_700,
weight="bold", zorder=6)
ax.text(res_x + res_w * 0.5, res_y + 0.26,
f"max( r(30)=1, submax(50)={_or_sm[50]}, r(40)={_or_rain[40]} ) = {_or_got}",
ha="center", va="center", fontsize=8.0, color=COL_TEXT, zorder=6)
fig.suptitle(
"Tek taraflı aralık sorgusu: alt-ağaç-max zenginleştirme → "
"peak_rainfall O(log n)",
color=COL_TEXT, fontsize=12.5, weight="bold", y=0.985)
ymin = min(p[1] for p in _OR_POS.values())
note_y = ymin - _OR_R - 1.05
ax.add_patch(FancyBboxPatch(
(th_x_left, note_y - 0.50), th_x_right - th_x_left, 0.92,
boxstyle="round,pad=0.03,rounding_size=0.10",
fc=COL_BG, ec=COL_ACCENT, linewidth=2.2, zorder=2))
ax.text((th_x_left + th_x_right) * 0.5, note_y + 0.16,
"Her düğümde aralığın BİR tarafı TOPTAN halledilir: ya atılır "
"(sol < t) ya da submax O(1) okunur (sağ ≥ t)",
ha="center", va="center", fontsize=8.8, color=COL_AMBER_700,
weight="bold", zorder=5)
ax.text((th_x_left + th_x_right) * 0.5, note_y - 0.22,
"→ her seviyede yalnız BİR çocuğa inilir → tek iniş yolu → O(log n) "
"(yol: 20 → 40 → 30, brute tanığı = %d)" % _or_brute,
ha="center", va="center", fontsize=8.3, color=COL_SLATE_500,
style="italic", zorder=5)
ax.set_xlim(th_x_left - 0.35, th_x_right + 0.35)
ax.set_ylim(note_y - 0.75, ky + _OR_R + 1.0)
ax.set_aspect("equal")
ax.axis("off")
plt.tight_layout()
plt.show()
```
::: {.callout-note collapse="true" title="Problem 2 (Rainy Research — peak rainfall): record_data O(1)-benzeri ve peak_rainfall(l, t) worst-case O(log n). t zamanından beri l enlemindeki en yüksek yağış."}
**Çözüm.**
Ölçümler (r yağış, l enlem, t zaman) üçlüsü; hepsi tamsayı, sınırsız → enlemin "küçük" olduğunu varsayma. Worst-case istendiği için **hash değil set AVL**.
- **Dış yapı:** enlem-anahtarlı **set AVL** L — her enlem l'yi bir "zaman veri yapısına" T(l) eşler.
- **İç yapı:** her T(l), **zaman-anahtarlı set AVL** — zamanı yağışa eşler.
- **Augmentation:** her düğümde **alt-ağaçtaki maksimum yağış** (alt-ağaç max r). Bu bir subtree-property'dir: düğüm = max(kendi r, sol alt-ağaç max, sağ alt-ağaç max), $O(1)$'de bakım.
**One-sided range query** (tek-taraflı aralık sorgusu): "$t$'den büyük-eşit tüm zamanlardaki max yağış"ı $O(\log n)$'de bul. Özyinelemeli, düğüm $v$'de iki durum:
```python
def peak(v, t): # v koku, t alt sinir
if v is None:
return 0
if v.time < t: # v + tum SOL alt-agac (< v.time < t) araligin DISINDA
return peak(v.right, t)
else: # v araliginda: SAG alt-agacin tamami da araliginda
return max(v.r,
v.right.submax if v.right else 0, # O(1): sag submax OKU
peak(v.left, t)) # belirsiz SOLA in
```
*[motor notu]* — Kaynak sayfadaki pseudocode'un yönleri ters yazılmıştı (sol submax okuyup sağa iniyordu); bu, sol alt-ağaçtaki $t$'den küçük zamanları yanlışlıkla dahil eder. Bağımsız brute-force tanığı farkı doğruladı: ters yön 1000 sorgudan 193'ünde yanlış değer verdi, doğru yön ($v.\text{right}.\text{submax}$ oku + $\text{peak}(v.\text{left})$) 1000/1000 brute ile eşleşti. Statement ("$t$'den beri max") bağlayıcı; yukarıdaki kod doğru yönü uygular.
Püf nokta: aralık içindeyken **sağ alt-ağaca inmek yerine** onun augmented max'ını $O(1)$'de oku; yalnızca sola tek bir özyinelemeli iniş yap → ağaç boyunca tek yol → $O(\log n)$.
> *"that's what we call a one-sided range query."* — Ku, 1:24:47
**Karmaşıklık.** record_data $O(\log n)$ (iki AVL'ye ekleme); peak_rainfall **worst-case $O(\log n)$**.
:::
::: {.callout-note collapse="true" title="Problem 3 (mekanik — geçerli augmentation): Bir set AVL'yi 'sol alt-ağacımdaki düğüm sayısı' ile zenginleştirmek geçerli mi?"}
**Cevap:**
Doğrudan **hayır** — ama dolaylı **evet**. "Sol alt-ağaç boyutu", rotasyon/güncellemede iki çocuğun augmentation'ından $O(1)$'de türetilemez (logaritmik yürüyüş gerekir), yani tek başına bir subtree-property değildir. Doğru yol: her düğümde **kendi alt-ağaç boyutunu** (`size = 1 + sol_size + sağ_size`, $O(1)$ bakım) tut; "sol alt-ağaç boyutu" gerektiğinde sol çocuğun size'ından **okunur**. Genel kural: depolanan augmentation daima bir subtree-property olmalı; türev bilgiler ondan $O(1)$'de hesaplanır.
> *"just augment the thing itself and just look at your left subtree and look at its augmentation."* — Ku, 25:42
Bu `size` augmentation'ı, **rank sorgusu** (k. en küçük, tek-taraflı aralık) verir — sequence AVL'nin `subtree_at`'inin set karşılığı.
:::
::: {.callout-note collapse="true" title="Problem 4 (mekanik — worst case vs expected): Bir hash tablosunda O(1) beklenen arama yapıp ardından bir AVL'de O(log n) predecessor sorgusu yapıyorum. Bu zincirin worst-case ve beklenen süresi?"}
**Cevap:**
- **Worst-case: $O(n)$.** Hash tablosunun worst-case araması $O(n)$'dir (tüm anahtarlar aynı kovaya düşebilir); AVL $O(\log n)$. Toplam worst-case $O(n + \log n) = O(n)$.
- **Beklenen: $O(\log n)$.** Hash beklenen $O(1)$ + AVL $O(\log n) = O(\log n)$.
Ders: "beklenen" ve "worst-case" farklı sözleşmelerdir. Sınav "worst-case istiyorum" derse hash tablosu kullanma (set AVL'ye geç); "expected/amortized serbest" derse hangi sınıfı elde ettiğini **etiketle**.
> *"It's possible that in the worst case it could be higher."* — Ku, 30:15
:::
## Quiz Hazırlığı Egzersizleri {#sec-quiz-hazirligi-d14}
**Egzersiz 1.** Sıralama tablosunu boş bir kâğıda ezberden doldur: her algoritma için worst-case süre, kararlı mı (stable), yerinde mi (in-place), hangi özel durumda tercih edilir.
**Egzersiz 2.** Sequence, set ve priority queue arayüzlerinin işlem-süre tablolarını ezberden çıkar; her hücreyi "hangi implementasyon bunu verir?" ile eşle.
**Egzersiz 3.** Üç master-teoremi durumunu üç farklı özyinelemeye uygula (örn. $T(n) = 2T(n/2) + O(n)$, $T(n) = 2T(n/2) + O(n^2)$, $T(n) = 4T(n/2) + O(n)$).
**Egzersiz 4.** Bir set AVL için yeni bir augmentation tasarla (örn. alt-ağaç toplamı), formülünü yaz ve rotasyonda $O(1)$'de korunduğunu kanıtla.
**Egzersiz 5.** İki anahtarlı (örn. isim + öncelik) bir veri yapısı problemini cross-linking ile çöz: hangi veri yapılarını, neye anahtarlanmış, hangi değişmezlerle kurarsın?
## Quiz 2 Öncesi Kapsam Genişlemesi {#sec-quiz-2-kapsam}
Quiz 1 buraya kadar; sıradaki blok (**Quiz 2** kapsamı) **çizge algoritmalarına** geçer:
- **Ders 13 ve 15 (L9-L10):** çizge temeli, **BFS** (ağırlıksız en kısa yol, $O(V+E)$), **DFS** (topolojik sıralama, çevrim).
- **Ders 16, 18-19 (L11-L13; araya Ders 17 PS5 girer):** **ağırlıklı** en kısa yollar — Bellman-Ford (negatif kenar), Dijkstra (öncelik kuyruğu).
- **Ders 21 (L14):** tüm-çiftler en kısa yollar (Johnson).
Bağ: bu blokta da aynı disiplin sürer — çizgeyi komşuluk listesiyle sakla (bir veri yapısı seçimi), problemi BFS/DFS/Dijkstra **kara kutusuna indirge**, sonra verimliliği analiz et.
## Ders 1-12 Toplu Cheat Sheet {#sec-toplu-cheat-d14}
| Konu | Özü | Kaynak (L/PS) |
|------|-----|------|
| Hesaplama modeli | Word-RAM; $O(1)$ işlemler; tamsayı bir kelimeye sığar | L1 |
| Asimptotikler | $O$, $\Theta$, $\Omega$; karmaşıklık mertebeleri | L1-L2 |
| Master teoremi | $T(n) = a \cdot T(n/b) + f(n)$; 3 durum | PS2 |
| Sıralama | merge/AVL ($n \log n$), heap (worst $n \log n$, in-place), radix ($n^c \to$ linear) | L3, L5 |
| Sequence DS | doubly-linked ($O(1)$ uç), dynamic array, sequence AVL ($O(\log n)$ orta) | L2, L7 |
| Set DS | sorted array (statik), set AVL (dinamik), hash (sözlük hızlı / sıra kötü) | L3 |
| Hashing | beklenen $O(1)$; zincirleme; universal hashing | L4 |
| İkili ağaç / AVL | $O(h)$; denge $\to h = O(\log n)$; rotasyon; augmentation | L6-L7 |
| İkili yığın | complete tree $\leftrightarrow$ array; build $O(n)$, delete_max $O(\log n)$ | L8 |
| Öncelik kuyruğu | binary heap veya max/min-augmented sequence AVL | L8 |
::: {.callout-warning title="Sonraki Ders"}
**Ders 15 (L10): Derinlemesine Arama (DFS)**
Justin Solomon ile, BFS'in kardeşi **DFS (depth-first search)**'e geçiyoruz: çizgeyi "olabildiğince derine in, sonra geri çekil" mantığıyla gez. DFS, **topolojik sıralama** (bağımlılık sıralaması) ve **çevrim tespiti** için kullanılır.
:::
## Builder ve OMSCS Bağlantıları {#sec-builder-omscs-d14}
::: {.callout-tip title="6 köprü"}
Bu tekrar oturumu, "doğru kara kutuyu seç, indirge, sakladığını ve anahtarladığını yaz" disiplinini kurar — köprülerin özeti:
1. **Quiz 1 = ilk-yarı midterm** → OMSCS CS 6515: veri yapıları + sıralama refleksleri, graduate dersin giriş varsayımıdır.
2. **Reduction → her şey** → "kara kutuya indirge" disiplini, DP ve NP-tamlıkta (problem A'yı B'ye indirgemek) birebir döner.
3. **Correctness/efficiency ayrımı** → mühendislikte "önce çalışsın, sonra hızlansın"; profilleme öncesi doğruluk.
4. **Cross-linking** → gerçek sistemler: aynı veriyi iki indeksle (örn. ID + zaman) tutup işaretçiyle bağlamak — veritabanı ikincil indeksi.
5. **Augmentation = subtree-property** → aralık sorguları (segment tree, order-statistics tree) — finans/analitik altyapısının çekirdeği.
6. **İletişim puana dahil** → kod review, tasarım dokümanı: "doğru ama anlatılamayan = yanlış".
:::
---
::: {.callout-important title="Tek bir şey alıp gideceksen"}
Quiz 1 senden algoritma icat etmeni değil, **doğru kara kutuyu seçmeni** ister. Problemi bir arayüze indirge, ne sakladığını ve neye anahtarlandığını açıkça yaz, doğruluğu değişmezlerle kanıtla — verimlilik en son gelir. "Doğru ama anlatılamayan çözüm, yanlış çözümdür."
:::
