Vize provası · A–D

A1: Height kenar sayısıdır; tek düğümün yüksekliği 0. Insert sırasını izleyerek ağacı çiz; red-black balancing uygulanmıyor.

A2: A'da n^(log₂3) = 3^(log₂n). B'de (log₂n)^7 / n^0.7 → 0. C'de log₂(√n) / √(log₂n) = √(log₂n)/2 → ∞. D'de 32^(log₂n) = n^5. O ve Ω aynı anda varsa Θ da vardır.

A3: A: n'i log n kez topla. B: azalan geometric series, toplam n ile 2n arasında. C: n'i n kez topla. D: n H_n, harmonic series H_n = Θ(log n).

A4: Sırasıyla T(n)=3T(2n/3)+Θ(1), 2T(3n/4)+Θ(n), 2T(2n/3)+Θ(n), 3T(3n/4)+Θ(n²). b, kalan parçanın tersidir: 2n/3 için b=3/2. Örtüşen parçalar veya tekrarlanan aynı çağrı da ayrı iş yapar. D'de log_(4/3)3 > 2 olduğundan yapraklar baskın; otomatik olarak n² log n çıkmaz.

A5:

• A: Her değer yalnız iki kez var. Bounded multiplicity, random pivot altında expected Θ(n log n) sonucunu korur; Θ(n) tane eşit değer içeren girdiden farklıdır.
• B: İlk pivot 2, sol tarafta yalnız 1 bırakır; sağ tarafta en küçük/ikinci en küçük pivotlarla sabit sayıda eleman elenir. Lineer partition işleri n, n−O(1), … boyutlarda sürer ve Θ(n²) olur. Küçük bir izde sağ parça [4,3,6,5,8,7] olur.
• C: n/2 tane sıfır birbirinden ayrıştırılamaz; <= partition bunları aynı tarafa gönderir. Her sıfır çifti sonunda karşılaştırılır: Ω(n²), üst sınır O(n²). Random pivot bu iki yönlü partition'ın eşitlik sorununu çözmez.
• D: Son pivot n/2 ilk adımda iki yarı oluşturur, fakat sol yarı sıralıdır. Son eleman pivotuyla bu n/2 elemanlık sıralı parça tek başına Θ(n²) iş çıkarır.

T(n)=aT(n/b)+n, T(1)=1. Bütün formlarda d=1: root işinin n olması bunu verir. t. seviyede a^t problem, her biri n/b^t boyutunda; toplam iş n(a/b)^t. h=log_b n, h+1 seviye, son seviyede a^h=n^(log_b a) yaprak ve aynı miktarda iş.

q=a/b < 1 ve yaprak seviyesi dahil:

T(n) = n(1−q^(h+1))/(1−q).

Hepsinde Θ(n); en çok işi root yapar. Tabloyu kontrol: A'da n=64 için 64+48+36+27=175; B'de n=81 için 81+54+36+24+16=211; C'de n=256 için 256+128+64+32+16=496; D'de n=216 için 216+144+96+64=520.

Partition geriye çözme

Yalnızca “solu küçük, sağı büyük” görünümüne bakarak pivotu kesin belirleyemezsin. Adayı orijinal dizide bul, verilen swap algoritmasıyla son diziyi doğrula.

Boşluklar

Aralıklar [start,end); end dahil değil. A/B/C'de k 0-based global index. D'de k 1-based global rank; hedef indeks k−1, recursive call'da k değişmiyor.

def quick_select(A, start, end, k):  # k: global 0-based index
    if end - start == 1:
        return A[start]
    r = partition(A, start, end, end - 1)  # trace için last pivot
    if r == k:
        return A[r]
    if k < r:
        return quick_select(A, start, r, k)
    return quick_select(A, r + 1, end, k)

Last-pivot izleri ve sayım

Her partition sonrası değişmiş diziyle devam et. Baştaki diziden tekrar başlama.

A/B'de partition en çok n−1 kez (n=1 için 0). C'nin yukarıdaki >1 loop'u en çok n−1 tur. D'de ilk çağrı ve tek elemanlı base case dahil toplam en çok n çağrı. Her adım en az pivotu çıkarır; yalnız bir alt parçaya girilir. Çağrı sayısının O(n) olması süreyi O(n) yapmaz: worst case partition işleri toplamı Θ(n²).

1. Brute force

Her i için j=i+1,…,n−1 değerlerini dolaş; formdaki koşul doğruysa sayacı artır. n(n−1)/2 çift kontrolü, Θ(n²) süre.

2. Lineer combine

L ve R artan sıralı; L, orijinal dizinin sol yarısından, R sağ yarısından gelir. Her iki yönde de pointer yalnız ileri gider: toplam O(len(L)+len(R)).

def cross_count(L, R, form):
    j = 0
    count = 0
    for x in L:
        if form == "A":       # x > 2*y
            while j < len(R) and x > 2 * R[j]:
                j += 1
            count += j
        elif form == "C":     # x > y+5
            while j < len(R) and x > R[j] + 5:
                j += 1
            count += j
        elif form == "B":     # y > 3*x
            while j < len(R) and R[j] <= 3 * x:
                j += 1
            count += len(R) - j
        else:                 # D: y > x+10
            while j < len(R) and R[j] <= x + 10:
                j += 1
            count += len(R) - j
    return count

A/C'de uygun y'ler R'nin prefix'i; B/D'de suffix'i. j'yi her x için sıfırlama. Strict > eşitlikte saymaz; B/D'de bu yüzden atlanacakların koşulu <=. Sabit form için branch kontrolü O(1).

3. Divide and conquer

def count_pairs(A, form):
    if len(A) <= 1:
        return A[:], 0
    m = len(A) // 2
    L, left_count = count_pairs(A[:m], form)
    R, right_count = count_pairs(A[m:], form)
    cross = cross_count(L, R, form)
    return merge(L, R), left_count + right_count + cross

merge iki sıralı listeyi lineer zamanda birleştiren standart yordamdır. CountDrops/CountJumps/CountFalls/CountRises sırasıyla A/B/C/D formunu kullanır; istenen sonuç dönen çiftin ikinci bileşenidir.

4. Running time

T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+Θ(n)=Θ(n log n). Slicing, combine ve merge toplam Θ(n) iş; her seviyede Θ(n), Θ(log n) seviye. Canlı ek bellek O(n), çağrı derinliği O(log n).

5. Correctness

Inductive hypothesis: kısa listelerde yordam sıralı listeyi ve doğru sayıyı döndürür. Her i<j çifti tam bir sınıftadır: ikisi sol yarıda, ikisi sağ yarıda veya biri solda biri sağda. İlk iki sınıf induction ile sayılır. Cross sınıfında orijinal i<j koşulu yarı üyeliğinden gelir; yarıyı sıralamak bu üyeliği değiştirmez. Sıralı R'deki uygun prefix/suffix her x için tam olarak bir kez sayılır. Sınıflar ayrık ve tüm çiftleri kapsar; merge de sıralı listeyi verir. Dizinin tamamını başta sıralamak i<j bilgisini yok eder.

Kontrol örnekleri: A [5,9,2,8,3,1] → 8; B [4,1,13,2,9,20] → 7; C [12,3,15,9,1,7] → 6; D [5,18,2,14,30,11] → 6. PDF'lerdeki cross örnekleri sırasıyla 3,3,4,4 verir.

IsSorted([1,3,2,4]) True döndürür; uçlar 1<4 ve iki yarı kendi içinde sıralıdır, ama orta sınırda 3>2 vardır. Genel hata: recursive kontrollerden geçen, ilk elemanı son elemanından küçük olan fakat ortadaki komşuları ters duran listeyi kabul edebilir. Herhangi bir alt çağrıdaki bu hata da yukarı taşınabilir.

return (A[n//2 - 1] < A[n//2]
        and IsSorted(A[:n//2]) and IsSorted(A[n//2:]))

Inductive step: n≥2 için her iki yarı daha kısadır; hypothesis sayesinde iki recursive sonuç o yarıların sıralılığına denktir. Bütün listenin sıralı olması, iki yarının sıralı olması ve solun son elemanının sağın ilk elemanından küçük olmasına denktir. Düzeltilen satır tam bu üç koşulu kontrol eder.

FindMax([4,9,2]) bir elemanlı listeye iner, ardından boş listeyi recursive olarak çağırır; matematiksel olarak sonlanmaz, Python'da RecursionError oluşur. Eski kod yalnız n=2^k, k≥1 uzunluklarında çalışır; diğer uzunluklarda recursion tree'de n=2'ye ulaşmadan n=1 dalı oluşur. n=1 de çalışmaz.

if n == 1:
    return A[0]
# mevcut n==2 base case kalabilir; geri kalan kod aynı

Inductive step: n=2 mevcut base case ile doğru. n≥3 için iki yarı boş değildir ve n'den kısadır; hypothesis her birinin maximum'unu verir. İkisinin maximum'u ayrık birleşimlerinin, yani A'nın maximum'udur. n=2 özel durumunu kaldırıp yalnız n=1 base case bırakmak da doğrudur; o sürümde step doğrudan n≥2'yi kapsar.

Contains([4,7,1],7) False döndürür. Her non-base call A[n//2]'yi atlar. Aranan değer yalnız atlanan konumlarda bulunuyorsa False yanlış olur; başka bir kopyası incelenen konumda bulunursa True yine doğru olabilir.

return Contains(A[:n//2], x) or Contains(A[n//2:], x)

Inductive step: n≥2 için iki yarı daha kısadır ve birlikte A'nın tamamını, hiç eleman atlamadan kapsar. Hypothesis ile her recursive sonuç x'in o yarıda bulunmasına denktir. x birleşimde ancak ve ancak en az bir yarıda bulunduğundan OR doğru sonucu verir.

CountBig([6,9,2],5) 3 döndürür; 9 iki yarıda da bulunur. Tek uzunluklu herhangi bir alt çağrıda ortak orta eleman x'ten büyükse fazladan sayılır. Başlangıç uzunluğu çift olsa da alt çağrılar tek olabilir (n=6 → 3+3). Kod yalnız fazla sayabilir; böyle bir ortak uygun eleman yoksa sonuç doğrudur.

return CountBig(A[:n//2], x) + CountBig(A[n//2:], x)

Inductive step: n≥2 için iki yarı boş değildir, daha kısadır ve ayrık birleşimleri A'dır. Hypothesis her yarıda x'ten büyüklerin doğru sayısını verir. Ayrık kümelerde sayılar toplandığından yeni satır bütün listedeki doğru sayıyı döndürür.

Slicing: dört form için ortak maliyet

Düzeltilmiş kodların worst case recurrence'ı T(n)=T(⌊n/2⌋)+T(⌈n/2⌉)+Θ(n), sonuç Θ(n log n). Python list slice'ları kopyadır; iki yarının toplam kopyalama maliyeti Θ(n). A/C'de short-circuit bazı çağrıları atlayabilir; bütün dalları gezen girdiler worst case'i gerçekleştirir (A: sıralı liste; C: x listede yok). İndeks aralıklarıyla kopyasız yazılsaydı bu dört algoritmanın worst case'i Θ(n) olurdu; verilen slicing'li kod için bunu yazma.

Sıfırdan başlarken ilk iş bir formu bitirmek değil, aşağıdaki konu sırasını çalışmaktır. Her derste küçük örneği uygula, kontrol sorusunu cevapla, sonra aynı bölümdeki çıkmış soruyu dene. Takıldığında ipucunu aç; çözümü okuduktan sonra kapatıp benzer bir soruyu kendin çöz.

• Asymptotics → recurrences → substitution: O/Ω/Θ, loop sayma, recursion tree ve induction.
• InsertionSort/MergeSort → QuickSort: trace, correctness, özel input ve partition.
• Select/QuickSelect → lower bound/RadixSort: tek tarafa recursion, index/rank, digit/pass.
• Heap → BST/red-black tree: yapı, operation maliyeti ve height.
• D&C design: algoritma kurma, merge ile çift sayma ve “tam bir kez” ispatı.

Konuları öğrendikten sonra aşağıdaki prova bloklarına geç:

1. Tanı · 25 dk: Bir formun Part A/B'sini kapalı kaynak çöz. B'de her cevabın yanına bir cümle gerekçe yaz. Yanlışı ilgili lab dersine bağla.
2. Recursion tree · 25 dk: Bir C1'i Master theorem olmadan çöz; sonra farklı a,b ile yeni bir tablo kur. Yaprakları iki kere ekleme, h+1 seviyeyi unutma.
3. Partition/QuickSelect · 30 dk: Her swap'ta diziyi yaz. A/B/C indeks, D rank; her satırda start,end,pivot,r ve sonraki aralığı göster.
4. Tasarım · 40 dk: A/C prefix ve B/D suffix sayımını kâğıtta yaz. Eşitlik sınırlarını ve tek elemanlı girdiyi dene; recurrence ve “tam bir kez” ispatını ekle.
5. Correctness · 30 dk: E1 için karşı örnek → tek satır düzeltme → induction hypothesis → inductive step → slicing maliyeti sırasını dört formda uygula.
6. Prova: Henüz çözmediğin formu tek oturumda kâğıtta çöz; süreyi kendin kaydet. Resmî süre duyurulunca ona göre yeniden prova yap. Puanları A/B/C/D/E için 25/15/15/30/15 üzerinden ayrı hesapla; bu dağılım yayımlanan formlara aittir.
7. Kapsam turu: L1–7'de formların doğrudan sormadığı başlıkları, HW1–HW4 ve S5.5'i tamamla. Son gün yeni cevap ezberlemek yerine yanlışlarını yeniden çöz.

Lab: vize çalışması · tüm dersler.