Divide and conquer tasarımı ve Karatsuba

S8: Constant factor sadece bir kez çarpılır, growth rate'in etkisi ise $n$ ile birlikte büyür. $10^4 n^{1.6} < n^2 \iff n > 10^{10}$; bu eşikten sonra $n^{1.6}$'lık algoritma, 10 000 kat yavaş donanımda bile kazanır.

S9: $(a+b)(c+d) - ac - bd = ad + bc$. $ac$ ve $bd$ zaten gerekli, ortadaki terimi tek bir ek multiplication ile buluruz.

S10: 4 subproblem'de $T(n) = 4T(n/2)+O(n)$, leaf'ler $4^{\log_2 n} = n^2$: grade-school yöntemiyle aynı. 3 subproblem'de $3^{\log_2 n} = n^{\log_2 3} \approx n^{1.585}$. Fark her level'de biriktiği için exponent'e yansır.

False: ortadaki 7 atlanır. Sağ yarı A[n//2:] olmalı. Hypothesis kısa listelerde doğruluk; n≥2’de iki daha kısa yarı tüm listeyi kapsar. x A’da ancak ve ancak en az bir yarıda olduğundan OR doğrudur. x yokken bütün dallar gezilir; slicing ile T(n)=2T(n/2)+Θ(n)=Θ(n log n) worst case.

A–D formlarındaki sorular ve kâğıt provası →

Fikir: $A[i] = i$ özelliği önce doğru, ilk boşluktan sonra hep yanlış. Yanlış olduğu ilk index'i binary search ile bulurum; cevap o index'in kendisi.

Pseudocode: yukarıdaki FirstMissing. Recursive yazmak da olur. 2020-21 cevap kâğıtlarından birinde (Altungöz) şu yazılmış ve doğru çalışıyor:

missAppoint(A, first, last):
    if first > last: return last + 1
    if A[first] != first: return first
    middle = floor((first + last) / 2)
    if A[middle] == middle: return missAppoint(A, middle + 1, last)
    return missAppoint(A, first, middle)

Correctness: Invariant korunur. $A[mid] = mid$ ise array sorted ve elemanlar farklı olduğundan $1..mid$ hepsi array'de, sola bakmak gereksiz. $A[mid] > mid$ ise sağdaki her index de ">", sağa bakmak gereksiz. Bitişte $A[lo-1] = lo-1$ (ya da $lo = 1$) ve $A[lo] \ge lo+1$ (ya da $lo = n+1$). Yani $1..lo-1$ array'de, $lo$ değil: cevap $lo$.

Trace ($A = [1,2,3,5,7,8,10]$): $mid = 4$, $A[4] = 5 > 4$ ⇒ $hi = 3$. $mid = 2$, $A[2] = 2$ ⇒ $lo = 3$. $mid = 3$, $A[3] = 3$ ⇒ $lo = 4$. $lo > hi$, cevap 4 ✓.

Running time: $T(n) = T(n/2) + O(1)$ ⇒ $O(\log n)$ (master theorem, $a = 1, b = 2, d = 0$, $a = b^d$).

Yorum: $A \subseteq \{1,\dots,m\}$ olduğu için 0 hiçbir zaman $A$'da değil. Kelimesi kelimesine okursan cevap hep 0 olur ve soru anlamını yitirir. Örnek 4 dediği için en küçük pozitif eksik sayıyı arıyorum. Cevabın başına bu cümleyi yaz.

Fikir: Hiç eksik olmasaydı $A[i] = i$ olurdu. İlk boşluktan itibaren $A[i] > i$. "$A[i] > i$" olan ilk index'i binary search ile bulurum; cevap o index'in kendisi.

SmallestMissing(A[1..n]):
    lo = 1; hi = n
    while lo <= hi:
        mid = floor((lo + hi) / 2)
        if A[mid] == mid: lo = mid + 1   // 1..mid hepsi A'da, cevap sağda
        else:             hi = mid - 1   // A[mid] > mid: boşluk mid'de ya da solunda
    return lo                            // lo = n+1 ise A = [1..n]; n < m olduğundan n+1 geçerli bir cevap

Neden doğru: Elemanlar farklı, sorted ve $\ge 1$, yani $A[i] \ge i$. Bir kez $A[i] > i$ olunca sonraki her index'te de öyle. Loop bitince $1..lo-1$ index'lerinde $A[i] = i$; $lo$'da ise ya $A[lo] > lo$ ya da $lo = n+1$. İki durumda da $lo$ eksik ve ondan küçük her pozitif sayı array'de.

Trace: $A = [2,4,5]$: $mid = 2$, $A[2] = 4 > 2$ ⇒ $hi = 1$. $mid = 1$, $A[1] = 2 > 1$ ⇒ $hi = 0$. Cevap $lo = 1$. $A = [1,2,3,4,5,6,9]$: $mid = 4$ ⇒ $lo = 5$. $mid = 6$ ⇒ $lo = 7$. $mid = 7$, $A[7] = 9 > 7$ ⇒ $hi = 6$. Cevap 7.

Running time: Her iterasyonda $O(1)$ iş var ve aralık yarıya iniyor: $T(n) = T(n/2) + O(1) = O(\log n)$.

Fikir: 2019-20 S5 ile aynı soru, bu kez çalışan kod isteniyor. Python list'leri 0-indexed olduğu için eksiksiz bir array'de $A[i] = i + 1$. Bu eşitliğin bozulduğu ilk index'i binary search ile bulurum; cevap o index $+1$. ("non-negative" kelimesi için 2019-20 S5'teki yorumu yaz.)

def smallest_missing(A):
    lo, hi = 0, len(A) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if A[mid] == mid + 1:   # A[0..mid] = 1..mid+1, boşluk sağda
            lo = mid + 1
        else:                   # A[mid] > mid + 1, boşluk mid'de ya da solunda
            hi = mid - 1
    return lo + 1               # lo: A[i] != i+1 olan ilk index (yoksa lo = n)

print(smallest_missing([1, 2, 3, 5, 7, 8, 10]))   # 4
print(smallest_missing([2, 3, 4]))                # 1
print(smallest_missing([1, 2, 3]))                # 4

Neden doğru: Loop invariant: $i < lo$ olan her index'te $A[i] = i+1$, $i > hi$ olan her index'te $A[i] > i+1$. Loop bitince $lo = hi + 1$, yani $lo$ eşitliğin bozulduğu ilk index, ya da boşluk yoksa $lo = n$. Her iki durumda $1..lo$ sayıları array'de, $lo+1$ değil.

Running time: Her iterasyonda aralık yarıya iniyor ve $O(1)$ iş yapılıyor: $O(\log n)$. Extra space $O(1)$.

Sık yapılan iki hata: 1-indexed formülü olduğu gibi koda taşıyıp A[mid] == mid yazmak (örnekte 1 döner) ve sonda lo'yu +1 eklemeden döndürmek (örnekte 3 döner).

(a) Her row'da son 1'i binary search ile bul ($O(\log n)$), en büyük column'u tut: $m$ row × $O(\log n)$.

(b) $j = -1$ ile başla (0-indexed). Her row'da while j+1 < n and M[r][j+1] == 1: j = j+1; $j$ arttıysa $(r, j)$'yi kaydet. $j$ en fazla $n$ kez artar, her row'da bir de başarısız kontrol var: $O(m + n)$. Örnek matriste cevap $(1, 3)$.

Fikir: $B$'yi bir kez sort et. Sonra $A$'nın her ID'sini sorted $B$'de binary search ile ara ve bulunanları say. Bir öğrenci bir kulübe bir kez kaydolduğu için her array'de ID'ler farklı; her eşleşme ayrı bir öğrenci.

CountCommon(A, m, B, n):
    MergeSort(B, 1, n)                          // class'ta tanımlı, worst case O(n log n)
    count = 0
    for i = 1 to m:                             // m iterasyon
        if BinarySearch(B, 1, n, A[i]) != NIL:  // O(log n)
            count = count + 1
    return count

Trace: Sorted $B = [1,2,3,4,5,7,11]$. 2: bakılanlar 4, 2 ⇒ var. 6: 4, 7, 5 ⇒ yok. 3: 4, 2, 3 ⇒ var. 9: 4, 7, 11 ⇒ yok. 11: 4, 7, 11 ⇒ var. 8: 4, 7, 11 ⇒ yok. Cevap 3 ✓.

Neden $O(m\log n)$ (sorunun istediği açıklama): Loop $m$ kez döner. Her iterasyondaki binary search, $n$ elemanlı aralığı her karşılaştırmada yarıya indirir; en fazla $\lfloor\log_2 n\rfloor + 1$ karşılaştırma yapar, yani recurrence $T(n) = T(n/2) + O(1) = O(\log n)$. Count'u artırmak $O(1)$. Arama kısmının toplamı $m \cdot O(\log n) = O(m\log n)$.

Sort adımını da dürüstçe yaz: $B$ sorted verilmediği için sort ayrıca $O(n\log n)$ tutar; toplam $O(n\log n + m\log n) = O(n\log n)$. Bu ancak $m = \Theta(n)$ iken $O(m\log n)$'e eşit. Unsorted $B$ ile her durumda $O(m\log n)$ zaten mümkün değil: $B$'nin bakmadığın bir elemanı $A$'daki bir ID'ye eşit olabilir, yani her algoritma $B$'nin $n$ elemanını da okumak zorunda ($\Omega(n)$). Oysa $m = 1$ iken $m\log n = \log n$. Cevapta iki satırı ayrı yaz: "$B$ sorted ise $O(m\log n)$; sort dahil $O(n\log n)$."

Sort için MergeSort seç: QuickSort'un worst case'i $O(n^2)$, sadece expected running time'ı $O(n\log n)$.

Daha iyi seçenek: Küçük olan $A$'yı sort et ($O(m\log m)$) ve $B$'nin her elemanını $A$'da ara ($n$ kez $O(\log m)$). Toplam $O((m+n)\log m)$, $m \ge 2$ için. $m \le n$ olduğundan bu hiçbir zaman $O(n\log n)$'den kötü değil, $m$ küçükse çok daha iyi.

Fikir: Random pivot ile partition yap. Soldaki eleman sayısı olması gerekene tam eşitse sol taraf eksiksizdir, sağa geç; değilse eksik soldadır. Her adımda tek tarafla devam ettiğim için QuickSelect gibi expected $O(n)$.

SmallestMissing(A, lo):          // A: farklı sayılar, hepsi >= lo
    if A is empty: return lo
    p = A'dan rastgele bir eleman
    L = [x in A : x < p];  R = [x in A : x > p]     // partition, O(|A|)
    if |L| == p - lo:  return SmallestMissing(R, p + 1)
    else:              return SmallestMissing(L, lo)

cevap = SmallestMissing(A, 1)

Correctness: $L$'deki sayılar farklı ve $[lo, p-1]$ içinde. $|L| = p - lo$ ise bu aralığın her sayısı var, $p$ de var; o halde cevap $\ge p+1$ ve cevabı sadece $R$'deki sayılar etkiler. $|L| < p - lo$ ise $[lo, p-1]$'de bir eksik var ve en küçük eksik orada; bu aralık sadece $L$'nin sayılarına bağlı. Boş array'de $lo$ eksiktir. Her call'da array en az 1 küçülür, yani algoritma biter.

Running time: Partition $O(n)$. Random pivot $1/2$ probability ile ortadaki yarıdan gelir, o zaman kalan taraf $\le 3n/4$. Expected olarak 2 denemede bir size $3/4$'e iner: $E[T(n)] \le 2cn + E[T(3n/4)]$ ⇒ $E[T(n)] \le 8cn = O(n)$. Worst case (pivot hep en kötü çıkarsa) $O(n^2)$; soru "average" istediği için bu kabul edilir.

Trace (pivot = ilk eleman, animasyondaki array): $p=16$: $|L| = 10 \ne 15$ ⇒ sol. $p = 13$: $9 \ne 12$ ⇒ sol. $p=9$: $7 \ne 8$. $p=5$: $3 \ne 4$. $p=4$: $2 \ne 3$. $p=1$: $0 = 0$ ⇒ sağ, $lo = 2$. $p=2$: $0 = 0$ ⇒ sağ, $lo = 3$. Array boş: cevap 3 ✓.

Fikir: Median'ı Select ile bul, her sayının median'a distance'ını hesapla, distance'lar arasında $k$-th smallest değeri Select ile bul, ondan küçük ya da ona eşit olanları topla.

KClosest(S, k):
    med = Select(S, ceil(n/2))                  // O(n)
    D = [ |x - med| for x in S ]                // O(n)
    t = Select(D, k)                            // k. en küçük uzaklık, O(n)
    out = [x in S : |x - med| < t]
    S içinde |x - med| == t olanlardan, out k olana kadar ekle
    return out                                   // toplam O(n)

Correctness: Distance'ı $t$'den küçük olan her sayı, en yakın $k$ sayının içinde olmak zorunda; $t$ $k$-th smallest distance olduğundan bunlar $< k$ tane. Eşit distance'lı sayılardan ($x = \text{med} \pm t$) $k$'ya tamamlayacak kadar ekleriz. Median'ın kendisi distance 0 ile listede; soru onu saymıyorsa $k+1$ ile çalıştır ve median'ı çıkar.

Trace: $S = \{1, 2, 10, 11, 12\}$, $k = 2$. Median 10, $D = [9, 8, 0, 1, 2]$, $t = \text{Select}(D, 2) = 1$. Distance'ı $< 1$ olan: 10. Distance'ı $= 1$ olandan bir tane: 11. Sonuç $\{10, 11\}$. Median'ı saymıyorsan $k+1 = 3$ ile çalıştır: $t = 2$, $\{10, 11, 12\}$, median'ı çıkar: $\{11, 12\}$.

Running time: üç $O(n)$ adım ve bir tarama: worst case $O(n)$.

(1.1) İki array'i arka arkaya koy, Select ile $n$-th smallest elemanı bul: $O(n)$. Her elemana bakmak zorundasın (bakmadığın eleman median'ı değiştirebilir), yani lower bound $\Omega(n)$; $O(n)$ optimal.

(1.2) $k = n$ ile başla. $A[k/2] \le B[k/2]$ ise $A$'nın ilk $k/2$ elemanının her biri için, ondan küçük en fazla $k-2$ eleman var; hiçbiri $k$-th smallest olamaz. Onları at ve $k \leftarrow k - k/2$ yap. Simetrik durum aynı. Her adımda $k$ yarıya iner: $T(k) = T(k/2) + O(1) = O(\log n)$. (CLRS 4e Alıştırma 9.3-10 aynı soru.)

Fikir: Yakıt yetiyorsa dur. Yetmiyorsa ulaşabildiğim en uzak istasyonda dur ve kalan yolu aynı fonksiyonla çöz.

// m (toplam yol) ve n global; şu anki konum = m - r
minStops(r, g, X, s):
    if g >= r: return 0                      // şehre durmadan ulaşırım
    pos = m - r
    j = s - 1
    while j + 1 <= n and X[j+1] - pos <= g:  // ulaşabildiğim en uzak istasyon
        j = j + 1
    if j < s: return INFINITY                // hiçbir istasyona yetmiyor (verilen koşullarda olmaz)
    return 1 + minStops(m - X[j], 300, X, j + 1)

cevap = minStops(m, 300, X, 1)

Correctness (greedy stays ahead): Herhangi bir optimal plan ilk durağını ya benim seçtiğim en uzak istasyondan önce yapar ya da tam orada. Onun ilk durağını benimkiyle değiştirirsem plan hâlâ geçerli: ben en az onun kadar ilerideyim ve dolu depoyla çıkıyorum, onun ikinci durağına da yetişirim. Durak sayısı artmadı. Aynı iddia kalan yol için induction ile sürer.

Running time: $j$ hiç geri gitmez. Tüm call'lar boyunca her istasyon en fazla bir kez "ulaşılabilir" diye kontrol edilir, her call bir de başarısız kontrol yapar. Call sayısı $\le n + 1$, toplam $O(n)$. Recurrence olarak: $T(n) = T(n - k) + O(k+1)$, burada $k$ bu adımda geçilen istasyon sayısı ⇒ $O(n)$. Durak sayısı azsa $j$'yi her adımda binary search ile bulmak $O(s\log n)$ verir ($s$ = durak sayısı). Cevabına bunu bir cümle olarak eklemek "as fast as possible" kısmına iyi gelir.

Trace: $m = 1000$, $X = [100, 250, 400, 520, 700, 850]$. Konum 0, yakıt 300 ⇒ ulaşılabilir 100, 250 ⇒ 250'de dur. Konum 250 ⇒ 520'ye kadar ⇒ 520'de dur. Konum 520 ⇒ 700'de dur. Konum 700, kalan 300, yakıt 300 ⇒ bitti. 3 durak, tüm durak kombinasyonlarını deneyen DP ile aynı.

B için while R[j]≤3x, D için while R[j]≤x+10 ile j’yi ilerlet; her x için len(R)−j ekle. C için while x>R[j]+5; her x için j ekle. Her formda recursive yapı aynı, cross koşulu farklı.