Soal dan jawaban metode divide dan conquer

Silahkan jawab pertanyaan dibawah ini !!

1.Algoritma yang berprinsip memecahkan permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan disebut:

      a. Sorting                                                         d. Logika

      b. Divide and Conquer                                 e. Algoritma

      c. Partition exchange sort

2. Tehknik pengurutan dgn cara pemilihan elemen atau proses kerja  dgn memilih elemen data terkecil yang kemudian dibandingkan & ditukarkan dgn elemen pd data awal, dst s/d seluruh elemen shg akan menghasilkan pola data yg telah disort disebut:

      a. Buble Sort                           d. Insertion

      b. Merge Sort                          e. Selection Sort

      c. Quick Sort

3. Tehnik Sort yg bekerja dgn menggunakan prinsip gelembung (bubble) udara yg akan bergerak naik ke atas secara satuper satu di sebut:

      a. Buble Sort                          d. Insertion

      b. Merge Sort                          e. Selection Sort

      c. Quick Sort

4.  Metode QuickSort sering disebut metode partition exchange sort, Diperkenalkan oleh:

      a. Ibnu Nafis                           d. Aristoteles  

      b. C.A.R. Hoare                                e. James Watt

      c. Alexander Graham Bell

     5. 1. Kelompokan deret bilangan kedalam 2 bagian, 4 bagian, 8 bagian, ......dst   à (2ⁿ)

         2. Urutkan secara langsung bilangan dalam kelompok    tsb.

         3. Lakukan langkah diatas untuk kondisi bilangan yg lain sampai didapatkan urutan yg    optimal .

      Perinsip kerja di atas dalam sorting data adalah untuk teknik:

      a. Buble Sort                           d. Insertion

      b. Merge Sort                         e. Selection Sort

      c. Quick Sort

6.  Dalam tehnik Searching yang termasuk tehnik pencarian tunggal adalah:

        a.Tehnik Sequential Search / Linier Search dan Tehnik Binary Search

        b. Tehnik StraitMAXMIN dan Tehnik D and C

 c .Tehnik Best Case

 d. Tehnik Worst Case

 e .Tehnik Average Case

7. Proses yg dilaksanakan pertama kali pd bgn tengah dr elemen himpunan, jk data yg dicari ternyata < elemen bagian atasnya, maka pencarian dilakukan dr bagian tengah ke bawah. Merupakan dalam tehnik:

         a.Tehnik Sequential Search / Linier Search

         b. Tehnik Binary Search **

         c. Tehnik StraitMAXMIN

        d. Tehnik D and C

        e. Tehnik Best Case

8. Rumus untuk menentukan Nilai Tengah (mid) adalah:

       a. ( Low + High ) Div 2

       b. ( Low + High ) - 2

       c. Mid –1

       d. Mid +1

       e. Mid *1

9. Terjadi jika elemen dalam himpunan disusun secara decreasing (menurun), Dengan Oprasi perbandingan sebanyak 2(n-1) kali satuan operasi di sebut:

       a. Worst Case

       b. Best Case

       c. Average Case

       d. StraitMAXMIN

       e. Binary Search

10. Pencarian yg dimulai dari record-1 diteruskan kerecord selanjutnya yaitu record-2, ke-3,..., sampai diperoleh isi record sama dengan informasi yg dicari di sebut:

        a. StraitMAXMIN

        b. Linear/Sequential Search

       c. StraitMAXMIN

       d. Average Case

       e. Best Case

11. Solusi optimal dari permasalahan yg mempunyai dua kriteria yaitu Fungsi Tujuan/Utama & nilai pembatas (constrain) disebut:

       a. Metode D dan C

       b. Metode Greedy

        c. Metode Buble Sort

        d. Metode Quick Sort

       e. Metode Searching

12. Manakah dibawah ini masalah yang bisa diselesaikan dengan Metode GREEDY adalah:

       a. Optimal On Tape Storage Problem

        b. Searching data

        c. Devide dan Conquer

        d. Sorting Data

       e. StartMaxMin

13. Misal terdapat 3 buah program ( n= 4 ) yang masing-masing mempunyai panjang program ( p1,p2,p3,p4)=(5,10, 2,1) Tentukan Urutan penyimpanannya :

       a. p2, p3, p1, p4                                 d. P4, p3, p1, p2          

       b. P3, p2, p1, p4                                 e. p1, p2, p3, p4

       c. p4, p2, p3, p1

14. Penyelesaian knapsack dengan Kriteria Greedy adalah dengan konsep dibawah ini , kecuali :
a. Pilih obyek dengan nilai Pi maximal
b. Pilih obyek dengan berat Wi minimal
c. Pilih obyek dengan Pi/Wi maximal
d. Pilih obyek dengan berat Wi maximal

       e. Pilih obyek dengan berat Pi x Xi

15.  Diketahui bahwa kapasitas M=40 Kg,dengan jumlah barang n=5. Berat Wi barang=(W1,W2,W3,W4,W5)=(14, 10, 20, 12, 16). Nilai Pi barang=(P1,P2,P3,P4,P5) = (28, 40, 70, 36, 24).Profit nilai yang didapat adalah:

          a.140                           d.124
   b.150                          e. 104
   c.160
 16.Diketahui bahwa kapasitas M=40 Kg, dengan jumlah barang n=5. Berat Wi barang = (W1,W2,W3,W4,W5) = (14, 10, 20, 12, 16) Nilai Pi barang = (P1,P2,P3,P4,P5) = (28, 40, 70, 36, 24).  Pola urutan data yang baru untuk Wi adalah:
a.10, 12, 14, 16, 20                  d. 14, 10, 12, 16, 20
b.12, 14, 10, 20, 16                 e. 10, 16, 12, 20, 14

       c. 10, 20, 12, 14, 16

17. Menggunakan soal No.21

         Pola urutan data yang baru untuk Pi adalah:
 a. 28, 70, 36, 40, 24                d. 40, 70, 36, 28, 24    
 b.40, 70, 28, 36, 24                 e. 40, 70, 24, 28, 36

        c. 24, 28, 36, 40, 70

18.  Menghitung jarak satu persatu sesuai dengan arah dari graph yang ditunjuk oleh tiap-tiap ruas/edge dan dilakukan terhadap ruas dari graph yang memiliki jalur awal dan jalur akhir adalah proses untuk mendapatkan solusi optimal dari permasalahan :
a. Knapsack                               d. Minimum Spanning Tree
b. Shortest Path Problem        e. Searching
c. Knapsack Problem

19. Pada gambar diatas. Berapa waktu minimal yang dibutuhkan untuk mencapai ke 5 simpul?

      a. 45                            c. 52                e. 25

      b. 54                            d. 50

20 Dibawah ini yang termasuk kriteria2 dari spanning tree adalah, kecuali :

      a. Setiap ruas pada graph harus terhubung (conected)

      b. Setiap ruas pd graph hrs mpy nilai (label graph)

      c. Setiap ruas pd graph tdk mpy arah (graph tdk berarah)

      d. Setiap ruas pd graph tsb hrs mpy arah (graph berarah)

      e. Salah semua

PENGERTIAN METODE DIVIDE AND CONQUER

METODE

DIVIDE AND CONQUER

     1. Pengertian

Algoritma Divide And Conquer merupakan algoritma yang sangat populer di dunia ilmu komputer. Divide and conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan.

Langkah-langkah umum algoritma Divide and Conquer :

·         Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya berukuran hampir sama).

·         Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah (secara reurtfi ).

·         Combine : Menghubungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

     2.      Penerapan Algoritma

Pemecahan masalah Convex Hull dengan algoritma divide and conquer

Pada penyelasaian masalah pencarian Convex Hull dengan menggunakan algoritma divide and conquer, sebagai generalisasi dari algoritma pengurutan mergesort.

            Adapun permasalahan convex hull adalah sebuah permasalahan yang memiliki aplikasi terapan yang cukup banyak, seperti pada permasalahan grafik komputer, otomatis desain, pengenalan pola (pattern recognition), dan penelitian operasi. Divide And Conquer adalah metode pemecahan masalah yang bekerja dengan membagi masalah menjadi beberapa upa-masalah yang lebih kecil, kemudian menyelesaikan masing-masing upa-masalah tersebut secara independent.

    3.      Penyelesaian Dengan Algoritma Divide And Conquer

a.       Asumsi : n = 2k dan titik-titik diurut berdasarkan absis (x).

b.      Algoritma closest pair :

ü  Solve : jika n = 2, maka jarak kedua titik dihitung langsung dengan rumus Eculidean.

ü  Divide : bagi titik-titik itu ke dalam dua bagian, Pleft dan Pright, setiap bagian mempunyai jumlah titik yang sam.

ü  Conquer : secara rekurtif, terapkan algoritma D-and-C pada masing-masing bagian.

c.       Pasang titik yang jaraknya terdekat ada tiga kemungkinan letaknya :

ü  Pasangan titik terdekat terdapat di bagian Pleft.

ü  Pasangan titik terdekat terdapat di bagian Pright;

ü  Pasangan titik terdekat dipisahkan oleh garis batas L, yaitu satu titik di Pleft dan satu titik di Pright.

Jika kasusnya adalah ( C  ), maka lakukan tahap COMBINE untuk mendapatkan jarak dua titik terdekat sebagai solusi persoalan semula.

Latihan Soal dan jawaban Bab METODE DIVIDE AND CONQUER

Latihan Soal

Terdapat  deret angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Urutkanlah deret angka tersebut dengan menggunakan Teknik sort yang sudah dijelaskan.

Jawab :

1.SELECTION SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 2 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 3 = 2, 34, 11, 50, 23, 89, 65, 99, 6, 37, 74, 44.

Langkah 4 = 2, 6, 11, 50, 23, 89, 65, 99, 34, 37, 74, 44.

Langkah 5 = 2, 6, 11, 50, 23, 89, 65, 99, 34, 37, 74, 44.

Langkah 6 = 2, 6, 11, 23, 50, 89, 65, 99, 34, 37, 74, 44.

Langkah 7 = 2, 6, 11, 23, 34, 89, 65, 99, 50, 37, 74, 44.

Langkah 8 = 2, 6, 11, 23, 34, 37, 65, 99, 50, 89, 74, 44.

Langkah 9 = 2, 6, 11, 23, 34, 37, 44, 99, 50, 89, 74, 65.

Langkah 10 = 2, 6, 11, 23, 34, 37, 44, 50, 99, 89, 74, 65.

Langkah 11 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 89, 74, 99.

Langkah 12 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99.

2. BUBBLE SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44.

Langkah 2 = 99, 34, 11, 50, 23, 89, 2, 65, 6, 37, 74, 44.

Langkah 3 = 2, 99, 34, 11, 50, 23, 89, 65, 6, 37, 74, 44.

Langkah 4 = 2, 6, 99, 34, 11, 50, 23, 89, 65, 37, 74, 44.

Langkah 5 = 2, 6, 11, 99, 34, 50, 23, 89, 65, 37, 74, 44.

Langkah 6 = 2, 6, 11, 23, 99, 34, 50, 89, 65, 37, 74, 44.

Langkah 7 = 2, 6, 11, 23, 34, 99, 50, 89, 65, 37, 74, 44.

Langkah 8 = 2, 6, 11, 23, 34, 37, 99, 50, 89, 65,74, 44.

Langkah 9 = 2, 6, 11, 23, 34, 37, 44, 99, 50, 89, 65,74.

Langkah 10 = 2, 6, 11, 23, 34, 37, 44, 50, 99, 89, 65,74.

Langkah 11 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 99, 89, 74.

Langkah 12 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 99, 89.

Langkah 13 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99.

3. QUICK SORT

4. INSERTION SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 2 = 34, 99, 11, 50, 23, 89, 2, 65, 6, 37, 44, 74

Langkah 3 = 34, 11, 99, 23, 50, 2, 89, 65 ,6, 37, 44, 74

Langkah 4 = 11, 34, 23, 99, 2, 50, 6, 89, 37, 65, 44, 74,

Langkah 5 = 11, 23, 34,2, 99, 6, 50, 37, 89, 44, 65, 74

Langkah 6 = 11, 23, 2, 34, 6, 99, 37, 50, 44, 89, 65, 74

Langkah 7 = 11, 22, 36, 34, 37, 99, 44, 50, 65, 89, 74

Langkah 8 = 2, 11, 6, 23, 34, 37, 44, 99, 50, 65, 74, 89

Langkah 9 = 2, 6, 11, 23, 34, 37, 44, 50, 99, 65, 74, 89

Langkah 10 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 99, 74, 89

Langkah 11 =2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 99, 89

Langkah 12 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99

5. MERGE SORT

Angka : 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 1 = 99, 34, 11, 50, 23, 89, 65, 2, 6, 37, 74, 44

Langkah 2 = 34, 99, 11, 50, 23, 89, 65, 26, 37, 74, 44

Langkah 3 = 11, 34, 50, 99, 22, 37, 58, 99, 37, 44, 74

Langkah 4 = 2, 11, 23, 34, 50, 99, 6, 37, 44, 65, 74, 89

Langkah 5 = 2, 6, 11, 23, 34, 37, 50, 99, 44, 65, 74, 89

Langkah 6 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 99, 74, 89

Langkah 7 = 2, 6, 11, 23, 34, 37, 44, 50, 65, 74, 89, 99

Soal dan Kunci jawaban Array atau Larik

Silahkan jawab pertanyaan dibawah ini!!

1.Type data dibawah ini, yang tidak termasuk dalam tipe data sederhana tunggal, adalah:            

a. Boolean      b. Integer             c. String         d. float             e. Char

2. ==, <=, >=   ,!=, termasuk dalam operator …                   

 a. Aritmatika     b. Relasi             c. Unary       d. Bitwise             e. Binary 

3.Type data yang menghasilkan bentuk keluaran nilai Truedan False(Benar dan Salah) ,  adalah :           

 a. Boolean        b. Integer             c. String                 d. float             e. Char

4.   void main()       

{       

....(a)....  x,y,z;       

clrscr();       

cout <<“\n input nilai X=“; cin >> x;       

cout <<“\n input nilai Y=“; cin >> y; z = x + y;       

cout <<“\n hasil penjumlahan =“ << z;       

getch();       

}

Tipe data yang tepat untuk (a) adalah ….                        

a. Boolean      b. Integer          c. String              d. Array              e. Char

5.  void main()

{          

int r = 10; int s;          

clrscr();          

s = 10 +  ++r;          

cout <<“r = “<< r << ‘\n’;          

cout <<“s = “<< s << ‘\n’;                                                       

getch();         

}                         

Hasil eksekusi dari program diatas adalah ….                        

a. r = 11, s = 21     c. r = 11, s = 20   

b. r = 10, s = 21     d. r = 10, s = 20       e. r = 12, s = 21

6.  Setiap elemen dari  sebuah Array haruslah mempunyai type data yang sama, termasuk dalam karakteristik array yaitu :           

 a. Statis      b. Heterogen             c. Dinamis             d. Homogen             e. Terurut  

7.   Array yang sering digunakan dalam menterjemahkan matriks pada pemrograman, adalah array berdimensi :            

a. Satu     b. Satu dan Dua      c. Dua              d. Satu dan Tiga             e. Tiga 

8.   Contoh aplikasi array dimensi dua adalah…..            

a. Input data suhu       

b. Input nilai mahasiswa perkelas dan matakuliah

c. Input nama hari    

d. Input nilai ipk mahasiswa    

e. Input nama bulan

9.   Terdapat Array : A [5][4] maka jumlah elemen Array tersebut adalah ……           

 a. 25     b. 15       c. 35    d. 20    e. 9   

   

10.  Array yang sangat banyak elemen nol-nya, dikenal sebagai :            

a. Upper tringular Array      c. Lower tringular Array        

b. One Dimensional Array   d. Multi Dimensional Array             e. Sparse Array

11.Sekumpulan data yang bertipe sama dan antara data satu dengan data yang lain dibedakan dengan indeksnya merupakan pengertian dari …

a.     Integer.    b.Array.  c.Variabel.   d.Char.      e. Booelan.  

12.  Jumlah titik pada indeks array harus berjumlah …

a.Satu titik.    b.Dua titik.   c.Tiga titik.  d.Empat titik.  e.Lima titik. 

13. SUM adalah …

a.Nilai rata-rata dari seluruh indeks array

b.Banyaknya indeks yang ada di dalam array.

c.Hasil dari penjumlahan seluruh data dalam array.

d.Indeks akhir dari array.

e.Nama variabel dari array.

14.Yang bukan merupakan tipe data composite adalah …

a.Image      b.Date time    c.Character    d.Enumerasi     e.Record.

15.  Identifier adalah …

a.Tipe data     c.Nama

b.Variabel      d.Nilai    e.Konstanta.

16.Nama lain dari flowchart adalah …

a.Algoritma    c.Bagan alir  

b.Alur             d.Tree                e.Diagram.

17.  Di bawah ini yang bukan termasuk teknik pengurutan data adalah….

a.Bubble sort    c.Selection sort   

 b.Tree sort       d.Merge sort        e.Head sort.  

18.  Array yang sering digunakan dalam menterjemahkan matriks pada  pemrograman, adalah array berdimensi…

a.Satu.                   c.Dua.    

b.Satu dan Dua     d.Satu dan Tiga.        e.Tiga.

19. Jika tail=null, maka kondisi Linked List adalah…

a.Terisi.      c.Kosong    

b.Penuh.     d.Tidak dapat ditambah.   e.Baru.

 20. Perintah yang tepat untuk menyatakan Linked list berada dalam  kondisi kosong, adalah…

a.Head=tail.              c.Bantu=null

b.Head=tail=null.     d.Bantu=head.           e.Bantu