semester ii 2018-2019 analisis algoritma · semester ii 2018-2019 . jadwal awal: 28 januari 2019 pr...

ANALISIS ALGORITMAJIMMY TIRTAWANGSA<[email protected]>

PROGRAM PASCA SARJANA INFORMATIKAUNIVERSITAS TELKOMSemester II 2018-2019

mailto:[email protected]

Jadwal● Awal: 28 Januari 2019● PR 1: 7 Maret 2019● TUGAS 1: 21 Maret 2019● UTS: 18 Maret 2019● PR 2: 9 Mei 2019● TUGAS 2: hari ke-(UAS+3)● UAS: TBD (13/20 Mei 2019)

Pertemuan:

Tiap Senin pagi 9:00 - 11:30

Tugas, Nilai, dan IndeksSumber Penilaian:

● UAS 40%● UTS 25%● TUGAS 20%● Kuis & PR 15%

Batas Minimum Indeks:

A. > 70B. -C. -D. < 50E. -

Tugas dan Homework:● Tugaspemrograman di spoj.com

○ signup○ pilih problem yang diumumkan○ tugas submit disini

● submit PR ke email [email protected]

● perhatikan tanggal batas akhir submisi

Rujukan dan Sumber Informasi Harus:

● Cormen, Leserson, Rivest, and Sten: Introduction to Algorithms 3rd ed.

● Kleinberg and Tardos: Algorithm Design● Levitin: Design & Analysis of Algorithms● Gunakan Internet

○ Berbagai materi sejenis di tempat lain○ Google: lecture notes○ Youtube : coursewares○ eBooks

● Diskusi● Banyak latihan sendiri● Hadiri dan ikuti diskusi kelas

Jangan:● Gunakan Internet

○ Untuk Copy solusi (Baca boleh, tapi bukan untuk disalin mentah2)

○ Melakukan tindak plagiat, baik tulisan maupun program○ Saat hadir di kelas (otak anda yang sedang dilatih, situs

Google tidak perlu dilatih lagi)● Bekerja sama, nyontek, dll

○ (Boleh diskusi untuk persiapan PR, tugas dan sebelum ujian)

○ (Tapi pada saat pembuatannya harus bekerja sendiri dengan kata2 sendiri)

● Terlambat submisi● Membuat alasan untuk tidak ikut ujian

● https://jimmytirtawangsa.staff.telkomuniversity.ac.id/

Beberapa Strategi Algoritma

Beberapa Strategi Perancangan Algoritma

● Brute force● Greedy● Divide and conquer, Pruning● Branch and bound● Dynamic Programming

Dynamic Programming

Dynamic Programming

● Solusi optimal merupakan komposisi solusi optimal dari subproblem● Jika ada beberapa kemungkinan solusi optimal, solusi terpilih bebas● Idenya adalah membangun tabel solusi optimal untuk seluruh subproblem● Tabel untuk menghindari komputasi berulang untuk subproblem yang sama

Contoh situasi: deret fibonaccif0 = 0f1 = 1fn = fn-2 + fn-1 ; n > 1

Fibonacci 1 1 2 3 5 8 13 ... func fib( n int ) int { if n < 2 { return 1 } else { return fib(n-2) + fib(n-1) }}

TFIB(n)= O(1) ; n < 2 TFIB(n-1)+TFIB(n-2) ; n >= 2



TFIB(n)≃𝚹(1.6n)=O(2n)

● TFIB(n) membentuk pohon biner, dengan leaf O(1)

● Batas longgar: TFIB(n)= O(2n)

i.e. TFIB(n)=O(2n-1)+O(2n-2)+O(1)=O(2n)

● Batas ketat: TFIB(n)= O(an), a>1

TFIB(n)= an = an-1+an-2

(Bagi dg. an-2): a2 = a + 1atau a2 - a - 1 = 0a = (1+√5)/2 ≈ 1.618i.e. TFIB(n)= O(1.618

n)




func fib( n int ) int { if n < 2 { return 1 } else { var fibv [n]int = {1, 1} for i:=3; i<=n; i++ { fibv[i] = fibv[i-2] + fibv[i-1] } return fibv[n] }}

TFIB(n)=O(n)

func fib( n int ) int { if n < 2 { return 1 } else { return fib(n-2) + fib(n-1) }}



Fibonacci 1 1 2 3 5 8 13 ... var fibv [n]int = {1, 1, 0, ...}func fib( n int ) int { if fibv[n] == 0 { fibv[n] = fib(n-2) + fib(n-1) } return fibv[n]}

TFIB(n)=O(n)● melakukan penjumlahan O(1+𝝙), atau ambil

dari tabel O(1)● jumlah dari semua operasi dibawahnya● 𝝙 jumlah fibv[i]==0, i < n

Subsekuen Monotonik Terpanjang10 2 3 5 7 11 13 1 3 4 2 4 6 8 ● Subsekuen monotonik adalah bagian dari

sekuen yang nilainya merangkak naik● LS(i)=LS(i-1)+1 jika val[i] >= val[i-1], jika

tidak LS(i)=1● Subsekuen terpanjang

MLS=maxi=1..n(LS(i))

Subsekuen Monotonik Terpanjangfunc subseq(val[n] int) (pos, len int) { var seq[n] int = {1, 1, … } for i, v := range a[1:] { if val[i-1] <= val[i] { seq[i] = seq[i-1]+1 } } pos, len = max(seq) return}

● Subsekuen monotonik adalah bagian dari sekuen yang nilainya merangkak naik

● LS(i)=LS(i-1)+1 jika val[i] >= val[i-1], jika tidak LS(i)=1

● Subsekuen terpanjang MLS=maxi=1..n(LS(i))

Minimum Perkalian pada Rantai Perkalian Matrik

● Misalkan diberikan perkalian matrik M1[5x2]xM2[2x4]xM3[4x3] = M123[5x3]○ Jika urutan operasi adalah (M1[5x2]xM2[2x4])xM3[4x3]=M123[5x3], ada 100 operasi perkalian○ Tetapi jika M1[5x2]x(M2[2x4]xM3[4x3])=M123[5x3], akan hanya perlu 54 operasi perkalian

● Diberikan rantai matrik M1[s0xs1]xM2[s1xs2]x...xMn[sn-1xsn]● Cari asosiasi perkalian yang menggunakan total perkalian paling sedikit

● Berapa total perkalian yang digunakan?

Minimum Perkalian pada Rantai Perkalian Matrik

● Misalkan diberikan perkalian matrik M1[5x2]xM2[2x4]xM3[4x3] = M123[5x3]○ Jika urutan operasi adalah (M1[5x2]xM2[2x4])xM3[4x3]=M123[5x3], ada 100 operasi perkalian○ Tetapi jika M1[5x2]x(M2[2x4]xM3[4x3])=M123[5x3], akan hanya perlu 54 operasi perkalian

● Diberikan rantai matrik M1[s0xs1]xM2[s1xs2]x...xMn[sn-1xsn]● Cari asosiasi perkalian yang menggunakan total perkalian paling sedikit

● Total perkalian yang digunakan untuk rantai matrik M1..n:○ MinKali(1..n) = Mini=1..n-1(MinKali(1..i)+MinKali(ii+1..n)+si-1sisi+1)

Amortisasi

Metoda Amortisasi

Total biaya amortisasi > Total biaya aktual● Agregasi

○ Biaya amortisasi per operasi = Jumlah biaya untuk k operasi / k operasi● Akunting

○ Beberapa operasi dibebankan biaya amortisasi > biaya aktual, kredit amortisasi terakumulasi○ Operasi lain dengan dengan biaya amortisasi < biaya aktual, mendebit tabungan tersebut

● Pembiayaan○ Biaya amortisasi per operasi = biaya aktual - biaya yang telah dibebankan sebelumnya + biaya

yang akan dibebankan oleh operasi berikutnya

● Potensi○ Potensi = potensi nilai dari struktur data○ Biaya amortisasi per operasi = biaya aktual per operasi + delta Potensi○ Biaya total amortisasi = Biaya total + Potensi(akhir) - Potensi(awal)

Contoh: Memasukkan data dalam tabel

● n data tersimpan dalam tabel berukuran m, dimana m = 𝚯(n)● Ukuran tabel digandakan jika penuh, i.e. n > m● Biaya menggandakan tabel adalah 𝚯(m) = 𝚯(n)● Biaya per operasi memasukkan data 𝚯(1), tetapi 𝚯(n) jika tabel penuh● Berapa biaya total untuk n data?

○ Biaya total = 20 + 21 + 22 + … + 2 lg n = 𝚯(n)

● DPL, Biaya amortisasi per operasi = 𝚯(n)/n = 𝚯(1)

Memasukkan data dalam tabel : Akunting

● Data baru tanpa menggandakan tabel, tabung biaya c = 𝚶(1)● Data baru mengakibatkan penggandaan tabel, telah ada n/2 data yang tidak

menyebabkan penggandaan tabel, dimana tabungan c nya tidak digunakan● c.n/2 biaya dipakai untuk menutupi biaya 𝚶(n) penggandaan tabel● Biaya amortisasi untuk penggandaan tabel: 𝚶(n) - c.n/2 = 0 (sejauh c cukup)● Biaya amortisasi per operasi: 1 + c = 𝚶(1)

Memasukkan data dalam tabel : Pembiayaan

● Ketika tabel digandakan dari m menjadi 2m, tambahkan bebankan biaya 𝚯(m) ke m/2 operasi sejak penggandaan terakhir

● Setiap memasukkan data hanya dibebankan 𝚯(1)● Total biaya amortisasi per data tetap 𝚯(1)

Memasukkan data dalam tabel : Potensial

● Metoda akunting menghitung beda/sisa biaya tersedia● Metoda potensial menghitung total biaya yang dimiliki● Kedua metoda mirip, penggunaan tergantung mana yang lebih intuitif● Biaya total amortisasi = Biaya total + Potensi(akhir) - Potensi(awal)

○ Potensi(awal) = 0, dimana tabel awal adalah kosong○ Potensi(akhir) = 𝚯(n), setara banyaknya data dalam tabel (potensi biaya pemindahan)○ Biaya total = 𝚯(n)+𝚯(n)-0 = 𝚯(n)

● Biaya amortisasi per operasi = biaya aktual + delta potensi○ 𝚯(1+x) + c.(-x+1) = 𝚯(1)○ x=n jika n == 2h dan x=0 jika tidak

Struktur Data

Mengapa Data Distrukturkan?Apa yang Perlu Diperhatikan?Pilihan yang Tersedia

Struktur Data

● Komposisi data agar komputasi dapat menjadi mudah/efisien● Beberapa struktur umum:

○ Array and Record○ Linked List○ Pohon dan Graf○ Hash dan data mapping

● Beberapa operasi primitif umum terhadap struktur data:○ Insert, Append, ...○ Delete, Remove, ...○ Search and Find○ Agregasi; Sum, Count, …○ Priority Queue (pengaturan data masuk dan keluar)

Array Tidak Terurut

Simple Unordered Array: Search and FindMaxfunc Search( A[1..n], v ) → ipos ipos := n while ipos >= 1 and A[ipos] != v do ipos := ipos - 1 endwhile return iposendfunc

func FindMax( A[1..n] ) → imaximax := 1i := 2while i <= n do

if A[i] >= A[imax] then imax := ii := i + 1

endwhilereturn imax

endfunc

Simple Unordered Array: Search and FindMaxfunc Search( A[1..n], v ) → ipos ipos := n while ipos >= 1 and A[ipos] != v do ipos := ipos - 1 endwhile return iposendfunc

● O(n)● Perbedaan jika data ditemukan/tidak

ditemukan?

func FindMax( A[1..n] ) → imaximax := 1i := 2while i <= n do

if A[i] >= A[imax] then imax := ii := i + 1

endwhilereturn imax

endfunc

● O(n)● Kapan terjadi perbedaan?...

Simple Unordered Array: Insert and Deleteproc Insert( A[1..n], v )

if avail(A) thenn := n + 1A[n] := v

endifendproc

proc Delete( A[1..n], ipos )i := iposwhile i < n do

A[i] := A[i+1]i := i + 1

endwhilen := n - 1

endproc

Simple Unordered Array: Insert and Deleteproc Insert( A[1..n], v )

if avail(A) thenn := n + 1A[n] := v

endifendproc

● O(1)● Masalah dengan kapasitas array...


A[i] := A[i+1]i := i + 1

endwhilen := n - 1

endproc

● O(n)● Situasi terburuk, Situasi rata2?

Simple Unordered Array: Mark and Compressproc Mark( A[1..n], ipos )

A[ipos] := MARKEDendproc

proc Compress( A[1..n] )i := 1j := 0while i <= n do

if A[i] != MARKED thenj := j + 1A[j] := A[i]

endifi := i + 1

endwhilen := j

endproc

● Garbage Collection (GC)

Simple Unordered Array: Mark and Compressproc Mark( A[1..n], ipos )

A[ipos] := MARKEDendproc

● O(1)● Pengganti Delete● Tapi: …

○ Perlu Compress○ Ubah Search, FindMax○ Masalah tempat untuk Insert

● Rata2 kompleksitas M&C?○ Amortisasi!

proc Compress( A[1..n] )i := 1j := 0while i <= n do

if A[i] != MARKED thenj := j + 1A[j] := A[i]

endifi := i + 1

endwhilen := j

endproc

● O(n)● Waktu pemanggilan:

○ Setiap Mark/Delete○ Saat penuh/hampir penuh○ Saat under-utlized

● Menimbulkan spike, tidak cocok dengan realtime

Array Terurut

Simple Ordered Array: Search and BinarySearchfunc Search( A[1..n], v ) → ipos i := n while i >= 1 and A[i] > v do i := i - 1 endwhile /* i < 1 or A[i] < v */ if i >= 1 and A[i] == v then ipos := i else ipos := 0 endif return iposendfunc

func BinarySearch( A[1..n], v ) → ipos i := 1 j := n found := FALSE while i <= j and not found do ipos := (i+j) div 2 if A[ipos] < v then i := ipos + 1 elif A[ipos] > v then j := ipos - 1 else found := TRUE endif endwhile if not found then ipos := 0 return iposendfunc

Simple Ordered Array: Search and BinarySearchfunc Search( A[1..n], v ) → ipos i := n while i >= 1 and A[i] > v do i := i - 1 endwhile /* i < 1 or A[i] < v */ if i >= 1 and A[i] == v then ipos := i else ipos := 0 endif return iposendfunc

● O(n)● Bandingkan dengan struktur sebelumnya

func BinarySearch( A[1..n], v ) → ipos i := 1 j := n found := FALSE while i <= j and not found do ipos := (i+j) div 2 if A[ipos] < v then i := ipos + 1 elif A[ipos] > v then j := ipos - 1 else found := TRUE endif endwhile if not found then ipos := 0 return iposendfunc

● O( ?)

Simple Ordered Array: Insert and Deleteproc Insert( A[1..n], v )

if avail(A) theni := nwhile i >= 1 and A[i] > v do

A[i+1] := A[i]i := i - 1

endwhileA[i+1] := vn := n + 1

endifendproc

● Manfaat ide insertion sort


A[i] := A[i+1]i := i + 1

endwhilen := n - 1

endproc

Simple Ordered Array: Insert and Deleteproc Insert( A[1..n], v )

if avail(A) theni := nwhile i >= 1 and A[i] > v do

A[i+1] := A[i]i := i - 1

endwhileA[i+1] := vn := n + 1

endifendproc

● Equiv. satu iterasi proses Insertion Sort● O(n)


A[i] := A[i+1]i := i + 1

endwhilen := n - 1

endproc

● O(n)

Komparasi

Komparasi Array Tidak Terurut dan Terurut

Primitif U-Array U-Array* O-Array

Search O(n) O(?) O(n) / O(lg n)

FindMax O(n) O(?) O(1)

Insert O(1) O(?) O(n)

Delete O(n) M+C = O(1) + O(n)Amortisasi

O(n)

Linked List

PointersLokasi dinamik

● Akses melalui alamat (pointer)● Ada tipe data alamat/pointer (*)● Saat eksekusi ditentukan

○ Lokasi data○ Alokasi memori

● Alokasi hanya saat diminta○ Fleksibel, mudah mendapat memori

tambahan○ Adanya overhead untuk menyimpan

alamat

Lokasi statik

● Akses data melalui nama variabel● Sistem operasi dan kompilator

men-translasi nama ke alamat● Lokasi data sudah ditentukan

○ Saat kompilasi/loading○ Kebutuhan memori tetap

● Semua sudah disiapkan○ Cepat○ Tidak mudah untuk memperbesar ruang

Single Linked List

Single Linked List: Searchfunc Search( H, v ) → p p := H while p != NIL and p^value != v do p := p^next endwhile return pendfunc

func Search( A[1..n], v ) → ipos ipos := n while ipos >= 1 and A[ipos] != v do ipos := ipos - 1 endwhile return iposendfuncn

Single Linked List: FindMaxfunc FindMax( H ) → pmax pmax := H if pmax != NIL then p := pmax^next while p != NIL do if p^value >= pmax^value then pmax := p endif p := p^next endwhile endif return pmaxendfunc

func FindMax( A[1..n] ) → imax imax := 1

i := 2 while i <= n do if A[i] >= A[imax] then imax := i endif

i := i + 1endwhile

return imaxendfunc

Single Linked List: Insertproc Insert( H, v ) p := new() p^value := v p^next := H H := pendproc

proc Insert( A[1..n], v ) if avail(A) then n := n + 1 A[n] := v endifendproc

Single Linked List: Delete

Single Linked List: Deleteproc Delete( H, p ) if p == H then H := p^next else q := H { asumsi p ada } while q^next != p do q := q^next endwhile q^next := p^next endif destroy(p)endproc

● Perlu address sebelum node sebelumnya

proc Delete( A[1..n], ipos )

i := ipos

while i < n do A[i] := A[i+1] i := i + 1 endwhile

n := n - 1endproc

● Perlu proses kompresi

Komparasi Array vs. Linked List

Primitives U-Array O-Array Linked List

Search O(n) O(lg n) O(n)

FindMax O(n) O(1) O(n)

Insert O(1) O(n) O(1)

Delete O(n) O(n) O(n)

Single Ordered Linked List: Searchfunc Search( H, v ) → p p := H while p != NIL and p^value < v do p := p^next endwhile if p != NIL and p^value != v then p := NIL endif return pendfunc

● Tetap lebih cepat jika tidak ada● Tidak mungkin melakukan Binary Search

func Search( H, v ) → p p := H while p != NIL and p^value != v do p := p^next endwhile return pendfunc

Single Ordered Linked List: FindMaxfunc FindMax( H ) → pmax pmax := H if pmax != NIL then while pmax^next != NIL do pmax := pmax^next endwhile endif return pmaxendfunc

● Tetap harus merambah sampai akhir list● Sangat cepat untuk FindMin!

func FindMax( H ) → pmax pmax := H if pmax != NIL then p := pmax^next while p != NIL do if p^value >= pmax^value then pmax := p endif p := p^next endwhile endif return pmaxendfunc

Single Ordered Linked List: Insert

Single Ordered Linked List: Insertproc Insert( H, v ) p := new() p^value := v if H == NIL then p^next := H H := p else q := H r := q^next while r != NIL and r^value <= v do q := r r := q^next endwhile p^next := r q^next := p endifendproc

● Seperti menambahkan data ke array terurut, harus mencari posisi dulu

proc Insert( H, v ) p := new() p^value := v p^next := H H := pendproc

Single Ordered Linked List: Deleteproc Delete( H, p ) if p == H then H := p^next else q := H while q^next != p do q := q^next endwhile q^next := p^next endif destroy(p)endproc

● Persis sama dengan list tidak terurut

proc Delete( H, p ) if p == H then H := p^next else q := H while q^next != p do q := q^next endwhile q^next := p^next endif destroy(p)endproc


Primitives U-Array O-Array Linked List O Linked List

Search O(n) O(lg n) O(n) O(n)

FindMax O(n) O(1) O(n) O(n) or O(1)

Insert O(1) O(n) O(1) O(n)

Delete O(n) O(n) O(n) O(n)

Doubly Linked List

Ordered/Unordered Doubly Linked List: Searchfunc Search( H, T, v ) → p p := H while p != NIL and p^value < v do p := p^next endwhile if p != NIL and p^value != v then p := NIL endif return pendfunc

● Persis sama seperti versi linked list tunggal

func Search( H, T, v ) → p p := H while p != NIL and p^value != v do p := p^next endwhile return pendfunc

Ordered Doubly Linked List: FindMax/FindMinfunc FindMax( H, T ) → pmax pmax := T return pmaxendfunc

● Sama seperti array terurut

func FindMin( H, T ) → pmin pmin := H return pminendfunc

proc Insert( H, T, v ) p := new() p^value := v if H == NIL then p^next := H p^prev := T H := p T := p else q := H r := q^next while r != NIL and r^value <= v do q := r r := q^next endwhile p^next := r p^prev := q q^next := p if r == NIL then T := p else q^prev := p endif endifendproc

proc Insert( H, T, v ) p := new() p^value := v p^next := H p^prev := NIL if H != NIL then H^prev := p endif H := p if T == NIL then T := p endifendproc

● Versi terurut mirip dengan linklist tunggal terurut, harus mencari posisi dulu

Ordered/Unordered Doubly Linked List: Insert

Ordered/Unordered Doubly Linked List: Deleteproc Delete( H, T, p ) q := p^prev r := p^next if p == H then H := r else q^next := r endif if p == T then T := q else r^prev := q endif destroy(p)endproc


Primitives U-Array O-Array Linked List O Linked List D Linked List

Search O(n) O(lg n) O(n) O(n) O(n)

FindMax O(n) O(1) O(n) O(n) / O(1) O(1)

Insert O(1) O(n) O(1) O(n) O(n) / O(1)

Delete O(n) O(n) O(n) O(n) O(1)

Circular List

Doubly Circular List

Komparasi Various Linked Lists


O Linked List

D Linked List

Circular List D Circular List

Search O(n) O(lg n) O(n) O(n) O(n)

FindMax O(n) O(1) O(n) O(n) / O(1) O(1)

Insert O(1) O(n) O(1) O(n) O(n) / O(1)

Delete O(n) O(n) O(n) O(n) O(1)

Binary Search Tree

Binary Search Tree

● Syarat binary tree leftchild^value < node^value < rightchild^value● Struktur record setiap node { value, ^parent, ^left, ^right }● Daftar terurut diperoleh dengan proses perambahan secara preorder

Binary Search Tree

Binary Search Tree: Searchfunc Search( T, v ) → pv pv := T

found := FALSE while pv != NIL and not found do

if pv^value < v then pv := pv^right elif pv^value > v then pv := pv^left else found := TRUE endif endwhile

return pvendfunc

func BinarySearch( A[1..n], v ) → ipos i := 1 j := n found := FALSE while i <= j and not found do ipos := (i+j) div 2 if A[ipos] < v then i := ipos + 1 elif A[ipos] > v then j := ipos - 1 else found := TRUE endif endwhile if not found then ipos := -1 return iposendfunc

Binary Search Tree: Search and FindMaxfunc Search( T, v ) → pv pv := T found := FALSE while pv != NIL and not found do if pv^value < v then pv := pv^right elif pv^value > v then pv := pv^left else found := TRUE endif endwhile return pvendfunc

func FindMax( T ) → pmax p := T pmax := NIL while p != NIL do pmax := p p := p^right endwhile return pmaxendfunc

Binary Search Tree: Insertfunc SearchParent( T, v ) → pv p := T pv := NIL while p != NIL do pv := p if p^value < v then p := p^right else p := p^left endif endwhile return pvendfunc

proc Insert( T, v ) q := new() q^value := v q^left := q^right = NIL pv := SearchParent(T, v) if pv == NIL then q^parent := NIL T := q else q^parent := pv if pv^value > v then pv^left := q else pv^right := q endif endifendproc

Binary Search Tree: Deleteproc Delete( T, p ) repl := p^left q := FindMax(repl)

q^parent^right := q^left q^left^parent := q^parent

q^right := p^right q^left := p^left q^parent := p^parent

p^right^parent := q p^left^parent := q remove( p )endproc

● Prosedur Delete disamping belum lengkap● Kasus2 khusus

○ p merupakan node root (contoh 7)○ p anak kiri/kanan dari root○ p tidak mempunyai anak kiri/kanan○ anak kiri terbesar (contoh 6) tidak punya anak kiri

Binary Search Tree: Search* and FindM*

● Bergantung pada tinggi pohon● Asumsi jumlah node adalah n

○ Jika pohon sangat berimbang, maka tinggi maksimum adalah …○ Jika pohon sangat condong, maka tinggi maksimum adalah …○ Jika rasio tinggi panjang/pendek adalah h/s=c, dimana c konstan …○ Jika rasio adalah polinomial, h = sc, dimana c konstan, ...

Binary Search Tree: Rotasi, Kiri dan Kananproc RotateLeft( T, p ) parent := p^parent lchild := p^left

p^parent := parent^parent p^left := parent

parent^parent := p parent^right := lchildendproc

● Prosedur RotateLeft belum lengkap● Kasus2 khusus

○ p adalah root○ p tidak punya anak kiri/kanan○ p tidak punya saudara (tunggal)

● Perubahan ketinggian○ Tinggi p dan anak kanannya berkurang 1○ Tinggi anak kiri p tidak berubah○ Tinggi parent dan saudara p bertambah 1

Balance Binary Search Tree

● Pada dasarnya adalah penyesuaian tinggi dengan RotateLeft dan RotateRight● Tidak mencari pohon yang setimbang sempurna● Penyeimbangan dilakukan saat Insert dan Delete● Contoh (lihat Wikipedia)

○ 2-3 tree○ AA tree○ AVL tree○ Red-black tree○ Scapegoat tree○ Splay tree○ Treap

Komparasi dengan Binary Search Tree

*) Diluar proses SearchParent atau FindMax


O Linked List

D Linked List

(Balance) BST

Doubly Circular List

Search O(n) O(n)/O(lg n) O(n) O(n) O(n) (O(lg n)) O(n)

FindMax O(n) O(1) O(n) O(n)/O(1) O(1) (O(lg n)) O(n)

Insert O(1) O(n) O(1) O(n) O(n)/O(1) (O(lg n)) O(1)*

Delete O(n) O(n) O(n) O(n) O(1) (O(lg n)) O(1)*

Direct Addressing

● Nilai data menjadi indeks / alamat memori○ Ingat proses Counting Sort○ Pemetaan 1 → 1 dari nilai data ke alamat memori

● Insert: pengujian apakah pada lokasi tersebut sudah tersimpan data?: O(1)○ Data tidak dapat duplikat○ Memori teralokasi untuk semua kemungkinan data, bukan cuma eksisting data saja○ Sehingga cukup menyimpan tag (Boolean), True/False

● Delete: kebalikan dari Insert dalam hal penggunaan tag-nya: O(1)● Search: Pengujian nilai tag: O(1)● FindMax: ???, List seluruh data: ??? ● Alokasi memori = O(m); m = rentang data

○ Rasio beban = α = n / m

Fungsi Hash

● Pemetaan dari nilai data menjadi alamat memori○ Mengurangi kebutuhan total alokasi memori○ Selalu resiko terjadi duplikasi pemetaan○ Pemetaan n → 1 dari nilai data ke alamat memori○ Semua lokasi harus mungkin terpetakan, tidak boros memori/tanpa blackhole

● Operator modulo: h(k) = k mod m○ Jika max(k)=bm, maka high b digits dari key tidak berpartisipasi membentuk nilai hash○ Gunakan bilangan prima m

● Operator perkalian: h(k) = ⌊m(k/A-⌊k.A⌋)⌋, 0 < A < 1○ Usulan Knuth, A=0.618○ Tidak sensitif terhadap nilai m

Struktur Hash

● Insert, Delete, Search bergantung pada jumlah tabrakan● Jika jumlah tabrakan adalah O(pI), dimana pI adalah jumlah operasi Insert

○ pI = O(n), dimana n adalah jumlah data○ p = jumlah operasi SID terhadap Hash, dan juga p = O(n)○ maka secara rerata operasi SID masing2 adalah O(1)

● Bagaimana dengan worst case?○ Worst case saat fungsi hash (selalu/dipaksa) tabrakan: Θ(n)○ O(m) dimana m adalah ruang alokasi memori hash

Fungsi Hash dan ReHash

● Mungkinkah mengindari tabrakan?○ Tergantung pada kemungkinan kemunculan data○ Sebaran hasil pemetaan

● Resolusi tabrakan?○ rehash○ di-renteng

● Rehash/Probing: h(k,i) = (h(k) + hi(k)) mod m○ Problem dengan clustering, sebagian area kosong, sebagian lain padat

● Hash Universal: himpunan fungsi hash hi(k), i=1..H○ Diketahui tabrakan per satu fungsi hi(k) adalah |H|/m○ Maka rata2 tabrakan 1/m jika fungsi dapat dipilih secara acak

Fungsi Hash dan ReHash

● Operator modulo: h(k) = k mod m, rentang key 0 < k < 1○ Jika m = bd, maka high b digits dari key tidak berpartisipasi membentuk nilai hash○ Gunakan bilangan prima m

● Operator perkalian: h(k) = ⌊m(k/A-⌊k.A⌋)⌋, 0 < A < 1○ Usulan Knuth, A=0.618○ Tidak sensitif terhadap nilai m

● Worst case saat fungsi hash (selalu/dibuat) tabrakan: Θ(n)● Rehash/Probing: h(k,i) = (h(k) + hi(k)) mod m

○ Problem dengan clustering, sebagian area kosong, sebagian lain padat

● Hash Universal: himpunan fungsi hash hi(k), i=1..H○ Diketahui tabrakan per satu fungsi hi(k) adalah |H|/m○ Maka rata2 tabrakan 1/m jika fungsi dapat dipili secara acak

Colision, Chain, dan Perfect Hash

● Nilai yang ditabrakan dikumpulkan (dalam struktur list)● O(1) in worst case: Perfect Hash

○ Two level hash functions■ One primary, the usual hash function h(k)■ Secondary hash one secondary space to handle colision

○ Secondary space is automatically enlarged square to the number of collision

Komparasi dengan Struktur Hash

*) Diluar proses SearchParent atau FindMax#) Perhitungan rata-rata, bukan worst-case


O Linked List

D Linked List

BST Hash

Search O(n) O(n)/O(lg n) O(n) O(n) O(n) O(lg n)/O(n) O(1)#

FindMax O(n) O(1) O(n) O(n)/O(1) O(1) O(lg n)/O(n) ?

Insert O(1) O(n) O(1) O(n) O(n)/O(1) O(lg n)/O(1)* O(1)#

Delete O(n) O(n) O(n) O(n) O(1) O(lg n)/O(1)* O(1)#

Himpunan / Set

Bit OperationsOPERATION OPERATOR EXAMPLE EXAMPLE

SHIFT Right A >> b 100012 >> 3 = 000102 1710 >> 3 = 210

SHIFT Left A << b 000012 << 3 = 010002 110 << 3 = 810

Bit AND A & B 100112 & 001012 = 000012 1910 & 510 = 110

Bit OR A | B 100112 | 001012 = 101112 1910 | 510 = 2310

Bit Exclusive OR A ^ B 100112 ^ 001012 = 101102 1910 ^ 510 = 2210

Bit NOT ~A ~100112 = 011002 ~1910 = 1210

MINUS (2sCompl) -A -(0100112) = 1011012 -(1910) = -1910

Operasi HimpunanOperasi Notasi Example

Unversal Set U All alphabet

Empty Set ∅ ∅

Membership is a ∈ A? a ∈ {a, e, i, o, u}

Subset is A ⊆ B? {a,e} ⊆ {a,b,c,d,e}

Union A ∪ B {a,b,c,d,e} ∪ {a,e,i,o,u} = {a,b,c,d,e,i,o,u}

Intersection A ∩ B {a,b,c,d,e} ∩ {a,e,i,o,u} = {a,e}

Set Difference A - B {a,b,c,d,e} - {a,e,i,o,u} = {b,c,d}

Complement A’ vowels’ = consonants

Equivalence A ≡ B {a,e,i} ≡ {i,a,e}

Operasi HimpunanOperasi Notasi Operasi Bits

Unversal Set U -1

Empty Set ∅ 0

Membership is a ∈ A? ((1<<a)&A)

Subset is A ⊆ B? !(A & ~B)

Member Assignment A = {a} A = (1<<a)

Union A ∪ B A | B

Intersection A ∩ B A & B

Set Difference A - B A & (~B)

Complement A’ U ^ A atau ~A

Equivalence A ≡ B A == B

Komparasi dengan Struktur Himpunan

*) Diluar proses SearchParent atau FindMax#) Perhitungan rata-rata, bukan worst-case+) Untuk elemen himpunan sebanyak word-size

Primitives U Array

O Array Linked List

O Linked List

D Linked List

(Balanced) BST

Hash Set

Search O(n) O(lg n) O(n) O(n) O(n) O(lg n) / O(n) O(1)# O(1)+

FindMax O(n) O(1) O(n) O(n) / O(1) O(1) O(lg n) / O(n) ? ---

Insert O(1) O(n) O(1) O(n) O(n) / O(1) O(lg n) / O(1)* O(1)# O(1)+

Delete O(n) O(n) O(n) O(n) O(1) O(lg n) / O(1)* O(1)# O(1)+

Struktur Data Himpunan

● Untuk maksimum jumlah elemen == ukuran satu word, eg. 32 bit, 64 bit, dst.● Jumlah elemen > ukuran word → array of words

○ Array size = ⌈jumlah_elemen / ukuran_word⌉○ Pemetaan elemen ke (indeks array, offset)

■ #el = indeks*ukuran_word + offset■ indeks dimulai dari 0

● Analisis waktu○ O(array_size) = O( ⌈jumlah_elemen / ukuran_word⌉ )○ Ukuran word relatif konstan, sehingga O( ⌈jumlah_elemen / ukuran_word⌉ )○ Hanya saja operasi relatif lebih cepat ukuran_word x

■ Dibandingkan setiap elemen disimpan dalam satu lokasi tersendiri

Dukungan Bahasa Pemrograman

● (almost) All support bitwise operations● Fortran: Logical operations on Integer data

○ Operators .NOT. .AND. .OR. .NEQV. .EQV.○ Intrinsic functions: not, iand, ior, ieor

● C, Java, Python, Golang : ~, &, |, ^, ==● Pascal:

○ supports datatype SET, and PACKED datatype○ not, or, xor, shl, shr on Integer

● Python also have bitarray library

(Priority) Queue

Operasi Dasar Queue

● Clear(Q) : kosongkan atau siapkan queue Q● Enqueue(Q, v): simpan data baru v kedalam queue Q● Requeue(Q, v): simpan atau update posisi v dalam queue Q● Dequeue(Q): keluarkan satau data dari queue Q● Empty(Q): periksa status kosong queue Q

Simple Queue Structure

● Can use simple array○ Enqueue by adding/appending at end of array○ Dequeue by taking/removing values at the beginning○ Eventually will run out of space if there is no defragmentation process

● Circular array○ Index/pointer to adding/taking values are modulo by the size of the array

● Circular linked list

Priority Queue

● Using simple or sorted based on priority values○ Big overhead on maintenance

● Use priority aware structure, such as Heap○ Perform FixHeap each time Enqueue, Dequeue, and Requeue is performed○ Enqueue:

■ Add at end and do reverese FixHeap■ Fight over top places going downward

○ Requeue:■ Change the value and do FixHeap

○ Dequeue:■ Remove the top and do FixHeap

Graph

● Each graph has two set component○ A set of vertices/nodes V○ A set of edges, pairs/tuple* (u, v), here u and v are members of V

● Two graph types:○ Directed graph, where the order in tuple for each edge is important;

■ one will be starting vertex and the other the destination vertex○ Undirected graph, the order of vertices in the tuple for each edge is not important

● Simple graph:○ Has no edge leading to itself, i.e. has no tuple (v, v)○ No more than one edge from vertex u to another vertex v, i.e. only one (u, v) where u, v is in V

Undirected and Directed Graphs

Graph

● Weighted graph:○ Graph where each edge will be given a value○ In unweighted graph, each edge has no value, or all edges are assumed to weight 1

● Here we will discuss problems with:○ Simple graph○ Edges with 2-tuple only○ Can be directed or undirected○ Can be weighted or unweighted

Weighted/Unweighted Directed Graph

Data Structure for Graph

● Structure for Vertex collection○ Need to search/test existence of a vertex quite quickly○ Information which are neighbors and how many there are○ May need a mapping from-to symbolic name to an index representing the vertex○ May be a record to store values attached to an vertex○ Sometimes, for temporary set of vertices, need to add and delete vertices quickly

● Structure for Edge collection○ Need to test existence (or non-existence) of an edge○ Often need to add and remove edges from the graph quite quickly○ Information about the vertices, end points of the edges○ May be a record to store values or weight attached to each edge

Some Basic Queries on A Graph

● Vertex size, |V|● Edge size, |E|● degree of a vertex, d(v)● list of directly connected vertices from v, neighbor(v)● connectivity test, is_edge(u, v)

Directed Graph: Adjacency Matrix

Adjacency Matrix Operations, e.g.

function IsEdge(Adj[1..n][1..n], u, v) → Booleanreturn Adj[u][v] == 1

endfunction

proc ListNeighbors( Adj[1..n][1..n], v )i := 1while i <= n do

if Adj[v][i] == 1 then… // (v,i) is an edge

endifi := i + 1

endwhileendproc

Graph: Adjacency List

Adjacency List Operations, e.g.function IsEdge(AdjList, u, v) → Boolean

p := AdjList[u]while p != NIL and p^value != v do

p := p^nextendwhilereturn p != NIL

endfunction

proc ListNeighbors( AdjList, v )p := AdjList[v]while p != NIL do

… // (v,i) is an edgep := p^next

endwhileendproc

Graph: Incident Matrix

Incident Matrix Operations, e.g.

function IsEdge(IM[1..n][1..m], u, v) → Booleani := 1while i <= m and IM[u][i] != 1 and IM[v][i] != 2 do

i := i + 1endwhilereturn i <= m

endfunction

proc ListNeighbors( IM[1..n][1..m], v )i := 1while i <= m do

if IM[v][i] == 1 thenj : = 1while j <= n do

if IM[j][i] == 2 then… // (v,i) is an edgeendif

endwhileendifi := i + 1

endwhileendproc

Weighted Directed Graph: Adjacency Matrix

Some Graph Structures

Several Graph Structures

● Dense graph; |E| = Ω(|V|2)● Sparse graph; |E| = Ο(|V|)● Tree, Star, and Forest

○ Tree has no loop and |E| = |V| - 1

● Bipartite; G(V, E)○ V=K∪L and K∩L=∅○ if (u,v) ∈ E then (u ∈ K and v ∈ L) or(u ∈ L and v ∈ K)

● Complete graph○ Each vertex is connected to every other vertices in the graph

Some Graph Problems

Listing Vertices in Breadth First Search (BFS)

● Visit every vertex starting from a given vertex s ∈ V● By visiting all a vertex’s neighbors before continuing to other vertices● Label each visited vertex:

○ sequentially starting from s=1, or○ +1 from parent’s label this vertex is visited from

● Parent-child relationship is stored○ the (spanning) tree can be reconstructed

BFS Process Example

● start with s=a

BFS Algorithmproc Initialize( G, s )

forall v in G.V dov.status := UNPROCESSEDv.value := +∞v.parent := NIL

endforG.V[s].status := INPROCESSG.V[s].value := 0

endproc

● Complexity of BFS● Value assignments

○ Observe queue usage

proc BFS( G, s )Initialize(G, s)Clear(Q) // Q is a queue structureEnqueue(Q, s)while not Empty(Q) do

u := Dequeue(Q)forall v in Neighbor(G,u) do

if v.status == UNPROCESSED thenv.status := INPROCESSv.value := u.value + 1v.parent := uEnqueue(Q, v)

endifendforu.status := PROCESSED

endwhileendproc

BFS Queue Usage

● Initial operations to queue○ Clear(Q)○ Enqueue(Q, s)

● Operations inside main loop○ u := Dequeue(Q); once per iteration○ Enqueue(Q, v); forall unprocessed v neighbor of u

● Observation:○ Siblings (have same values) will be processed first○ Incoming vertices are nieces and nephews (and cousins) of vertices in waiting○ Incoming vertices will have monotonic increasing values○ At any time, in queue there will be at most two different values of vertices

BFS Labels: Shortest Path from Source s

● By Contradiction:○ Assume that there is a vertex v which value l is no the shortest value, ie. its shortest path p < l○ and u’, its neighbor, has correct shortest path as its value ○ Meaning it claims, its path should actually pass thru u’ to reach v.○ And its current path, passing thru u to reach v is longer○ That means u’ < u and u’ should come first before u into Q○ However when u’ was processed, all its neighbors are stored into Q○ If v is a neighbor of u’ then it definitely will be in Q○ And since there is no such u’, then there is a contradiction○ So v must have assigned a shortest path value, and its coming from u

Shortest Path Problem

● Given a weighted (directed) graph G=(V,E)○ Find a shortest path from s to t ○ Find shortest paths from s to any other vertices○ Find shortest paths from any vertex to any other vertices

● A vertex can be visited at most once○ Visiting more than once create a loop○ If the loop’s weight is positive, visiting more than once is unneeded○ If the loop’s weight is negative, visiting the loop indefinitely will be very unfair

Shortest Path Problem, Properties

● Shortest distance from s to v can’t be more than shortest distance from s to u + weight from u to v, if (u,v) ∈ E

○ Triangle inequality: δ(s,v) < δ(s,u) + d(u,v) where (u,v) ∈ E○ so if v.value = δ(s,v) then v.value will stop to change○ So all v.value from the graph stop to change, shortest path from s to all other nodes are found

● δ(s,t) = δ(s,v) + δ(v,t) is shortest path from s to t, if:○ δ(s,v) is shortest path from s to v and○ δ(v,t) is shortest path from v to t

● Some algorithm ideas:○ Bellman-Ford: update short path information for each vertex until no more changes○ Dijkstra: set next node short path based on “parent’s” short path

Shortest Path Example

● start with s=a

Finding Shortest Path

BFS Algorithm Revisitedproc Initialize( G, s )



endproc

● Complexity of BFS:

proc BFS( G, s )Initialize(G, s)Clear(Q) // Q is a priority queueEnqueue(Q, s)while not Empty(Q) do


if v.status != PROCESSED thenif v.value == +∞ then

v.status := INPROCESSv.value := u.value + 1v.parent := uEnqueue(Q, v)

endifendif

endforu.status := PROCESSED

endwhileendproc

Dijkstra Shortest Path Algorithmproc Initialize( G, s )



endproc

proc Dijkstra( G, s )Initialize(G, s)Clear(Q) // Q is a priority queue on valueEnqueue(Q, s)while not Empty(Q) do


if v.status != PROCESSED thend := u.value + weight(u,v)if v.value > d then

v.value := dv.parent := uRequeue(Q, v)

endifendif


endwhileendproc

Minimum Spanning Tree Problem

● A tree is …● A spanning tree (from a graph G)

○ contain all the vertices from G○ all vertices are connected○ |ET| = |V| - 1○ Weight of the tree is the sum of weight from all edges in ET

● MST has the smallest weight from all possible spanning tree in the graph● Some algorithm ideas:

○ Kruskal: Union two sub-MST will produce a new sub-MST○ Prim: Selecting a vertex with smallest weight connection to expand current sub-MST

MST Example

Prim MST Algorithmproc Initialize( G, s )



endproc

proc MST( G )s := 1 // let any vertex as the starting pointInitialize(G, s)Clear(Q) // Q is a priority queue on weightEnqueue(Q, s)while not Empty(Q) do


if v.status != PROCESSED thenif v.value > weight(u,v) then

v.value := weight(u,v)v.parent := uRequeue(Q, v)

endifendif


endwhileendproc

Listing Vertices in Depth First Search (DFS)

● Visit every vertex starting from a given vertex s ∈ V● By continue visiting first child of visited vertex, or its sibling if none exists● Label each visited vertex:

○ sequentially starting from s=1, or○ +1 from parent’s label this vertex is visited from

● Parent-child relationship is stored○ the (spanning) tree can be reconstructed

DFS Process Example

● start with s=a

DFS Algorithmproc Initialize( G, s )

forall v in G.V dov.status := UNPROCESSEDv.stime := -1v.etime := -1v.parent := NIL

endforG.V[s].status := INPROCESS

endproc

● Complexity of DFS

proc DFS( G, s )Initialize(G, s)time := 0Clear(Q) // Q is a stack structurePush(Q, s)

while not Empty(Q) do u := Pop(Q) if u.status ≠ PROCESSED then forall v in Neighbor(G, s) do

if v.status == UNPROCESSED then v.status := INPROCESS v.stime := time Push(Q, v)

endif endfor u.status := PROCESSED

endif endwhileendproc

semester ii 2018-2019 analisis algoritma · semester ii 2018-2019 . jadwal awal: 28 januari 2019 pr...

Documents