Algorithms

Undergraduate, Giresun University, Computer Engineering, 2026

algorithms An algorithm is a finite and well-defined sequence of steps for solving a problem or performing a computation. Algorithms form the foundation of software systems and are used in tasks ranging from sorting and searching to graph processing, optimization, text analysis, and scientific computing. This course lays the foundations: how to measure an algorithm’s running time and memory use with asymptotic notation, recurrences and the Master Theorem, and how these tools apply to fundamental problems. It covers sorting and searching, graph algorithms (traversal, shortest paths, minimum spanning trees and network flow) and string algorithms (pattern matching, compression and tries), comparing alternative solutions by correctness, complexity and practical trade-offs. Algorithm-design paradigms, hard problems and other models of computation continue in Advanced Algorithms.


Ders Kitabı

📕 Algoritmalar (PDF, 12 MB)


Başlangıç Kaynakları


Kısım I: Temeller

Bölüm 1: Giriş

Algoritma, bir problemi sonlu sayıda ve iyi tanımlanmış adımla çözen yöntemdir. Bölümde algoritma kavramı ve bir algoritmanın taşıması gereken özellikler gündelik örneklerle tanıtılır; algoritmadan koda geçiş ve algoritma türleri ele alınır. Girdi boyutu, satır satır işlem sayımı ve büyüme tablosuyla sabit, doğrusal, karekök, kübik, faktöriyel ve üstel zaman alan örnekler üzerinden çalışma süresinin girdi boyutuyla nasıl büyüdüğü gösterilir ve Öklid algoritmasının neden hızlı olduğu açıklanır.


Bölüm 2: Algoritma Karmaşıklığı

Bölümde adım sayma, en iyi, en kötü ve ortalama durum, alan karmaşıklığı ile Büyük O, Omega ve Teta gösterimleri ele alınır. Döngülerin toplam formülleriyle çözümlenmesi, yineleme bağıntılarının açma yöntemi ve özyineleme ağacıyla kurulup Ana Teorem ile çözülmesi örnek fonksiyonlar üzerinde işlenir; amortize analize de kısaca değinilir.


Bölüm 3: Sıralama Algoritmaları

Sıralama, verinin belirli bir düzene sokulmasıdır ve pek çok algoritmanın ön adımını oluşturur. Bölümde kabarcık, eklemeli, seçimli ve Shell sıralaması gibi temel yöntemler ile birleştirme sıralaması, hızlı sıralama ve heap sort adım adım izlenir ve Java kodlarıyla çözümlenir. Karşılaştırmaya dayalı sıralamanın Ω(n log n) alt sınırı gösterilir; saymalı, basamak ve kova sıralaması gibi doğrusal zamanlı yöntemlerle gerçek kütüphanelerde kullanılan Timsort tanıtılır. Algoritmalar kararlılık, ek bellek ve karmaşıklık bakımından karşılaştırılır.


Bölüm 4: Arama Algoritmaları

Arama, bir veri kümesinde istenen öğenin yerini bulma problemidir. Bölümde bekçili sürümüyle birlikte doğrusal arama, sıralı dizide ikili arama ve bu yöntemin örtük bir ikili arama ağacı olarak yorumu, tekrarlı öğelerde ilk konumun bulunması anlatılır. Hash fonksiyonları, doğrusal yoklama ve zincirleme ile hash tablosunda arama ve yük faktörünün maliyete etkisi incelenir. Ara değer arama, atlayarak arama ve üstel arama da ele alınır; algoritmalar aynı dizideki yoklama sayılarıyla karşılaştırılır ve hangi durumda hangisinin uygun olduğu tartışılır.


Kısım II: Çizge Algoritmaları

Bölüm 5: Çizge Gezinme Algoritmaları

Çizgeler, yol ağlarından sosyal ağlara kadar düğümler ve bağlantılarla ifade edilebilen her yapıyı modellemekte kullanılır. Bölüm, çizgenin bellekte komşuluk listesi ve matrisiyle gösterimi, derinlik öncelikli (DFS) ve genişlik öncelikli (BFS) gezinme ile başlar. Ardından Tarjan ve Kosaraju algoritmalarıyla güçlü bağlantılı bileşenler, Kahn algoritması ve DFS ile topolojik sıralama ve iki parçalılık testi işlenir.


Bölüm 6: En Kısa Yol Algoritmaları

Bölümde en kısa yol problem türleri ve hepsinin üzerine kurulduğu gevşetme işlemi tanıtılır. Dijkstra algoritması öncelikli kuyrukla, negatif kenarlara izin veren Bellman-Ford algoritması negatif döngü tespitiyle, tüm çiftler arası en kısa yollar Floyd-Warshall algoritmasıyla çözülür. Sezgisel fonksiyonlarla yönlendirilen A* araması ve ağırlıksız çizgede BFS de ele alınır; algoritmalar örnek çizgeler üzerinde karşılaştırılır.


Bölüm 7: Minimum Kapsayan Ağaç Algoritmaları

Minimum kapsayan ağaç, bir çizgenin bütün düğümlerini en düşük toplam ağırlıkla birbirine bağlar. Bölümde kesim ve döngü özellikleri ile bunlara dayanan Kruskal, Prim, Borůvka ve ters silme algoritmaları işlenir. Kruskal için ayrık kümeler (union-find) yapısı yol kısaltma ve rütbeye göre birleştirmeyle anlatılır; Prim algoritmasının dizi ve öncelikli kuyruk sürümleri ile Dijkstra algoritmasından farkı gösterilir.


Bölüm 8: Ağ Akışı

Ağ akışı, kapasiteli bir ağda kaynaktan hedefe gönderilebilecek en büyük akışı arar. Bölümde kapasite ve korunum kısıtları, artık ağ, artış yolu ve darboğaz kavramları ile maksimum akış–minimum kesim teoremi anlatılır. Ford-Fulkerson yöntemi ile Edmonds-Karp, Dinic ve itme–yeniden etiketleme algoritmaları karmaşıklıkları ve uygulamalarıyla birlikte ele alınır.


Kısım III: Dizgi Algoritmaları

Bölüm 9: Dizgi Eşleştirme ve Sıkıştırma

Dizgi algoritmaları metin arama, veri sıkıştırma ve biyolojik dizi çözümlemesi gibi alanların temelini oluşturur. Bölümün ilk kısmında kaba kuvvet, Knuth-Morris-Pratt, Boyer-Moore ve Rabin-Karp örüntü eşleştirme algoritmaları işlenir ve karşılaştırılır. İkinci kısımda kayıpsız sıkıştırma; çalışma uzunluğu kodlaması (RLE), LZW ve LZ78 yöntemleriyle anlatılır.


Bölüm 10: İleri Dizgi Algoritmaları

Bölüm, sözlüksel sıra ile LSD ve MSD basamak sıralamasıyla dizgi sıralamadan başlar. Düzenli ifadeler, sonlu durum makineleri ve örüntü eşleme otomatı, Levenshtein düzenleme uzaklığının dinamik programlamayla hesaplanması, sonek dizisi ve Burrows–Wheeler dönüşümü işlenir.


Bölüm 11: Trie Veri Yapısı

Önek ağacı (trie), dizgileri ortak öneklerini paylaşarak saklar. Bölümde trie ekleme, arama, silme ve otomatik tamamlama işlemleriyle anlatılır; joker karakterli arama ve yazım denetimi örnekleri verilir. Üçlü arama trie’si, sıkıştırılmış trie, sonek trie’si ve birçok örüntüyü tek geçişte arayan Aho–Corasick algoritması da tanıtılır.


Devamı: İleri Algoritmalar

Tasarım paradigmaları (böl ve fethet, açgözlü algoritmalar, dinamik programlama), zor problemler (geri izleme, dal sınır, yaklaşım algoritmaları) ve diğer hesaplama modelleri (rastgele, çevrim içi ve paralel algoritmalar) İleri Algoritmalar dersinde işlenir.


Part I: Foundations

Chapter 1: Introduction

An algorithm is a method that solves a problem in a finite number of well-defined steps. This chapter introduces the idea of an algorithm and the properties every algorithm must have through everyday examples, then looks at how an algorithm becomes code and at the main kinds of algorithms. Using input size, line-by-line operation counts and a growth table, we follow examples that run in constant, linear, square-root, cubic, factorial and exponential time to see how running time grows with the input, and we explain why Euclid’s algorithm is so fast.


Chapter 2: Algorithm Complexity

This chapter gives the tools for measuring cost: counting steps, best, worst and average cases, space complexity, and Big O, Omega and Theta notation. We analyze loops with summation formulas, set up recurrences by unrolling and with recursion trees, and solve them with the Master Theorem on a series of sample functions. A brief look at amortized analysis closes the chapter.


Chapter 3: Sorting Algorithms

Sorting puts data into a given order and is the first step of many other algorithms. We trace the elementary methods (bubble, insertion, selection and Shell sort) and then merge sort, quicksort and heapsort step by step, analyzing each with Java code. The chapter proves the Ω(n log n) lower bound for comparison sorting, introduces linear-time methods such as counting, radix and bucket sort along with Timsort, the algorithm real libraries use, and compares all of them by stability, extra memory and complexity.


Chapter 4: Searching Algorithms

Searching is the problem of locating a wanted item in a collection of data. We cover linear search and its sentinel version, binary search on a sorted array and its reading as an implicit binary search tree, and finding the first position among duplicates. Hash functions, hash-table lookup with linear probing and with chaining, and the effect of the load factor on cost come next, followed by interpolation, jump and exponential search. The algorithms are compared by the number of probes they make on the same array, with a discussion of which one suits which situation.


Part II: Graph Algorithms

Chapter 5: Graph Traversal

Graphs model anything that can be described as nodes and connections, from road networks to social networks. The chapter starts with storing a graph as an adjacency list or an adjacency matrix and with depth-first (DFS) and breadth-first (BFS) traversal. It then covers strongly connected components with Tarjan’s and Kosaraju’s algorithms, topological sorting with Kahn’s algorithm and with DFS, and testing whether a graph is bipartite.


Chapter 6: Shortest Paths

We introduce the kinds of shortest-path problems and the relaxation step that all shortest-path algorithms are built on. Dijkstra’s algorithm is implemented with a priority queue, Bellman–Ford handles negative edges and detects negative cycles, and Floyd–Warshall computes shortest paths between all pairs. A* search guided by heuristic functions and BFS on unweighted graphs are also covered, and the algorithms are compared on sample graphs.


Chapter 7: Minimum Spanning Trees

A minimum spanning tree connects all the vertices of a graph at the lowest possible total weight. The chapter presents the cut and cycle properties and the algorithms built on them: Kruskal, Prim, Borůvka and reverse-delete. For Kruskal we develop the disjoint-set (union-find) structure with path compression and union by rank; for Prim we give both the array and the priority-queue versions and point out how it differs from Dijkstra’s algorithm.


Chapter 8: Network Flow

Network flow asks for the largest flow that can be sent from a source to a sink through a network with capacities. We define capacity and conservation constraints, the residual network, augmenting paths and bottlenecks, and prove the max-flow min-cut theorem. The Ford–Fulkerson method, Edmonds–Karp, Dinic’s algorithm and push–relabel are then studied together with their complexity and applications.


Part III: String Algorithms

Chapter 9: String Matching and Compression

String algorithms underlie text search, data compression and the analysis of biological sequences. The first half of the chapter studies and compares the brute-force, Knuth–Morris–Pratt, Boyer–Moore and Rabin–Karp pattern-matching algorithms. The second half turns to lossless compression with run-length encoding (RLE), LZW and LZ78.


Chapter 10: Advanced String Algorithms

The chapter opens with string sorting: lexicographic order and LSD and MSD radix sort. It goes on to regular expressions, finite-state machines and pattern-matching automata, and computes the Levenshtein edit distance with dynamic programming. Suffix arrays and the Burrows–Wheeler transform complete the chapter.


Chapter 11: Tries

A trie, or prefix tree, stores strings so that common prefixes are shared. We implement insertion, search, deletion and autocomplete, and apply tries to wildcard search and spell checking. Ternary search tries, compressed tries, suffix tries and the Aho–Corasick algorithm, which finds many patterns in a single pass over the text, round out the chapter.


Next: Advanced Algorithms

Design paradigms (divide and conquer, greedy algorithms, dynamic programming), hard problems (backtracking, branch and bound, approximation algorithms) and other models of computation (randomized, online and parallel algorithms) are covered in Advanced Algorithms.