Veri Yapıları ve Algoritmalar I
Karmaşıklık analizi, bağlı listeler, yığın, kuyruk, özyineleme, arama ve sıralama.
Kaynak kitap: Data Structures & Problem Solving Using Java (Mark Allen Weiss)
- 1. haftaIntroduction to Data Structures and Algorithms, Complexity Analysis
- Karmaşıklık analizi: Big-O, Ω, ΘBir kod parçasının kaç işlem yaptığını saymayı ve sonucu Big-O ile yazmayı öğrenirsin. Vizede her yıl gelen “What is the running time?” sorularının temeli.
- 2. haftaIntroduction to Linked Lists
- Tek yönlü bağlı liste (singly linked list)Node sınıfı, başa/sona/araya ekleme, silme ve gezinme. Vizede “listenin son hali ne?” ve “şu metodu yaz” sorularının kaynağı.
- 3. haftaDoubly Linked Lists, Ordered Linked Lists
- Çift yönlü, sıralı ve dairesel listelerprev referansı olan çift yönlü liste, elemanları sıralı tutan ordered list ve sonu başa bağlanan dairesel liste. Sınavda referans güncelleme izleri ve insertSorted metodu sorulur.
- 4. haftaLinked List Applications and Review
- Bağlı liste uygulamaları ve tekrarListeyi ters çevirme, ortayı bulma, döngü tespiti, iki sıralı listeyi birleştirme ve liste ile dizi karşılaştırması. Vizenin “write a method” sorularının çoğu bu dört algoritmadan gelir.
- 5. haftaStacks
- Yığın (stack): dizi ve bağlı liste ileLIFO mantığı, push/pop/peek, dizi ve bağlı liste ile iki gerçekleme, overflow ve underflow. Sınavda işlem dizisinden sonra yığının hali ve pop sırası soruları gelir.
- 6. haftaStacks for Algebraic Operations
- Yığınla ifade işlemleri: parantez, infix → postfix, postfix hesaplamaParantez dengesini kontrol etmek, infix ifadeyi öncelik kurallarıyla postfix'e çevirmek ve postfix ifadeyi yığınla hesaplamak. Sınavda adım adım yığın tablosu çizdirilir.
- 7. haftaQueues
- Kuyruk (queue): dairesel dizi ve bağlı liste ileFIFO mantığı, enqueue/dequeue/peek, dizinin başa doğru kaymasını önleyen dairesel tampon ve head/tail'li bağlı kuyruk. Sınavda işlem dizisinden sonra dizinin ham hali ve front/rear değerleri sorulur.
- 8. haftaQueues II: Circular and Priority Queues
- Kuyruk II: dairesel indeks hesabı, deque, öncelik kuyruğucount tutmayan dairesel kuyruğun boş/dolu formülleri, iki uçlu kuyruk (deque), öncelik kuyruğunun (priority queue) mantığı ve kuyrukla simülasyon. Sınavda formülle indeks bulma ve simülasyon izi sorulur.
- 9. haftaData Structure Classes in Java
- Java'nın hazır veri yapıları: CollectionsArrayList, LinkedList, ArrayDeque, Stack, Queue/Deque arayüzleri, Iterator ve HashMap. Elle yazdığın yapıların Java'daki karşılıkları ve hangi işte hangisini seçeceğin. Sınavda “what is printed” ve yapı seçimi soruları gelir.
- 10. haftaRecursion
- Özyineleme (recursion)Taban durum ve özyinelemeli adım, çağrı yığını izleri, bağlı listede özyinelemeli metotlar ve geri izlemeye (backtracking) giriş. Sınavda “what is printed”, çağrı sayısı ve özyinelemeli metot yazma soruları gelir.
- 11. haftaRecursive Complexity
- Özyinelemeli karmaşıklık: yineleme bağıntılarıÖzyinelemeli bir metodun süresini T(n) bağıntısıyla yazmak ve açılım, özyineleme ağacı ve master teoremi ile çözmek. Sınavda “write the recurrence and give the Big-O” soruları gelir.
- 12. haftaSearching Algorithms
- Arama algoritmaları: doğrusal, ikili, interpolasyonDoğrusal arama, ikili aramanın döngülü ve özyinelemeli halleri, karşılaştırma sayıları ve interpolasyon aramasının fikri. Sınavda low/mid/high iz tablosu ve en kötü durumda karşılaştırma sayısı sorulur.
- 13. haftaSorting Algorithms I
- Sıralama I: bubble, selection, insertionÜç temel O(n²) sıralama algoritması, her geçişten sonra dizinin hali, karşılaştırma ve takas sayıları ve kararlılık (stability). Sınavda “show the array after each pass” sorusu neredeyse garanti.
- 14. haftaSorting Algorithms II
- Sıralama II: merge sort, quick sort, heap sortBöl ve yönet ile O(n log n) sıralama: merge sort'ta birleştirme adımları, quick sort'ta partition izi, heap sort'a genel bakış ve bütün sıralamaların karşılaştırma tablosu. Final sınavının sıralama sorularının çoğu buradan.