1. (5 score) G = (V.E) ile tanmlanan graph iin |E| deeri ||^2 den ok kk ise bu graphlara denir. 2. (5 score) G = (V.E) ile tanmlanan graph iin E deeri | V |^2 deerine yakn ise bu graphlara denir. 10. (10 score) isim, sovisim, doum tarihi ve baba adlar eit olan rencilerin birbirlerine eit kabul edildi aadaki Student class'nda eguals metodunu ve tm data fielderin "31x + y" kuralna gre birletirilerek hash code oluturan bashcode metodunu gerekletiriniz. public class Student { String isim, soyisim, babaadi: Date dogum Tarihi: public boolean egyals(Object 0) { } public int bashCodel) { 3. (5 score) G = (V.E) ile tanmlanan graph adiacency list kullanlarak gsterilirse .......... Space, adiacency matrisle gsterilirse........... space gerektirir. 4. (5 score) Her nede'dan kme temsilcisine (header ocdea) bir pointer kullanlarak disigint-setler, linked-list olarak gerekleitiridiinde herhangi bir elemann hangi kmeye ait olduunu bulan findset ilemi en kt (worst case) ............. zaman, verilen iki elemann kmelerini birletiren union ilemi ise en kt (worst case)............. zaman gerektirir (toplam eleman sayisi n dir.). 5. (5 score) Bir nceki soruda eer union ilemi kme byklne gre yaplrsa yani kk kme byk kme birletirilirse (weighted union heuristic), union ilemi en kt (worst case) ............. zaman gerektirir. 6. (Sscore) Yine 4.sorudaki linked list data structure' iin, n-1 tane union ilemi; kme byklne gre yaplrsa weighted-union heuristic) toplamda en kt (worst case)..........., yaplmazsa toplamda en kt .......... zaman gerektirir (toplam deer istenmekte dikkat ediniz.). } 11. (10 puan) Her bir rencinin derslerini string listelerde tutan bir tane HashMap datas tanmlaynz. rnek put ve set metodlarnn kullanmn gsteriniz. 12. (20 puan) Union-find (disigint set) data structure'i forest-tree ve union by rank UnionFind class' ile gerekletirilmek istenmektedir. Bu classta a[i], i elemannn garent nede ny vermektedir. Eer a[i] negatif ise i nede'y, root node olarak kabul edilmekte ve kmeyi temsil etmektedir. . Math.abs(a[i])-1 deeri de bu root ile gsterilen kmenin rankini vermektedir. Aadaki class da uningo ve find Set metodlarn gerekletiriniz. class UnionFind 23 99 int[] a; l/kume elemanlarinin parent nedenu verir public Union Eindrint n){ 7. (5 score) Yukardaki graph "uzerinde BES(breadth-first search) algoritmas, deeri 5 olan vertex zerinde saaldnda vertexleri eriim sralarna gre yaznz. 8. (5 score) Bir nceki sorudaki graph zerinde DES depth-first search) algoritmas, deeri 5 olan vertex zerinde arldnda vertexler "zerindeki ilemlerin biti srasna gre yaznz. 9. (20 puan) Aadaki class'da DFS algoritmasn gerekleitiren ve vertexler zerindeki ilemlerin biti zamanlarnn srasna gre listeye ekleyerek retuco eden DFS metodunu gerekletiriniz. import java util.*; //directed graph public class Graph Map-Vertex, Set> adi; a = new int[n]; } // {x} kumesini olusturur public makeSetlint x){ a[x] =-1; } 1/X'in hangi kumexe ait oldugunu bulup return eder public int findSet(int xX } 1. (5 score) G = (V.E) ile tanmlanan graph iin |E| deeri ||^2 den ok kk ise bu graphlara denir. 2. (5 score) G = (V.E) ile tanmlanan graph iin E deeri | V |^2 deerine yakn ise bu graphlara denir. 10. (10 score) isim, sovisim, doum tarihi ve baba adlar eit olan rencilerin birbirlerine eit kabul edildi aadaki Student class'nda eguals metodunu ve tm data fielderin "31x + y" kuralna gre birletirilerek hash code oluturan bashcode metodunu gerekletiriniz. public class Student { String isim, soyisim, babaadi: Date dogum Tarihi: public boolean egyals(Object 0) { } public int bashCodel) { 3. (5 score) G = (V.E) ile tanmlanan graph adiacency list kullanlarak gsterilirse .......... Space, adiacency matrisle gsterilirse........... space gerektirir. 4. (5 score) Her nede'dan kme temsilcisine (header ocdea) bir pointer kullanlarak disigint-setler, linked-list olarak gerekleitiridiinde herhangi bir elemann hangi kmeye ait olduunu bulan findset ilemi en kt (worst case) ............. zaman, verilen iki elemann kmelerini birletiren union ilemi ise en kt (worst case)............. zaman gerektirir (toplam eleman sayisi n dir.). 5. (5 score) Bir nceki soruda eer union ilemi kme byklne gre yaplrsa yani kk kme byk kme birletirilirse (weighted union heuristic), union ilemi en kt (worst case) ............. zaman gerektirir. 6. (Sscore) Yine 4.sorudaki linked list data structure' iin, n-1 tane union ilemi; kme byklne gre yaplrsa weighted-union heuristic) toplamda en kt (worst case)..........., yaplmazsa toplamda en kt .......... zaman gerektirir (toplam deer istenmekte dikkat ediniz.). } 11. (10 puan) Her bir rencinin derslerini string listelerde tutan bir tane HashMap datas tanmlaynz. rnek put ve set metodlarnn kullanmn gsteriniz. 12. (20 puan) Union-find (disigint set) data structure'i forest-tree ve union by rank UnionFind class' ile gerekletirilmek istenmektedir. Bu classta a[i], i elemannn garent nede ny vermektedir. Eer a[i] negatif ise i nede'y, root node olarak kabul edilmekte ve kmeyi temsil etmektedir. . Math.abs(a[i])-1 deeri de bu root ile gsterilen kmenin rankini vermektedir. Aadaki class da uningo ve find Set metodlarn gerekletiriniz. class UnionFind 23 99 int[] a; l/kume elemanlarinin parent nedenu verir public Union Eindrint n){ 7. (5 score) Yukardaki graph "uzerinde BES(breadth-first search) algoritmas, deeri 5 olan vertex zerinde saaldnda vertexleri eriim sralarna gre yaznz. 8. (5 score) Bir nceki sorudaki graph zerinde DES depth-first search) algoritmas, deeri 5 olan vertex zerinde arldnda vertexler "zerindeki ilemlerin biti srasna gre yaznz. 9. (20 puan) Aadaki class'da DFS algoritmasn gerekleitiren ve vertexler zerindeki ilemlerin biti zamanlarnn srasna gre listeye ekleyerek retuco eden DFS metodunu gerekletiriniz. import java util.*; //directed graph public class Graph Map-Vertex, Set> adi; a = new int[n]; } // {x} kumesini olusturur public makeSetlint x){ a[x] =-1; } 1/X'in hangi kumexe ait oldugunu bulup return eder public int findSet(int xX }