Algorithms
Undergraduate, Giresun University, Computer Engineering, 2026
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ı
Başlangıç Kaynakları
- Algoritmalarda Önemli İsimler (HTML)
- Algoritmalar İçin Ön Bilgiler (HTML)
- Dersin Haritası (HTML)
- Terim Sözlüğü (HTML)
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Algoritma Karmaşıklığı Analizi
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Asimptotik Büyüme Gezgini · Özyineleme ve Ana Teorem
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Sıralama Algoritmaları · Sıralama Yarışı · Sıralama Özellikleri Laboratuvarı
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Arama Algoritmaları · Hash ve Ara Değer Arama · Üstel Arama
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Çizge Gezinme Simülatörü · Çizge Yapısı Algoritmaları Simülatörü · İki Parçalılık, Döngü ve Köprü Simülatörü
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: En Kısa Yol Algoritmaları Simülatörü · A* Yol Bulma Simülatö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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Minimum Kapsayan Ağaç Simülatörü
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Ağ Akışı Simülatö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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Dizgi Eşleştirme Algoritmaları · Önek Fonksiyonu ve Z Algoritması · Dizgi Sıkıştırma Algoritmaları
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Dizgi Sıralama: LSD Basamak Sıralaması · Sonlu Durum Makinesiyle Dizgi Ayrıştırma · Dizgi Benzerliği: Levenshtein Uzaklığı · Dizgi Dönüşümü: Burrows–Wheeler Dönüşümü
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.
- 🖼️ Sunum · 📄 PDF · 📖 Ders notu · 📝 Sorular · 💻 Kod
- 🕹️ Simülatörler: Trie ve Sonek Algoritmaları
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.