Design and Analysis Algorithm Ahmad Afif Supianto, S.Si., M.Kom
Pertemuan 08
Contents 1 3
Decrease and Conguer
2
Insertion and Selection Sort
3
DFS and BFS
4
Binary Search Tree
2
Decrease and conquer 1. Mengurangi permasalahan menjadi lebih kecil pada permasalahan yang sama 2. Selesaikan permasalahan yang lebih kecil tersebut 3. Kembangkan permasalahan yang lebih kecil itu sehingga menyelesaikan permasalahan sebenarnya 4. Dapat dilakukan dengan dengan metode top down atau bottom up
3
Variasi decrease and conquer Decrease by a constant (Mengurangi secara konstan atau tetap) The size of a problem instance is reduced by the same constant factor (usually two) on each iteration of the algorithm (dikurangi secara faktar konstan yang sama) A size reduction pattern varies from one iteration to another (Ukuran pengurangan bervariasi dari satu iterasi ke iterasi lainnya).
4
Decrease by a constant (usually by 1): insertion sort graph traversal algorithms (DFS and BFS) topological sorting algorithms for generating permutations, subsets
Decrease by a constant factor (usually by half) binary search and bisection method exponentiation by squaring multiplication à la russe Variable-size decrease Euclid’s algorithm selection by partition Nim-like games
Biasanya menggunakan algoritma rekursif.
5
Permasalahan eksponensial: Hitung xn
Brute Force:
n-1 multiplications
Divide and conquer:
T(n) = 2*T(n/2) + 1 = n-1
Decrease by one:
T(n) = T(n-1) + 1 = n-1 T(n) = T(n/a) + a-1
Decrease by constant factor: 6
log a log 2 n
= (a-1)
n
=
when a = 2
Insertion sort To sort array A[0..n-1], sort A[0..n-2] recursively and then insert A[n-1] in its proper place among the sorted A[0..n-2]
Usually implemented bottom up (nonrecursively) Example: Sort 6, 4, 1, 8, 5 6|4 1 8 5 4 6|1 8 5 1 4 6|8 5 1 4 6 8|5 1 4 5 6 8 7
Pseudo code Insertion sort
8
9
10
Kompleksitas waktu algoritma Insertion Sort:
Penyelesaian: T(n) = cn + T(n – 1) = cn + { c ⋅ (n – 1) + T(n – 2) } = cn + c(n – 1) + { c ⋅ (n – 2) + T(n – 3) } = cn + c ⋅ (n – 1) + c ⋅ (n – 2) + {c(n – 3) + T(n – 4) } = ... = cn+c⋅(n–1)+c(n–2)+c(n–3)+...+c2+T(1) = c{ n + (n – 1) + (n – 2) + (n – 3) + ... + 2 } + a = c{ (n – 1)(n + 2)/2 } + a = cn2/2+cn/2 +(a–c) = O(n2) 11
Selection sort
12
13
• Misalkan tabel A berisi elemen-elemen berikut:
• Langkah-langkah pengurutan dengan Selection Sort:
14
Kompleksitas waktu algoritma:
Penyelesaian (seperti pada Insertion Sort):
15
Depth-First Search (DFS) Mengunjungi vertex-vertex pada grafik dengan selalu bergerak dari vertex yang terakhir dikunjungi ke vertex yang belum dikunjungi, lakukan backtrack apabila tidak ada vertex tetangga yang belum dikunjungi.
Rekursif atau menggunakan stack Vertex di-push ke stack ketika dicapai untuk pertama kalinya Sebuah vertex di-pop off atau dilepas dari stack ketika vertex tersebut merupakan vertex akhir (ketika tidak ada vertex tetangga yang belum dikunjungi)
“Redraws” atau gambar ulang grafik dalam bentuk seperti pohon (dengan edges pohon dan back edges untuk grafik tak berarah/undirected graph) 16
Pseudo code DFS
17
Example: DFS traversal of undirected graph a
b
c
d
e
f
g
h
DFS traversal stack: a ab abf abfe abf ab abg abgc abgcd abgcdh abgcd …
DFS tree:
1
2
6
7
a
b
c
d
e f g 4 3 5 Red edges are tree edges and black edges are back edges. 18
h 8
Notes on DFS Time complexity of DFS is O(|V|). Why? each edge (u, v) is explored exactly once, All steps are constant time.
19
Breadth-first search (BFS) Mengunjungi vertex-vertex grafik dengan berpindah ke semua vertex tetangga dari vertex yang terakhir dikunjungi
BFS menggunakan queue Mirip dengan level ke level dari pohon merentang “Redraws” atau gambar ulang grafik dalam bentuk seperti pohon (dengan edges pohon dan back edges untuk grafik tak berarah/undirected graph)
20
Example of BFS traversal of undirected graph a
b
c
d
e
f
g
h BFS tree:
BFS traversal queue: a bef efg fg g ch hd d
1
2
6
8
a
b
c
d
e
f
g
h
3 4 5 7 Red edges are tree edges and black edges are cross edges. 21
Pseudo code BFS
22
Notes on BFS Asumsi: setiap simpul dapat membangkitkan b buah simpul baru. Misalkan solusi ditemukan pada aras ke-d Jumlah maksimum seluruh simpul: 1+b+b2 +b3 +...+bd =(bd+1 –1)/(b–1) T(n) = O(bd) Kompleksitas ruang algoritma BFS = sama dengan kompleksitas waktunya, karena semua simpul daun dari pohon harus disimpan di dalam memori selama proses pencarian. 23
Breadth First Search (grafik berarah) 2
s
4
5
3
8
7
6
24
9
Breadth First Search Shortest path from s
0
1 2
s
4
5
3
7
6
Undiscovered
Discovered
Queue: s
Top of queue
Finished
8
25
9
Breadth First Search 1 2
0
s
4
5
3
7
6
1
Undiscovered
Discovered
Queue: s 2
Top of queue
Finished
8
26
9
Breadth First Search 1 2
0
4
5
s
8
7
1
3
6
1
Undiscovered
Discovered
Queue: s 2 3
Top of queue
Finished
27
9
Breadth First Search 1 2
0
4
s
5
8
7
1
3
6
1
Undiscovered
Discovered
Queue: s 2 3 5
Top of queue
Finished
28
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
6
1
Undiscovered
Discovered
Queue: 2 3 5
Top of queue
Finished
29
9
Breadth First Search 1
2 2
0
4
s
5 already discovered: 7 don't enqueue
5
1
3
8
6
1
Undiscovered
Discovered
Queue: 2 3 5 4
Top of queue
Finished
30
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
6
1
Undiscovered
Discovered
Queue: 2 3 5 4
Top of queue
Finished
31
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
6
1
Undiscovered
Discovered
Queue: 3 5 4
Top of queue
Finished
32
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
6
3
1
2
Undiscovered
Discovered
Queue: 3 5 4
Top of queue
Finished
33
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
1
6
2
Undiscovered
Discovered
Queue: 3 5 4 6
Top of queue
Finished
34
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
1
6
2
Undiscovered
Discovered
Queue: 5 4 6
Top of queue
Finished
35
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
1
6
2
Undiscovered
Discovered
Queue: 5 4 6
Top of queue
Finished
36
9
Breadth First Search 1
2 2
0
4
s
5
8
7
1
3
1
6
2
Undiscovered
Discovered
Queue: 4 6
Top of queue
Finished
37
9
Breadth First Search 1
2 2
0
3 4
s
5
8
7
1
3
1
6
2
Undiscovered
Discovered
Queue: 4 6
Top of queue
Finished
38
9
Breadth First Search 1
2 2
0
3 4
s
5
8
7
1
3
1
6
2
Undiscovered
Discovered
Queue: 4 6 8
Top of queue
Finished
39
9
Breadth First Search 1
2 2
0
3 4
s
8
7
5
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 6 8
Top of queue
Finished
40
9
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 6 8 7
Top of queue
Finished
41
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 6 8 7 9
Top of queue
Finished
42
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 8 7 9
Top of queue
Finished
43
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 7 9
Top of queue
Finished
44
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 7 9
Top of queue
Finished
45
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 7 9
Top of queue
Finished
46
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 7 9
Top of queue
Finished
47
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 9
Top of queue
Finished
48
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 9
Top of queue
Finished
49
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue: 9
Top of queue
Finished
50
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Undiscovered
Discovered
Queue:
Top of queue
Finished
51
9
3
Breadth First Search 1
2 2
0
3 4
s
8
5
7
1
3
3
1
6
2
Level Graph
52
9
3
Latihan: Gunakan algoritma BFS dan DFS untuk menemukan pohon merentang (spanning tree) dari graf G di bawah ini jika traversalnya dimulai dari simpul e. Dalam menjawab soal ini, perlihatkan traversal BFS/DFS sebagai pohon berakar dengan e sebagai akarnya.
53
Binary Search Tree Several algorithms on BST requires recursive processing of just one of its subtrees, e.g.,
k
Searching Insertion of a new key Finding the smallest (or the largest) key
54
>k
Binary Search Tree
Not a binary search tree
A binary search tree
55
56
Searching (Find) Find X: return a pointer to the node that has key X, or NULL if there is no such node BinaryNode * BinarySearchTree::Find(const float &x, BinaryNode *t) const { if (t == NULL) return NULL; else if (x < t->element) return Find(x, t->left); else if (t->element < x) return Find(x, t->right); else return t; // match }
Time complexity: O(height of the tree) 57
Algorithm BST(x, v) //Searches for node with key equal to v in BST rooted at node x if x = NIL return -1 else if v = K(x) return x else if v < K(x) return BST(left(x), v) else return BST(right(x), v) Efficiency
worst case: C(n) = n average case: C(n) ≈ 2ln n ≈ 1.39log2 n, if the BST was built from n random keys and v is chosen randomly. 58
Aplikasi DFS dan BFS Search Engine (google, yahoo, altavista).Komponen search engine: Web Spider : program penjelajah web (web surfer) Index: basisdata yang menyimpan kata-kata penting pada setiap halaman web Query: pencarian berdasarkan string yang dimasukkan oleh pengguna (end- user)
Secara periodik (setiap jam atau setiap hari), spider menjejalahi internet untuk mengunjungi halamanhalaman web, mengambil kata-kata penting di dalam web, dan menyimpannya di dalam index. Query dilakukan terhadap index, bukan terhadap website yang aktual. 59
60
61
Bagaimana spider menjelajahi (surfing) web?
Halaman web dimodelkan sebagai graf berarah Simpul menyatakan halaman web (web page) Sisi menyatakan link ke halaman web Bagaimana teknik menjelajahi web? Secara DFS atau BFS Dimulai dari web page awal, lalu setiap link ditelusuri secara DFS sampai setiap web page tidak mengandung link. Pada setiap halaman web, informasi di dalamnya dianalisis dan disimpan di dalam basisdata index. 62
Click to edit subtitle style
