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

Week 11

Attack:
   1. Cloned RFID
       -> data numpang lewat doang ke komp org lain, tp data tsb dipake sm org lain tsb (disebut jg immigrant attack)
       -> perbedaan dgn:
           wire taping => wire taping cuma nyadap, sekedar tau data doang (cukstaw lol)
           MITM => datanya diubah sblm dikirim ke org lain, bkn cm sekedar dipake

Vulnerability:
1. Replay Attack
    -> gaperlu tau isi dari data, tp data tsb dpt dipake utk dikirim ke tmpt lain utk mendpt credential org itu

2. Reprocessed Transactions
    -> cth: org masukin username sm password, nah uname dan password itu diambil packetnya dan dipake buat login lg -> password replay
    -> cth2: biometric authentication -> cth bikin replika sidik jari pake karet -> physical replay

3. Reuse of Session Data

Countermeasure
1. Unrepeatable Protocol
    -> cth pake one time password

2. Liveness beacon
    -> cth: sequence number, nonce (memberi simple modification utk memastikan org yg sdg berkomunikasi ikut terlibat)

Similar Attack: Session Hijacking
langkah" session hijacking:
1. IP Spoofing -> ganti" header IP suatu packet agar source jadi dari si attacker
2. Tebak sequence Number (kadang bisa di predict)
3. Data dari attacker hrs sampe duluan ke destination sblm data dr sender aslinya

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

Insert, Update, Delete, Commit, Rollback, Truncate (Database)

DML:
1. Insert new Row
    insert data bisa secara implisit dan eksplisit
    implisit -> nama kolom disebutin
    INSERT INTO TableSomething (ColA, ColB) VALUES(1, 2);

    eksplisit ga sebutin nama kolom
    INSERT INTO TbSomething VALUES (1, 2, NULL);

    Insert data bisa dari table lain:
    INSERT INTO TbA (SELECT x FROM tableY WHERE ID > 1);

2. Update data
    UPDATE tableName SET colName = value WHERE condition
    bisa dimasukin subquery juga loh~
    UPDATE tbName SET colName = (SELECT x FROM tbY where condition);

3. Delete data
    DELETE FROM tbName WHERE condition;

DCL:
1. Truncate data -> sm kyk delete, tp dia autocommit
    TRUNCATE TABLE tbA;

Database Transaction
- COMMIT
- ROLLBACK

FOR UPDATE -> dimasukin di query select, fungsinya agar user lain gabisa edit data yg lg di select sm 1 user

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

Computer Security - Not All is What It Seems (Week 10)

Harm:
   Forgeries (pemalsuan)
   -> Fake Email
   -> Fake Website
   -> Fake Code, cth pdf reader fake, antivirus fake
 
Vulnerability:
 -) Integrity Failure
   Attack Details:
   1. Website Defacement: mengubah konten sebuah web
   2. Subtitute Content of Real Website: ubah sbagian kcl dr web, tujuan agar user ga aware
   3. Fake Email Message: tujuan utk phising -> memancing org utk memberikan private data
   4. Fake/Inaccurate Email Header Data: email from siapa bs diedit
   5. Web Bug: adalah sbuah invisible image (1 * 1 pixel image), utk memberikan data yg diinginkan
   6. Clickjacking: bikin user agree tanpa sadar
   7. SQL injection: mengubah statement agar menjalankan yg user inginkan

Countermeasure:
   Digital Signature
   -> Properties of Digital Signature:
   1. Nonrepudiation
   2. Authenticity
   3. Must be unforgeable, not alterable, not reusable.

   *) Encryption vs Hash
   Hash:
   - one way function
   - tujuan: biar bs tau data diubah" atau ngga
   Encryption:
   - two way function (encrypt -> decrypt / decrypt -> encrypt)
   - tujuan: biar message ga langsung bs dibaca sama org

Read More