Advanced Algorithms

Undergraduate, Giresun University, Computer Engineering, 2026

advanced algorithms This course is the continuation of Algorithms. It studies the main algorithm-design paradigms (divide and conquer, greedy algorithms and dynamic programming), methods for hard problems (backtracking, branch and bound and approximation algorithms), and other models of computation: randomized, online and parallel algorithms. For each technique the course examines correctness, running time and the kinds of problems it suits, and compares the techniques on shared examples such as the knapsack and travelling salesman problems.


Ders Kitabı

📕 İleri Algoritmalar (PDF, 9 MB)


Başlangıç Kaynakları


Kısım I: Tasarım Paradigmaları

Bölüm 1: Böl ve Fethet Yaklaşımı

Böl ve fethet yaklaşımı, bir problemi aynı türden daha küçük alt problemlere böler, bunları özyinelemeli olarak çözer ve sonuçları birleştirir. Bölümde genel şablon ile buna karşılık gelen yineleme bağıntısı, Ana Teorem ile çözümleme, birleştirme sıralaması, hızlı sıralama ve hızlı üs alma örnekleri ele alınır; alt problemler örtüştüğünde yaklaşımın neden verimsizleştiği gösterilir. Geometriden Quickhull ile dışbükey örtü ve en yakın nokta çifti, aritmetikten Karatsuba tam sayı çarpımı ve Strassen matris çarpımı ayrıntılı biçimde incelenir.


Bölüm 2: Açgözlü Algoritmalar

Açgözlü algoritmalar çözümü adım adım kurar, her adımda o an en iyi görünen seçimi yapar ve bu seçimi sonradan değiştirmez. Bölümde açgözlü seçim özelliği ile optimal alt yapı koşulları anlatılır; para üstü problemi üzerinden yaklaşımın hangi durumda en iyi sonucu verdiği, hangi durumda yanıldığı gösterilir. Etkinlik seçimi, son tarihli iş sıralama ve kesirli sırt çantası problemleri, kesim özelliğine dayanan minimum kapsayan ağaç algoritmaları ve Huffman kodlaması işlenir; Huffman kodunun neden en iyi önek kodu olduğu da gerekçelendirilir.


Bölüm 3: Dinamik Programlama

Dinamik programlama, örtüşen alt problemleri bir kez çözüp sonuçlarını saklayarak üstel maliyetli özyinelemeleri polinom zamana indirir. Bölümde optimal alt yapı ve örtüşen alt problemler özellikleri, bir DP çözümü tasarlamanın adımları, bellekleme ile tablolama arasındaki fark ve yaklaşımın böl ve fethet ile açgözlü yöntemlerden ayrıldığı noktalar Fibonacci örneği üzerinden açıklanır. Ardından 0/1 ve sınırsız sırt çantası, alt küme toplamı, en uzun artan alt dizi, en uzun ortak alt dizgi ve en uzun ortak alt dizi problemleri tablolar adım adım doldurularak çözülür. En uzun artan alt dizi için ikili aramaya dayanan O(n log n) çözüm de verilir.


Kısım II: Zor Problemler

Bölüm 4: Geri İzleme Algoritmaları

Geri izleme, kısmi çözümleri adım adım genişleten ve geçerli bir çözüme ulaşamayacağı anlaşılan daldan vazgeçip önceki karar noktasına dönen sistematik bir arama yöntemidir. Bölüm P, NP ve NP-zor problemlere kısa bir girişle başlar; durum uzayı ağacı ve seç–keşfet–geri al şablonu labirent ve permütasyon örnekleriyle tanıtılır. n-vezir, Sudoku, çizge boyama, Hamilton yolu ve kelime arama problemleri Java kodlarıyla çözülür; en az çakışma sezgiseli yerel onarıma dayalı bir seçenek olarak gösterilir. Geri izlemenin en kötü durum maliyeti ve budamayı güçlendiren sezgiseller de tartışılır.


Bölüm 5: Dal Sınır Algoritmaları

Dal sınır yöntemi, durum uzayı ağacını tararken her düğüm için bir sınır hesaplar ve en iyi çözümü içeremeyeceği kesinleşen dalları budar. Bölümde sınırın seçimi, budama koşulları ve FIFO, LIFO ve en düşük maliyetli (LC) arama stratejileri anlatılır; yöntemin geri izlemeden farkı ortaya konur. 0/1 sırt çantası problemi kesirli gevşetmeyle, gezgin satıcı problemi giderek sıkılaşan üç alt sınırla çözülür; atama problemi, tam sayılı doğrusal programlama ve maksimum klik de örnek olarak işlenir. Dal sınırın A* ile ilişkisi kurulur ve tasarım paradigmaları birlikte karşılaştırılır.


Bölüm 6: Yaklaşım Algoritmaları

Yaklaşım algoritmaları, en iyi çözümü bulmanın çok pahalı olduğu NP-zor problemlerde polinom zamanda ve kanıtlanmış bir oran içinde en iyiye yakın çözümler üretir. Bölümde yaklaşım oranı kavramı ve yaklaşım algoritmasının sezgiselden ve yaklaşım şemalarından farkı açıklanır. Gezgin satıcı problemi için en yakın komşu sezgiseli, metrik TSP’de MST tabanlı 2-yaklaşım ve 2-opt yerel arama; iş çizelgelemede liste çizelgeleme ve en uzun iş önce (LPT) kuralı; düğüm kapsama için 2-yaklaşım algoritması ve 3-SAT’tan indirgeme işlenir. Sırt çantası için oran sıralı açgözlü yaklaşım ve baskın özvektörü bulan kuvvet yinelemesi (power iteration) de ele alınır.


Kısım III: Diğer Hesaplama Modelleri

Bölüm 7: Rastgele Algoritmalar

Rastgele algoritmalar, çalışma sırasında rastgele seçimler yaparak daha yalın bir tasarıma, daha iyi bir beklenen çalışma süresine ya da kötü girdilere karşı dayanıklılığa ulaşır. Bölümde Las Vegas ve Monte Carlo türleri ile hata olasılığının tekrarlı çalıştırmayla küçültülmesi anlatılır. Fisher–Yates karıştırması ve saf karıştırmanın yanlılığı, BogoSort, rastgele pivotlu hızlı sıralama ve beklenen karşılaştırma sayısı ile QuickSelect incelenir. Monte Carlo yöntemiyle π tahmini, Miller–Rabin asallık testi, Karger minimum kesim algoritması ve sözde rastgele sayı üretimi de bölümün konuları arasındadır.


Bölüm 8: Çevrim İçi Algoritmalar

Çevrim içi algoritmalar girdiyi parça parça alır ve geleceği bilmeden geri alınamaz kararlar verir. Bu algoritmaların başarısı, tüm girdiyi önceden bilen en iyi çevrim dışı algoritmayla karşılaştıran rekabetçi analiz ve düşman modeliyle ölçülür. Bölümde kayak kiralama problemi ve alt sınırı, FIFO, LRU ve OPT politikalarıyla sayfalama, Belady anomalisi ve rastgele işaretleme algoritması, liste güncellemede öne taşı (MTF) kuralı ele alınır. Veri akışı modelinde hareketli ortalama, çevrim içi ortanca, rezervuar örnekleme ve kayan hash ile örüntü arama, son olarak da artımlı öğrenme incelenir.


Bölüm 9: Paralel Algoritmalar

Paralel algoritmalar, hesaplamayı birden çok işlem birimine bölerek çalışma süresini kısaltmayı ve büyük veri kümelerini işlenebilir kılmayı amaçlar. Bölümde Flynn sınıflandırması, bellek mimarileri ve PRAM modeli ile hızlanma, verimlilik, maliyet, Amdahl yasası ve iş–derinlik ölçütleri tanıtılır. Paralel toplama ve önek toplamı (Hillis–Steele ve Blelloch), boru hattı ve boru hatlı ağaç, paralel birleştirme sıralaması, MapReduce ve veri paralelliğiyle matris çarpımı örnekleri işlenir. Yarış durumu, eş zamanlı çizge gezinme ve Java’daki paralellik araçları da ele alınır.


Getting Started


Part I: Design Paradigms

Chapter 1: Divide and Conquer

Divide and conquer splits a problem into smaller instances of the same problem, solves them recursively and combines the answers. We set up the general template and its recurrence, solve recurrences with the Master Theorem, and revisit merge sort, quicksort and fast exponentiation in this light, noting why the approach breaks down when subproblems overlap. The chapter then works through Quickhull for convex hulls, the closest pair of points, Karatsuba’s integer multiplication and Strassen’s matrix multiplication.


Chapter 2: Greedy Algorithms

A greedy algorithm builds its answer one step at a time, always taking the choice that looks best right now and never revisiting it. We state the greedy-choice property and optimal substructure, and use coin change to see when greed is optimal and when it fails. Activity selection, scheduling with deadlines, the fractional knapsack, minimum spanning trees through the cut property, and Huffman coding follow, together with a proof that Huffman’s code is an optimal prefix code.


Chapter 3: Dynamic Programming

Dynamic programming solves each overlapping subproblem once and stores the result, turning exponential recursions into polynomial-time algorithms. Using Fibonacci, we cover optimal substructure and overlapping subproblems, the steps of designing a DP solution, memoization versus tabulation, and how DP differs from divide and conquer and from greedy methods. We then fill in the tables step by step for 0/1 and unbounded knapsack, subset sum, longest increasing subsequence (including the O(n log n) binary-search version), longest common substring and longest common subsequence.


Part II: Hard Problems

Chapter 4: Backtracking

Backtracking extends a partial solution step by step and, as soon as a branch cannot lead to a valid solution, abandons it and returns to the last decision point. After a short introduction to P, NP and NP-hard problems, we present the state-space tree and the choose–explore–undo template with mazes and permutations. We solve n-queens, Sudoku, graph coloring, Hamiltonian paths and word search in Java, look at the min-conflicts heuristic as a local-repair alternative, and discuss the worst-case cost of backtracking and the heuristics that make pruning stronger.


Chapter 5: Branch and Bound

Branch and bound explores the state-space tree while computing a bound at every node, and prunes any branch that provably cannot contain the best solution. We discuss how to choose bounds and when to prune, compare FIFO, LIFO and least-cost (LC) search, and contrast the method with backtracking. The 0/1 knapsack is solved with the fractional relaxation and the travelling salesman problem with three progressively tighter lower bounds; the assignment problem, integer linear programming and maximum clique serve as further examples. We close by relating branch and bound to A* and comparing the design paradigms side by side.


Chapter 6: Approximation Algorithms

When finding the optimum of an NP-hard problem is too expensive, an approximation algorithm runs in polynomial time and returns a solution within a proven factor of the best one. We define the approximation ratio and separate approximation algorithms from heuristics and from approximation schemes. Topics include the nearest-neighbor heuristic, the MST-based 2-approximation for metric TSP and 2-opt local search; list scheduling and the longest-processing-time (LPT) rule; a 2-approximation for vertex cover and a reduction from 3-SAT; the ratio-sorted greedy method for knapsack; and power iteration for the dominant eigenvector.


Part III: Other Models of Computation

Chapter 7: Randomized Algorithms

Randomized algorithms make random choices while they run, which can buy a simpler design, a better expected running time or robustness against bad inputs. We distinguish Las Vegas from Monte Carlo algorithms and show how repeated runs drive the error probability down. The chapter covers the Fisher–Yates shuffle and the bias of the naive shuffle, BogoSort, randomized quicksort with its expected number of comparisons, and QuickSelect, followed by Monte Carlo estimation of π, the Miller–Rabin primality test, Karger’s minimum-cut algorithm and pseudorandom number generation.


Chapter 8: Online Algorithms

An online algorithm receives its input piece by piece and must make irrevocable decisions without knowing the future. We measure such algorithms by competitive analysis against an adversary, comparing them with the best offline algorithm that sees the whole input in advance. Topics include ski rental and its lower bound, paging with FIFO, LRU and OPT, Belady’s anomaly and the randomized marking algorithm, and the move-to-front rule for list update; in the data-stream model we look at moving averages, the running median, reservoir sampling and pattern search with a rolling hash, and finish with incremental learning.


Chapter 9: Parallel Algorithms

Parallel algorithms split a computation across several processing units to cut the running time and to make large data sets tractable. We introduce Flynn’s taxonomy, memory architectures and the PRAM model, together with speedup, efficiency, cost, Amdahl’s law and the work–span measures. Worked examples include parallel sum and prefix sums (Hillis–Steele and Blelloch), pipelines and pipelined trees, parallel merge sort, MapReduce and data-parallel matrix multiplication; race conditions, concurrent graph traversal and Java’s parallelism tools round out the chapter.