Polito DSA için Academy Lab Çalışma Rotası: Linked List’ten Graph’a

Polito DSA çalışırken bir linked list animasyonunu anlayıp aynı işlemi boş editörde yazamamak sık karşılaşılan bir durumdur. Görseli takip etmek, algoritmanın kararını kendi başınıza üretebildiğiniz anlamına gelmez. Bu rota her konuda dört kanıt üretmenizi ister: bir sonraki adımı tahmin etmek, trace ile karşılaştırmak, C uygulamasını yazmak ve sınır durumlarını bağımsız test etmek.

Buradaki görevler Websoftik Academy'nin özgün çalışma önerileridir. Dersin kapsamı ve grup bilgisi için Polito Algorithms and Data Structures 2026/27 rehberini; dönem takvimi için 12 haftalık çalışma planını kullanabilirsiniz. Bu yazının odağı, bir çalışma oturumunun sonunda elinizde ne bulunacağıdır.

1. Çalışma Dosyanızı Dört Kanıtla Kurun

Her konuya bir sayfa ayırın: girdi, tahmin, gözlenen trace, C test sonucu. İlk denemede Lab'i durdurun; sonucu ve değişecek state'i yazın. Sonra tek adım ilerleyip farkı açıklayın. En sonunda kaynak kodu kapatarak kendi uygulamanızı derleyin. Hazır görselleştirmedeki başarıyı kendi kodunuzun doğruluğu olarak kaydetmeyin.

Algorithm Visualizer'ın kaynak satırı ile veri durumunu birlikte izleten C örneklerinde, önce aktif satırın hangi değişikliği yapacağını söyleyin. Kaynak ve trace'in eşleşmesi, değişkeni yanlış anda okumayı fark etmenize yardımcı olur. Farklı örnek seçeneği bulunan algoritmalarda girdiyi değiştirip aynı kuralı yeniden sınayın.

Bir basamağı tamamlamak için iki küçük girdide yardımsız tahmin, çalışan bir C fonksiyonu ve en az üç sınır testi isteyin. Temel pointer veya fonksiyon sorularında takılıyorsanız DSA için C temeli kontrolüne dönün. Bu ölçüt bir not tahmini değil, sonraki oturumu seçme aracıdır.

2. Linked List: Bağlantıyı ve Belleği Ayrı Kontrol Edin

Özgün başlangıç göreviniz 4 → 9 → 12 listesinden 9'u silmek olsun. Önce prev, target ve target->next adreslerini çizip hangi bağlantının değişeceğini tahmin edin. Linked List Lab rehberinden pointer adımlarını karşılaştırın: bağlantıyı değiştirmek ve belleği serbest bırakmak iki ayrı iştir.

C'de ilk eşleşmeyi silen bir fonksiyon yazın. Baş düğüm değişebileceği için yeni head'i döndürmek veya pointer-to-pointer kullanmak arasında bilinçli bir arayüz seçin. Fonksiyonun sonucu “silindi/silinmedi” bilgisini de taşısın. İşlemden sonra erişilebilir değerleri yazdırın; yalnızca eleman sayısına güvenmeyin.

Testleriniz boş liste, tek elemanın silinmesi, bulunmayan değer, ilk ve son düğüm olsun. Tekrarlı değerlerde yalnız ilk eşleşmenin silindiğini doğrulayın. Çıktınız bir önce/sonra adres çizimi, silme sözleşmesi ve beş testin beklenen sonucudur. Bellek incelemesini desteklenen yerel araçla yapabiliyorsanız sızıntı ve serbest bırakılmış belleğe erişimi de kontrol edin.

3. Stack ve Queue: Aynı Düğümlerden Farklı Davranış Üretin

İstekler 21, 34 ve 55 sırasıyla gelsin. “En son geleni geri al” için stack, “ilk geleni işle” için queue seçin. Kâğıtta üç ekleme ve iki çıkarma sonrasındaki değerleri tahmin edin. Linked List Lab'in ilgili akışında bağlantı değişikliklerini izleyip neden bir modelin 55'i, diğerinin 21'i önce verdiğini açıklayın.

Kendi C sürümünüzü header, uygulama ve istemci dosyalarına ayırın. İstemci push/pop veya enqueue/dequeue çağırabilsin; node alanlarını değiştirmesin. Boş yapıdan çıkarma işleminde hata nasıl bildirilir, çıktı parametresi değişir mi ve düğüm belleğini kim serbest bırakır? Bu kararları koddan önce yazın.

Boş yapı, tek elemanın çıkarılması ve boşaldıktan sonra tekrar ekleme testlerini çalıştırın. Queue için son eleman çıkınca head ile tail'in birlikte tutarlı kaldığını gösterin. Tamamlanma çıktınız aynı işlem dizisinin iki farklı sonucu, kullanılan arayüz ve sınır testi raporudur.

4. Recursion: Çağrı Sayısını Stack Derinliğinden Ayırın

Önce [3, 5, 2] array toplamı için taban durumu ve her çağrıda küçülen problemi yazın. Çağrı parametrelerini, bekleyen toplamları ve dönüş sırasını tahmin edin. Recursion Lab'in array-sum örneğinde call stack ile bütün çağrı ağacının aynı görünüm olmadığını karşılaştırın.

Ardından bu mantığı kendi C linked-list toplam fonksiyonunuza taşıyın; Lab'deki array örneği ile bağımsız liste uygulamanızın farklı temsiller olduğunu açıkça kaydedin. Boş, tek elemanlı ve negatif değer içeren listede test edin. Toplamın kullandığınız sayı tipinin aralığında kaldığı küçük girdiler seçin. Çağrı sayısını ve en fazla aynı anda açık frame sayısını ayrı kaydedin. Bu görevde ikisi de liste uzunluğuyla büyür; her recursive algoritma için böyle olmak zorunda değildir.

Ek görev olarak iki elemanlı bir kümenin alt kümelerini üretin. Seçimden dönüşte hangi state'in geri alınacağını tahmin edin ve boş küme dâhil dört sonucu kontrol edin. Çıktınız taban durum, küçülme gerekçesi ve bir çağrı/dönüş çizimidir.

5. Sorting: Son Diziden Önce Turun Kuralını Doğrulayın

Insertion Sort için [4, 2, 2, 7, 1] girdisini kullanın. İkinci 2 işlendiğinde hangi değerlerin kayacağını ve eşit anahtarın nereye yerleşeceğini tahmin edin. Sorting Lab'de pass ile tek karşılaştırma/taşıma adımını ayrı izleyin. Her turun sonunda sıralı prefix sınırını işaretleyin.

C'de küçük bir insertion sort yazın; koşuldaki > ile >= farkını eşit anahtarlı, farklı kimlikli kayıtlarla inceleyin. Yalnız tam sayı çıktısı eşit kayıtların sırasını göstermez. Boş dizi, tek eleman, zaten sıralı, ters sıralı ve bütün anahtarları eşit girdiler seçin.

Çıktınız sıralı prefix çizimi ve her testte karşılaştırma/taşıma sayısı olsun. Ardından Visualizer'daki C sorting örneğinde kaynak satırını state değişimiyle eşleştirin. Daha az adım gördüğünüz küçük bir girdiden genel Big-O sonucu çıkarmayın; Complexity rehberiyle girdi ailesini ve büyüme koşulunu açıklayın.

6. BST: Sıralama Kuralı Dengeli Ağaç Garantisi Değildir

Aynı değerleri iki sırayla ekleyin: 1, 2, 3, 4, 5 ve 3, 1, 5, 2, 4. Önce iki ağacı ve 5 için arama yolunu çizin. Trees & BST Lab üzerinde şeklin arama yolunu nasıl değiştirdiğini izleyin. BST kuralı korunurken ağaç bir zincire dönüşebilir; sıradan BST otomatik dengelenmez.

C uygulamanızda ekleme, arama ve inorder traversal yazın. Duplicate key'i reddetmek veya belirli tarafa yerleştirmek gibi bir politika seçin. Her iki ekleme sırasının inorder çıktısı aynı sıralı anahtarları vermeli, yükseklikleri farklı olabilmelidir. Aramanın maliyetini yüksekliğe bağlı O(h) olarak açıklayın; dengesiz durumda h doğrusal büyüyebilir.

Boş ağaç, bulunmayan anahtar ve tekrarlı anahtar testlerini ekleyin. Sonraki oturumda root silmeyi çalışın. Çıktınız iki ağaç çizimi, arama yolu ve kendi duplicate sözleşmenizdir.

7. Heap: Öncelik Kuyruğunu Sıralı Koleksiyon Sanmayın

Geçerli bir min heap olan [2, 5, 3, 9, 7, 4] dizisine 1 eklenince izlenecek parent yolunu tahmin edin. Heap Lab'de array indeksi ile ağaç düğümünü birlikte okuyun. Sonuç yalnız parent-child öncelik ilişkisini sağlamalıdır; array'in tamamı sıralı olmak zorunda değildir.

C'de sabit kapasiteli min-priority queue kurup insert ve extract-min uygulayın. İndekslemenin sıfırdan mı birden mi başladığını yazın. Art arda extract işlemleri sıralı çıkış verebilir; array'i doğrudan gezmek aynı garantiyi vermez. Eşit öncelikli kayıtlarda geliş sırasını korumak istiyorsanız ikinci bir karşılaştırma anahtarı tanımlayın.

Boş heap, dolu kapasite, tek eleman ve eşit öncelikler testleri çalışsın. Çıktınız sift-up yolu, her işlem sonrası heap kontrolü ve çıkarılan sıra olsun. Keyfi kimlikle aramayı da hızlı yapacağı varsayımını ayrıca sorgulayın.

8. Hash Table: Silmeden Sonra Arama Yolunu Koruyun

Yedi slot ve h(k)=k mod 7 ile 10, 17, 24 anahtarlarını linear probing kullanarak ekleyin. Üç anahtarın başlangıç slotunu ve yerleşeceği yolu önceden yazın. 17 silinince 24'ün bulunup bulunmayacağını tahmin edin. Hash Tables Lab ile EMPTY ve tombstone arasındaki farkı karşılaştırın.

C'de EMPTY, OCCUPIED ve DELETED durumlarını ayrı tutan küçük bir tablo yazın. Arama en fazla kapasite kadar slot denesin; dolu tabloda sonsuz döngüye girmesin. Silinmiş slotu tekrar kullanmadan önce aynı anahtarın ileride bulunmadığını kontrol etmek duplicate davranışı açısından önemlidir.

Collision, silinmiş slotun arkasında arama, bulunmayan anahtar ve dolu tablo testlerini ekleyin. Çıktınız probe listeleri ve işlem sayılarıdır. İyi dağılım ve kontrollü doluluk altında beklenen maliyet O(1) olabilir; kapasitesi m olan açık adreslemeli tabloda en kötü arama O(m) maliyetine ulaşabilir. Eleman sayısı n ve m=Θ(n) olduğunda bu sınır O(n) olarak ifade edilir. Anahtar uzunluğu ve yeniden büyütme maliyetini varsayımlarınıza ayrıca yazın.

9. Graph: Algoritmadan Önce Yolun Anlamını Seçin

A-B, A-C, B-D ve C-D kenarları olan ağırlıksız, yönsüz bir graph, ayrıca izole E vertex'i çizin. A'dan BFS için mesafeleri ve queue durumunu tahmin edin. B ile C'nin sırası komşu sırasına bağlı olabilir; mesafeler B/C için 1, D için 2 olmalıdır. Graph Lab'de frontier, visited ve parent bilgilerini birlikte karşılaştırın.

C'de adjacency list üzerinde BFS yazın; vertex'i kuyruğa eklerken keşfedilmiş işaretleyerek tekrar eklemeyi engelleyin. İzole vertex, cycle, kaynakla aynı hedef ve ulaşılamayan hedef testleri olsun. Çıktınız mesafe tablosu, parent'tan kurulan bir yol ve test raporudur.

Sonra A-B ağırlığını 9, A-C ve C-B ağırlıklarını 2 yapın. BFS doğrudan A-B'yi en az kenarlı yol olarak bulabilir; ağırlık toplamı 9'dur. Dijkstra A-C-B yoluyla 4 bulur. BFS ağırlıksız ya da eşit ağırlıklı durumda en kısa yolu destekler; Dijkstra'nın standart garantisi negatif olmayan ağırlıklara dayanır. Negatif kenarlı örnekte önce algoritma seçimini yeniden değerlendirin.

10. Karma Görevi Çözün ve Eksik Basamağı Ölçün

Son görevde 2026/27 DSA rehberindeki kampüs istekleri örneğini bağımsız bir C mini projesine genişletin. Kimlik, öncelik ve geliş sırasını aynı veri modelinde tutun. En öncelikliyi çıkarma, kimlikle bulma ve geliş sırasıyla raporlama gereksinimlerini ayrı yazın. Tek yapının her işlemi hızlandıracağını varsaymadan iki tasarım önerin. Küçük girdide sonuçları tahmin edin, ilgili trace'lerle karşılaştırın ve bir tasarımı C ile uygulayın.

Kontrol listeniz dört maddeden oluşsun: sonuç doğru mu; yapısal kural korunuyor mu; bellek sorumluluğu açık mı; maliyet varsayımları gerekçeli mi? Tekrarlı kimlik, eşit öncelik ve boş koleksiyon testlerini kaydedin. 48 saat sonra farklı veriyle yardımsız tekrarlayın. Hata hangi basamakta çıktıysa bir sonraki oturumu oraya ayırın.

13 Ekim 2026'da doğrulanan 01URN Algorithms and Data Structures 2026/27 resmî kılavuzu, C uygulaması, veri yapıları ve algoritma analizini birlikte ele alır. Buradaki sıra bağımsız bir öneridir; sınav formatı ve zorunlu görevler için kendi grubunuzun duyurularını izleyin.

Araçları Academy Lab merkezinden açabilirsiniz. Düzenli olarak aynı tasarım veya C hatasına dönüyorsanız çalışma dosyanızla Polito DSA özel ders sayfasına başvurabilirsiniz. Diğer ders rotaları Polito ders merkezinde yer alır.