design and analysis of algorithm decrease and conquer algorithm

Design and Analysis of AlgorithmDecrease and Conquer Algorithm

Aryo Pinandito, ST, M.MT – PTIIK Universitas Brawijaya

Decrease and Conquer Mengurangi permasalahan menjadi lebih

kecil pada permasalahan yang sama

Selesaikan permasalahan yang lebih kecil tersebut

Kembangkan permasalahan yang lebih kecil itu sehingga menyelesaikan permasalahan sebenarnya

Dapat dilakukan dengan dengan metode top down atau bottom up

Variasi decrease and conquer Mengurangi dengan sebuah constant

(Decrease by a constant)

Ukuran dari masalah dikurangi dengan faktor konstanta yang sama – biasanya dikurangi sebanyak dua pada setiap iterasi

Pola pengurangan ukuran masalah bervariasi/berbeda antara iterasi satu dengan yang lainnya

Decrease and Conquer 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.

Permasalahan Eksponensial Permasalahan: Hitung xn

Brute Force:

Divide and conquer:

Decrease by one:

Decrease by constant factor:

n-1 multiplications

T(n) = 2 * T(n/2) + 1 = n-1

T(n) = T(n-1) + 1 = n-1

T(n) = T(n/a) + a-1 = (a-1) loga n

= log2 n when a = 2

Sorting in Decrease and Conquer

Insertion Sort, Selection Sort

Insertion Sort

Insertion Sort dengan Divide and Conquer

Prosedur Merge dapat diganti dengan prosedur penyisipan sebuah elemen pada tabel yang sudah terurut (lihat algoritma Insertion Sort versi iteratif).

Divide, Conquer, and Solve

Merge

Kompleksitas Insertion Sort

Selection Sort

Pseudocode Selection Sort

Contoh Selection Sort

Kompleksitas Selection Sort

Searching

Depth-First Search (DFS)Breadth-First Search (BFS)

Binary Search Tree (BST)

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)

Pseudo code DFS

Example: DFS traversal of undirected graph

a b

e f

c d

g h

DFS traversal stack: DFS tree:

a b

e f

c d

g h

aababfabfeabfababgabgcabgcdabgcdhabgcd… Red edges are tree edges and black edges are back edges.

1 2

54

6

3

7

8

DFS : 1, 2, 4, 8, 5, 6, 3, 7

1

2 3

4 5 6 7

8

DFS : 1, 2, 3, 6, 8, 4, 5, 7

1

2 3

4 5 6 7

8

DFS : 1, 2, 5, 8, 9, 6, 3, 7, 4

1

2 4

5 6

3

7

8 9

Notes on DFS Time complexity of DFS is O(|V|). Why? each edge (u, v) is explored exactly once, All steps are constant time.

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)

Example of BFS traversal of undirected graph

BFS traversal queue:

a b

e f

c d

g h

BFS tree:

a b

e f

c d

g h

abefefgfggchhdd

Red edges are tree edges and black edges are cross edges.

1

3

2 6

4 75

8

Pseudo code BFS

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.

Breadth First Search (grafik berarah)

28

s

2

5

4

7

8

3 6 9

Breadth First Search

29

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: s Top of queue

21

Shortest pathfrom s

Breadth First Search

30

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: s 2 Top of queue

3

1

1

Breadth First Search

31

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: s 2 3 Top of queue

5

1

1

1

Breadth First Search

32

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 2 3 5 Top of queue

1

1

1

Breadth First Search

33

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 2 3 5 Top of queue

41

1

1

2

Breadth First Search

34

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 2 3 5 4 Top of queue

1

1

1

2

5 already discovered:don't enqueue

Breadth First Search

35

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 2 3 5 4 Top of queue

1

1

1

2

Breadth First Search

36

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 3 5 4 Top of queue

1

1

1

2

Breadth First Search

37

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 3 5 4 Top of queue

1

1

1

2

6

2

Breadth First Search

38

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 3 5 4 6 Top of queue

1

1

1

2

2

Breadth First Search

39

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 5 4 6 Top of queue

1

1

1

2

2

Breadth First Search

40

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 5 4 6 Top of queue

1

1

1

2

2

Breadth First Search

41

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 4 6 Top of queue

1

1

1

2

2

Breadth First Search

42

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 4 6 Top of queue

1

1

1

2

2

83

Breadth First Search

43

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 4 6 8 Top of queue

1

1

1

2

2

3

Breadth First Search

44

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 6 8 Top of queue

1

1

1

2

2

3

73

Breadth First Search

45

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 6 8 7 Top of queue

1

1

1

2

2

3

9

3

3

Breadth First Search

46

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 6 8 7 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

47

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 8 7 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

48

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 7 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

49

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 7 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

50

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 7 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

51

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 7 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

52

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

53

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

54

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: 9 Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

55

s

2

5

4

7

8

3 6 9

0

UndiscoveredDiscovered

Finished

Queue: Top of queue

1

1

1

2

2

3

3

3

Breadth First Search

56

s

2

5

4

7

8

3 6 9

0

Level Graph

1

1

1

2

2

3

3

3

BFS : 1, 2, 3, 4, 5, 6, 7, 8

1

2 3

4 5 6 7

8

BFS : 1, 2, 3, 4, 5, 6, 7, 8

1

2 3

4 5 6 7

8

BFS : 1, 2, 3, 4, 5, 6, 7, 8, 9

1

2 4

5 6

3

7

8 9

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.

Binary Search Tree Several algorithms on BST requires recursive

processing of just one of its subtrees, e.g., Searching Insertion of a new key Finding the smallest (or the largest) key

k

<k >k

Binary Search Tree

A binary search tree Not a binary search tree

Searching (Find) Find X: return a pointer to the node that has

key X, or NULL if there is no such node

Time complexity: O(height of the tree)

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}

Algoritma BST 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.

Aplikasi DFS dan BFS Search Engine (Google, Yahoo!). Komponen search engine:

1. Web Spider : program penjelajah web (web surfer)2. Index: database yang menyimpan kata-kata penting pada

setiap halaman web 3. Query: pencarian berdasarkan string yang dimasukkan

oleh pengguna (end-user)

Secara periodik (setiap jam atau setiap hari), spider menjejalahi internet untuk mengunjungi halaman-halaman web, mengambil kata-kata penting di dalam web, dan menyimpannya di dalam index.

Query dilakukan terhadap index, bukan terhadap website yang aktual.

Search Engine Google

Hasil Pencarian Search Engine Google

Bagaimana Spider Menjelajahi 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 yang ditemukan, informasi di dalamnya dianalisis dan disimpan di dalam database index.

Perbedaan BSF dan DSFBSF DSF 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

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 stack Vertex di-push ke stack

ketika dicapai untuk pertama kalinya

Vertex di-pop off dari stack ketika vertex tersebut merupakan vertex akhir (tidak ada vertex tetangga yang belum dikunjungi)

Questions?

Terima KasihThank

You

Danke Gratias

Merci

ありがとうございます

감사합니다 Kiitos

谢谢ًشكرا

Grazias

धन्यवाद