İstanbul Ticaret Üniversitesi

 

Veri Yapıları ve Algoritma Analizi (data structures and Algorithm Analysis)

 

Dersi Veren: Şadi Evren ŞEKER (Yük. Müh.)

Web Sitesi: www.sadievrenseker.com/vy

Email Adresi:vy [at] sadievrenseker.com

Dersin Amacý:

Temel mühendislik nosyonlarýndan birisi olan veriyapýlarý bilginsin öðrencilere kazandýrýlmasý ve programlama felsefesine hâkim hale getirilmesi. Algoritma tasarýmýnda dikkat edilmesi gereken konularýn öðretilmesi ve bu sayede problem analizinde farklý bir bakýþ açýsý olan analiz ve tasarým iyileþtirlmesi (optimisation) mantýðýnýn geliþtirilmesi.

Günümüzde en çok kullanýlan C-Syntax�ine öðrencilerin alýþtýrýlmasý ve bu sayede Java, C++ gibi dillere kolay geçiþ yapabilecek hale getirilmesi. Temel veri yapýlarýnýn tanýtýlmasý ve kullanabilecek seviyeye getirilmesi.

Eðitim hayatlarýnýn geri kalanýnda ve mühendislik hayatýnda gerekecek matematiksel alt yapýnýn kazandýrýlmasý ve algoritma tasarýmýnda kullanýr hala getirilmesi.



Olasý Ders Ýçeriði:
  • Pointer Ýþlemleri
  • Struct ve Composition (yapý ve oluþum)
  • Linked List (baðlý liste) ve örnek kodlar
  • Soyut veri tipleri (Abstract Data Types)
  • Stack (Yýðýn)
  • Queue (sýra)
  • Ara sýnav
  • (Aðaçlar) , Ýkili Aðaçlar , Ýkili Arama Aðacý
  • Graphics (Grafikler)
  • Shortest Path & Minimum Spanning Tree (En kýsa yol ve asgari tarama aðacý)
  • Map Accumulate ve Filter fonksiyonlarýnýn aðaç ve baðlý listede kullanýmý
  • Final
    Yukarýdaki içerik tahmini içerik olup öðrenci performansýna göre deðiþtirilebilir.

    Derste Yazýlan Kodlar
    1. Hafta: Bağlı Listelere Giriş
  • 2. Hafta: Bağlı Listelerden Silme
  • 3. Hafta: Bağlı Liste Sıralı veri Girişi, ADT ve Dairesel Bağlı Liste
  • 4. Hafta: Çift bağlı listelerde ekleme ve silme işlemi , Ödev1'in çözümü
  • 5. Hafta: Bağlı Liste ve Dizi kullanarak Stack(Yığın) kodlanması, Bağlı liste kullanarakQueue (Sıra) kodlanması
  • 6. Hafta: Tekrar konuları ve 2. ödevin çözümü
  • 7. Hafta vize imtehanı ve çözümü

  • 8. Hafta ağaç yapısı ve ikili arama ağacı kodlanması (binary search tree)
  • 9. Hafta (telafi dersi) ağaçtan veri silen kod (ayrıca dikişli ağaç benzeri ufak bir uygulama)
  • 10. Hafta ,Heap kodları 
  • 11. Hafta, Kruskal asgari tarama ağacı kodu

  • Duyurular:
  • Vize açık kitaptır, fotokopi ve bilgisayar çıktılarının kullanılmayacaktır, kendi notlarınız veya istediğiniz kitapları sınava getirebilirsiniz.
  • 22 Nisan perşembe yapılamayan dersler, 28 Nisan çarşamba günü yapılacaktır (9.00 sabah , 12. 00 öğle seansının telafi saatleridir)
  • Final Kapalı kitaptır, ders notu, kitap veya herhangi başka bir kaynağın sınavda kullanılmasına izin verilmeyecektir.
  • Proje teslimleri için son gün 28 Mayıs'tır. Bu tarihte gece yarısına kadar maillerinizi kabul edeceğim. Gece yarısından sonra gelen mailler kabul edilmeyecektir. Lütfen son saati, hatta son günü beklemeyiniz.
  • Projenizde en az bir ağaç kodlaması VE stack,queue,heap,bst yapılarından birisini ADT olarak kullanmanız gerekir. Bu projedeki en az gereksinimdir.
  • Dekanlığın yaptığı sözlü tebligat gereği, final notlarınızı öğrenmeniz gerektiğini düşünmeme rağmen bu sene final notlarınızı öğrenemeyeceksiniz. Dekanlık öğrnecilerin final notlarını öğrenmesini istemiyor. Dolayısıyla ancak harf notlarınıza itiraz edebileceksiniz. Yönetmelikte yazdığı üzere final sınavından sonra 1 hafta içerisinde finallerinizi okumam ve daha sonra da harf notlarınızı teslim etmem gerekiyor. Ayrıca sizin notunuza itiraz için 7 gün süreniz bulunuyor.Lütfen bu itiraz süresini iyi değerlendirip notlarına itiraz etmek isteyenler süreyi geçirmeden dekanlığa itirazda bulunsunlar (bana itrazda bulunmayın çünkü harf notlarınızın ilanından sonra dekanlığa itiraz etmeniz gerekiyor, bu konu 29. maddede geçmektedir) (ayrıca her öğrenciye bütün yönetmeliği dikkatlice okumasını tavsiye ederim)

    Proje demolarınız için radevü alabileceğiniz takvim programı açılmıştır. Bu bağlantıdan erişebilirsiniz. Lütfen duyuruları dikkatle okuyarak randevü alınız.

  • Ödevler:
  • Ödev 1 : 
  • Elemanları tam sayılardan (integer) oluşan bir bağlı liste üzerindeki en küçük ve en büyük sayı arasında kaç eleman olduğunu saydıran program yazınız.
  • Örnek 1:
  • 13 → 17 → 19 → 96 → 76 → 89 → -2 → -11 → 0 → 56
  • Yukarıdaki bağlı listede en büyük sayı 96 , en küçük sayı -11 ve aralarında 3 eleman bulunmaktadır. 
  • Örnek 2:
  • 131 → 117 → -19 → 95 → 76 → 189 → -2 → -11 → 0 → 1156
  • Yukarıdaki bağlı listede en büyük sayı 1156 , en küçük sayı -19 ve aralarında 6 eleman bulunmaktadır. 
  • Ödev 15 mart pazartesi gece yarısına kadar dersin mail adresine teslim edilecektir.Geç teslimler kabul edilmeyecektir.
  • Ödevinizi, isminizi içeren bir rar dosyası olarak postanıza iliştiriniz. Örneğin "sadievrenseker.rar"  seklinde ve ödevinizin kaynak koduna yorum olarak mutlaka isminizi ve okul numaraınızı yazınız. 
  • Ödev 2:
  • Kullanıcıdan bir sayı alarak bu sayı kadar eleman içeren, aşağıdaki temsili resimde 8 sayısı için görüldüğü gibi bir dairesel bağlı liste (circular linked list) oluşturun. 

  • Bu dairesel bağlı liste üzerinde bir başlangıç numarası ve atlama miktarını kullanıcıdan alın. 
  • Yukarıda başlangıç sayısı 2 ve atlama miktarı 3 olarak verilmiştir. Bu durumda 2. elemandan başlanarak 3 eleman sayılmış ve bu eleman (5. eleman) listeden silinmiştir. Ardından tekrar 3 eleman sayılmış ve 8. eleman da listeden silinmiştir. Bu işlemin dairesel listede tekrarlanması sonucunda ikinci geçişte aşağıdaki görüntü elde edilir:
  • İşlem tekrarlanınca nihayi hali aşağıdaki şekilde olur:
  • Yukarıdaki bu son şekilde, 2 adet eleman kalmış (1 ve 6) ve diğer elemanlar sırayla silinmiştir.
  • Bu ödevde sizden istenen listedeki eleman sayısını, kaçıncı elemandan başlanacağını ve kaçar eleman atlanacağını kullanıcıdan okumanız ardından da sona kalan elemanları bulmanızdır. Sona kalan eleman sayısı, atlanacak olan eleman sayısının bir eksiğidir. Yukarıdaki örnekte 3 atlandığı için sona 2 eleman kalmıştır. Ayrıca bu ödev dairesel bağlı liste kullanılarak yapılacak ve 1. ödevde belirtilen gönderme şartlarına uyulacaktır. Ödevin teslim tarihi 29 Mart'tır. 

  • Ödev 3:
  • Dizileri (array) kullanarak sıra (queue) kodlayınız. Bu kodda, en az enque  ve deque fonksiyonları bulunmalıdır. Kodunuzda optimum yer kullanımı ve hız olması için en iyi çözümü arayınız. Tasarımınızı anlatan bir word dosyası ilave ediniz. Bu dosyada, enque, deque fonksiyonlarının dizi üzerinde nasıl işlemler yaptığını ve neden bu işlemlerin en optimum (en iyi) olduğunu açıklayınız. Sadece bu ödev için tasarımı açıklayan rapor içermeyen ödevler teslim edilmemiş sayılacaktır. Ödevin son teslim tarihi 2 nisan 2010'dur. 

    Ödev 4:

  • Bir çift bağlı listeyi (doubly linked list) alarak bir ikili arama ağacına çeviren kodu yazınız. Bu ödevde ağaçta bulunan düğümlerin hafızadaki yerlerini değiştirmemeniz gerekir. Örneğin aşağıdaki şekilde bağlı bir liste düşünelim :

  • Yukarıdaki ilk şekilde bulunan çift yönlü bağlı liste, ikinci şekilde görüldüğü üzere bir ikili arama ağacına dönüşmüştür. Bilindiği üzere çift bağlı listede bir düğümde iki gösterici (pointer) ve bir veri alanı bulunmakta ve ikili arama ağacında da aynı yapı kullanılmaktadır. O halde yapısal bir değişikliğe gidilmeden, veriler için ilave hafıza alanı açılmadan ve yeniden ekleme silme gibi işlemler yapılmadan SADECE ve SADECE göstericilerin (pointer) değerleri değiştirilerek, bir çift yönlü bağlı liste (doubly linked list) bir ikili arama ağacına dönüştürülebilir.
  • Sizden bu ödevde istenen, bir çift yönlü bağlı liste alarak dengeli bir ikili arama ağacı (balanced binary search tree) oluşturmanızdır.
  •  Ödevin son teslim tarihi 29 nisan 2010 perşembe'dir.

  • Ödev 5:
  • Ders kitabında bulunan 19.1, 19.2 ve 19.3 soruları çözünüz. (Son teslim tarihi 17 Mayıs 2010)
  • Ödev 6:
  • int n = Öğrenci No;
  • if(n%3==0)
  •  Dijkstra
  • if(n%3==1)
  •  BellmanFord
  • if(n%3==2)
  •  Prims
  • algoritmasını kodlayınız.
  • Son teslim tarihi 27 Mayıs 2010

  • Referans Kitaplar:
    Programlama ve Veri Yapýlarýna Giriþ (C, C++ ve JAVA ile) , Yazan : Þadi Evren ÞEKER, detaylý bilgi için týklayýnýz
    Öðrencilerin dil tercihine baðlý olarak "Mark Allen Weiss" tarafýndan yazýlmýþ "Addison Wesley" yayýn evi tarafýndan yayýnlanmýþ Data Structures and Algorithm Analysis in C,C++ veya JAVA olabilir detaylý bilgileri için yazarýn web sitesini ziyaret edebilirsiniz.
    Yine schaum's serisi "Data Structures with" kitaplarýndan istenilen dil için kitap alýnabilir "Data Structures with Java, C veya C++" olabilir.
    Hatýrlatma: Ders boyunca kullanýlacak olan resmi dil C dilidir.


  • Dersin deðerlendirmesi:
  • Quizler&Classwork&Ödevler %20
  • Arasýnav %20
  • Dönem Projesi %20
  • Final %40