Dynamic Programming (lanjutan) & Greedy

Dynamic Programming (lanjutan)

-> Knapsack 0/1

    cth:

    i   =  1     2     3     4

    w =  2     1     3     2

    p  = 12   10   20   15

   M = 5

    keterangan:

    i = item

    w = weight tiap item

    p = profit tiap item

    M = max weight yang bisa dibawa

    output: buat tabel, nilai tabel selanjutnya ditentukan dari nilai tabel sebelumnya

Greedy
1. Minimum Spanning Tree
    Spanning tree: graph yg ga ada cycle

   1. Algo. Prim
      -> selalu nyambung, mulai dari node yang cost nya terkecil, lalu lanjut ke node lain yang jaraknya terkecil dari node sebelumnya

   2. Algo. Kruskal
      -> urutin dari yang jaraknya terkecil, jangan ambil yang menyebabkan cycle

2. SSSP (Single Source Shortest Path) -> coming soon or coming never, lol

3. Huffman Code
    -> merepresentasi karakter dengan variable length
    -> representasi karakter yg populer digunakan: ASCII & EBDIC, merupakan representasi dgn fixed length
    -> Aturan:
        1. Makin sering huruf tsb muncul, makin pendek representasinya -> cth: A bnyk dipake, shg A direpresentasikan sbg 0
        2. tidak boleh 1 karakter merupakan awalan dari karakter lain -> cth: A = 0 ; B tdk boleh 01 (karena 0 merupakan A)

    -> Contoh membuat representasi berdasarkan aturan berikut:
        A > B > C > D
        Langkah:
        1. ambil 2 huruf terkecil dulu yaitu {C, D}, bedakan dengan 0 & 1
        2. gabungkan dgn huruf selanjutnya {B, C, D}, bedakan dgn 0 & 1, dan seterusnya

        Dlm bentuk Tree:
     

 
Sehingga
A = 0
B = 10
C = 110
D = 111

3. Knapsack Fractional -> barang bs dibagi
    Ada 3 macam greedy:
    1. Greedy Weight
    2. Greedy Profit
    3. Greedy Ratio (Profit / Weight) <-- optimal="" p="" selalu="">

    Penjelasan:
    1. Greedy weight: mengurutkan item yg dimasukkan duluan berdasarkan weight item tsb
        logikanya yang weight paling kecil yang dimasukin duluan

    2. Greedy Profit: mengurutkan item yg dimasukkan berdasarkan profit. logikanya yg profit terbesar yg dimasukkan duluan

    3. Greedy Ratio: mengurutkan item yg dimasukkan duluan berdasarkan rasio dari barang tsb (rasio dapet dari profit / weight) 

Read More

Dynamic Programming

1. Fibonacci (coming soon!)

2. Koefisien Binomial
    C(n, k) = C(n-1, k-1) + C(n-1, k) dimana n > k > 0

3. Coin Change (coming soon or coming never.. idk)

4. Binary Search Tree yang optimal
cth:
A = 0,1
B = 0,2
C = 0,4
D = 0,3

Subproblem {1,2} -> dlm hal ini A=1, B=2, dst, nilai ini merupakan nilai k
A -> B
Cost: 1 * 0,1 + 2 * 0,2 = 0,3

B -> A
Cost: 1* 0,2 + 2 * 0,1 = 0,4

pilih yg cost terkecil, maka arah dari A -> B

Subproblem {3,4}
C -> D
Cost: 1 * 0,4 + 2 * 0,3 = 1,0

D -> C
Cost: 1 * 0,3 + 2 * 0,4 = 1,1

nilai k yang dimaksud diatas berguna untuk menentukan yang mana yang jadi root dari tree tersebut. misalkan k = 1, berarti rootnya adalah A
jadi susunannya: A -> B -> C -> D
(anggap ini dlm bentuk tree, penyusunan berdasarkan abjad. kalau abjad yang ingin dimasukkan ke tree lebih besar dari root nya (misal B adalah huruf yg lebih besar dari A, F adalah huruf yang lebih besar dari C, dsb) maka menjadi cabang tree di sebelah kanan root, dan sebaliknya jika lebih kecil maka menjadi cabang tree sebelah kiri.)

jadi dari aturan diatas, k = 2 dapat dituliskan sbb:
              B
           /      \
         A       C
                     \
                     D

Read More

Analisis dan Perancangan Algoritma - Space and Time Tradeoff

String Matching:
1. Algo. Horspool
   Kasus 1 dan 2: gada string yg berulang di depan
   Kasus 3 dan 4: ada yang berulang

               B   A   R   B   E   R
                    4    3    2    1    0
   (penomoran dari huruf paling akhir ke awal)

   Shift Tabel T (berupa array) => index nya sesuai ascii
   contoh ascii A = 65 -> T[65] = 4

2. Algo. Boyer-Moore
   Ada 2 tabel, yaitu
   -> Shift Tabel T
   -> Suffix Table utk hitung d2

   k = banyaknya variabel yang sama
   k = 0 -> Boyer-Moore = Horspool

   utk mencari d1
   -> Bad-Character (bc) = karakter setelah string yang sama
        d1 = max(T[bc] - k, 1)

   untuk mencari d2
   -> Good Suffix
        a. Aturan lama (masih bisa keliru)
        d2 = jarak antar karakter yang karakter sebelumnya berbeda
        contoh: A B  C  B   A   B
                            (3) (2) (1) (0)
        diliat dari karakter paling kanan (B) (nomor 0), karakter sebelumnya A (nomor 1)
        lalu sebelum A = karakter B (nomor 2) (sama seperti karakter paling kanan yaitu B), sehingga dilihat, jika karakter sebelumnya = A (karakter di nomor 3 = karakter di nomor 1), maka karakter di nomor 3 bukan merupakan good suffix, dan lihat lagi karakter sebelumnya.
        Namun, karena pada contoh, C != A (karakter di nomor 3 != karakter di nomor 1), sehingga C merupakan good suffix dan dihitung jarak dari B (nomor 0) ke B (nomor 2). jarak = 2 -> d2 = 2
        Kalau tdk ditemukan good suffix sampai huruf paling awal dari string, maka d2 = jumlah karakter di string tersebut

        b. Aturan Baru
            //coming soon! kalo ga lupa

Sorting By Counting
contoh:
idx array = [0] [1] [2] [3] [4]
       data  =  9    8  11  10  12

Tabel Frekuensi
idx array = menyesuaikan data
... [8]  [9]  [10]  [11]  [12]
     1     1     1       1       1  
<- array="" dalam="" data="" jumlah="" p="">
Tabel Distribusi = menyimpan posisi awal data hrs dimasukkan

... [8]     [9]          [10]         [11]        [12]
     1        1             1              1             1  
      |         |              |               |              |
     v        v             v              v             v
     1   (1+1=2)   (2+1=3)   (3+1=4)   (4+1 = 5)  
<- array="" dalam="" data="" jumlah="" p=""><-isi dist.="" p="" tb.="">
<- array="" dalam="" data="" jumlah="" p=""><-isi dist.="" p="" tb.="">karena array dimulai dari index 0, maka nilai di tabel distribusi dikurang dgn 1
sehingga isi dr tabel distribusi:
[0]  [1]  [2]  [3]  [4]
 0     1    2     3     4

Read More