| Yazar |
|
mrflz
Luleburgaz
admin
Kayıt: 15.06.2006 |
|
Derste de bahsedildiği gibi Advanced Algorithm Analysis dersi projeleri şu şekilde belirlenmiştir.
Proje 1 (10 puan) Teslim tarihi: 5 MAYIS 2010 saat 13:10 (dersin ilk 10 dakikasında).
k-th smallest bulma. Verilen n integer içerisinde k-th smallest olanı bulan decrease and conquer algoritması ile çalışan program yazılacak. Ayrıca bu programın kullanması gereken 'partition' prosedürünü kullanan quick sort da implement edilecek ve k-th smallest bir de bu şekilde bulunacak. Program çalıştığında input olarak k-sayısını, n-sayısını, ve bu n tane random sayının üretileceği bir aralık isteyecek. Yukarıda bahsi geçen hem O(n) hem de O(nlogn) algoritmalar kullanılarak run-timeları ile birlikte bulunan sonuç da output edilecek.
Ayrıca bir sayfalık proje outcome report eklenecek (hem soft hem de hard copy olarak), bu rapor bulunan sonuçları içerecek, farklı n değerleri için simulasyonlar yapılıp run-timelar plot edilecek ki O(n) ile O(nlogn) arasındaki fark ne kadar bariz görülecek.
Proje 2 (20 puan) Teslim tarihi: 25 MAYIS 2010 saat 16:00.
Skip-list (15 puan) versus binary search (5 puan). Program çalıştığında input olarak n-sayısını, ve n tane random sayının üretileceği bir aralık isteyecek.
Bu sayılar skip-liste insert edilecek ve ayrıca insertion-sort ile bir array'a (binary search için) insert edilecekler. Her iki metot için de insertion zamanları tutulacak ve plot edilecek, ayrıca ortalama (standart sapması ile beraber) insertion zamanı da verilecek.
Sonrasında her bir sayı query olarak kullanılacak, query zamanları plot edilecek ve bu zamanların maximumu ve ortalaması (standart sapması ile beraber) verilecek.
Delete işlemi yapılmayacak.
Farklı n değerleri için simulasyonlar yapılıp run-timelar ve Özet sonuçlar bir sayfalık proje outcome report da ayrıca verilecek (hem soft hem de hard copy olarak)...
I see the ghosts of navigators but they are lost
|
|
|
| Yazar |
|
rose
Kayıt: 22.06.2007 |
|
Arkadaşlar birinci projede sadece quick sort u çalıştırıp k. item i almıcak mıyız?
Bu projenin esprisi zor yanı nedir derse gelen arklar söler mi?
|
|
|
| Yazar |
|
mrflz
Luleburgaz
admin
Kayıt: 15.06.2006 |
|
herhalde kodlarını yazmak zor yanı :D
I see the ghosts of navigators but they are lost
|
|
|
| Yazar |
|
fenerista
Istanbul
Kayıt: 27.11.2006 |
|
o sadece n(logn) li, algoritmada olacak sıralayıp alacan, o(n) de çalışan algoritma için yine quicksorta benzer bir algoritma yapacaksın ama aynısı değil tabi.
Oktay,
Thk you!
|
|
|
| Yazar |
|
rose
Kayıt: 22.06.2007 |
|
fenerista yazdi | | | o sadece n(logn) li, algoritmada olacak sıralayıp alacan, o(n) de çalışan algoritma için yine quicksorta benzer bir algoritma yapacaksın ama aynısı değil tabi. |
hımm şimdi oldu peki biraz yardımcı olur musun o algoritmayı nasıl yapacaz hani mantık olarak falan ne şekilde işlicek o derste yoktum da hocada anlatmış sanırım gerçi bişiler?
|
|
|
| Yazar |
|
mrflz
Luleburgaz
admin
Kayıt: 15.06.2006 |
|
"Verilen n integer içerisinde k-th smallest olanı bulan decrease and conquer algoritması "
ilk projedeki ilk kısım
ilk eleman pivot alınıyor.daha sonra dizi pivottan sonrakinden başlanarak taranıyor, kendinden sonra gelen buyuk bulursa duruyor indexi alıyor, sonra sondan geri gelmeye baslıyor, kendinden kucuk bulursa duruyor indexini alıyor.
sonra buldugu kucuk ve buyuk sayıların indexleirni değişitiriyor daha sonra kucuk sayı ile pivotun yerini değiştiriyor.
eger bu durumda pivot aldıgımız sayının indexi aradıgmız k indexi ile eşleşirse k. elemanı bulmus oluyoruz. değil ise pivottan kucuk ya da buyuk olma durumuna gore saga veya sola dallanıyoruz. Yine dallandıgımız tarafın sol basındaki sayıyı pivot alıyoruz..
Derste anlatılan trace edilen algoritma bu sekildemiydi? yanlıs var sanki? yanlıssa dogrusunu hataırlayn yazabilir mi acaba?
hatta dersteki dizi
4 1 10 9 7 12 8 15
2 1 4 9 7 12 8 10 15
8 7 9 12 10 15
8 7 9
7 8
8 burada pivot iken sonucta medyan olarak bulunmustu...
I see the ghosts of navigators but they are lost
|
|
|
| Yazar |
|
mrflz
Luleburgaz
admin
Kayıt: 15.06.2006 |
|
bir de çift sayıda eleman olursa dizide medyan yok mu diyeceğiz yoksa
⌊(n + 1)/2⌋ (the lower median)
olarak mı alacagız? fikri olan var mı?
I see the ghosts of navigators but they are lost
|
|
|
| Yazar |
|
mrflz
Luleburgaz
admin
Kayıt: 15.06.2006 |
|
hocanın kitabının 160. sayfasında derinlemesine bir giriş var !!!
I see the ghosts of navigators but they are lost
|
|
|
| Yazar |
|
angelme
istanbul
Kayıt: 21.10.2006 |
|
mrflz yazdi | | bir de çift sayıda eleman olursa dizide medyan yok mu diyeceğiz yoksa
⌊(n + 1)/2⌋ (the lower median)
olarak mı alacagız? fikri olan var mı? |
hatırladığım kadarıyla medyan yok diyecektik hocanın derste öyle dediğini hatırlıyorum.
|
|
|
|
|
-
 Del.icio.us
-
 Digg
-
 Facebook
-
 Furl
-
 Google
-
 Blink
-
 Simpy
-
 Spurl
-
 Y! MyWeb
|
|
| | | | | |
