Veri Yapıları ve Algoritmalar II
Ağaçlar, BST, AVL, heap, hashing, graflar ve açgözlü algoritmalar.
Kaynak kitap: Data Structures & Problem Solving Using Java (Mark Allen Weiss)
- 1. haftaIntroduction and Sorting Algorithms.
- Sıralama algoritmaları: analiz, alt sınır, counting ve radix sortMerge sort, quicksort ve heapsort'un adım adım izi ve Big-O analizi, karşılaştırmalı sıralamanın n log n alt sınırı, karşılaştırmasız counting ve radix sort.
- 2. haftaIntroduction to different tree structures.
- Ağaçlar: terminoloji, ikili ağaçlar ve gezinmelerKök, yaprak, derinlik, yükseklik gibi terimler, genel ve ikili ağaçlar, preorder/inorder/postorder/level-order izleri ve ifade ağaçları.
- 3. haftaIntroduction to binary search trees.
- İkili arama ağaçları: arama, ekleme, silmeBST özelliği, arama yolu, ekleme sırasının ağacın şeklini nasıl belirlediği, silmenin üç durumu, inorder successor ve yükseklik analizi.
- 4. haftaImplementing binary search tree using Java.
- BST'yi Java ile yazmakGeneric BinarySearchTree sınıfı: düğüm sınıfı, özyinelemeli insert/remove/contains/findMin/findMax, gezinme, size ve height; sınavda istenen 'write a method' kalıpları.
- 5. haftaIntroduction to balanced trees and implementing AVL balanced tree structure using Java.
- AVL ağaçları: denge faktörü ve rotasyonlarBST'yi O(log n)'de tutan AVL kuralı, LL/RR/LR/RL rotasyonları ve sınavın klasik sorusu: bu sırayla eklenince ağaç neye benzer?
- 6. haftaUsing other balanced tree structure using Java.
- Diğer dengeli ağaçlar: red-black, 2-3, B-ağacı, splayRed-black ağacın beş kuralı ve ekleme durumları, 2-3 ağacında bölünme, B-ağacının diskteki rolü ve splay fikri. Sınavda renkli ağaç çizme ve bölünme izi sorusu buradan.
- 7. haftaUsing heap structure and implementing them using Java.
- İkili heap: dizi gösterimi, percolate, buildHeap, heapsortBinary heap'in dizi içinde tutulması, insert (percolate up) ve deleteMin (percolate down) izleri, O(n) buildHeap ve heapsort. Sınavın klasik sorusu: şu işlemlerden sonra dizi neye benzer?
- 8. haftaUsing heaps as priority queues. Midterm.
- Öncelik kuyruğu: heap ile PriorityQueueBinary heap'in öncelik kuyruğu olarak kullanımı, Java'nın PriorityQueue sınıfı, Comparator ile sıralama ve k-en-küçük, k listeyi birleştirme, iş zamanlama uygulamaları.
- Vize tekrarı: sıralama, ağaçlar, BST, AVL, heap1-8. haftaların tek sayfada özeti: Big-O tablosu, her konunun iz sürme kalıbı ve karışık vize soruları.
- 9. haftaAnalyzing and implementing hashing algorithms.
- Hashing: zincirleme, açık adresleme ve rehashHash fonksiyonu, doluluk oranı, ayrı zincirleme, doğrusal/karesel yoklama, çift hashing, tembel silme ve rehash; sınavın klasik 'tabloyu doldur' sorularının adım adım çözümü.
- 10. haftaAnalyzing and implementing graph structure using Java.
- Graflar: gösterim, BFS, DFS ve topolojik sıralamaGrafı komşuluk matrisi ve listesiyle saklamak, BFS ve DFS ile gezmek, bağlı bileşenleri saymak ve DAG'ı topolojik sıraya dizmek; sınavın 'ziyaret sırasını yaz' sorularının kuralları.
- 11. haftaAnalyzing and implementing graph algorithms.
- En kısa yol ve döngü tespiti: BFS, Dijkstra, Bellman-FordAğırlıksız grafta BFS ile, pozitif ağırlıkta Dijkstra ile, negatif kenarda Bellman-Ford ile en kısa yol; yönlü ve yönsüz grafta döngü bulma. Sınavın tablo doldurma soruları buradan gelir.
- 12. haftaAnalyzing and implementing greedy algorithms.
- Açgözlü algoritmalar: etkinlik seçimi, kesirli sırt çantası, para üstüGreedy fikri, ne zaman doğru sonuç verdiği ve ne zaman çöktüğü. Etkinlik seçimi, kesirli ve 0/1 sırt çantası, para üstü örnekleri ve karşı örnekleriyle.
- Huffman kodlaması: ağaç kurma, kodlar, toplam bitEn küçük iki frekansı birleştirerek Huffman ağacı kurma, kodları ağaçtan okuma, toplam bit ve ortalama hesabı, çözme (decode). Sınavda neredeyse her dönem çıkan iz sorusu.
- 13. haftaAnalyzing and implementing greedy algorithms. Quiz.
- Minimum yayılan ağaç: Prim, Kruskal ve union-findAğırlıklı yönsüz grafta tüm düğümleri en ucuza bağlayan ağaç. Kruskal'ı union-find ile, Prim'i adım tablosuyla izlemeyi ve quiz tipi soruları çözmeyi öğrenirsin.
- 14. haftaReview.
- Final tekrarı: hangi yapı, hangi algoritma, hangi Big-ODönemin tamamı tek sayfada: problem tipine göre yapı/algoritma seçme tablosu, bütün işlemlerin Big-O özeti ve her konudan birer karışık final sorusu.