Laporan Praktikum Struktur Data dan Algoritma
-
Upload
fembi-rekrisna-grandea-putra -
Category
Education
-
view
79 -
download
3
Transcript of Laporan Praktikum Struktur Data dan Algoritma
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
BINARY HEAP
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 25 SEPTEMBER 2014
SOAL
1. Print Screen
2. Penjelasan Program
public class BinaryHeap
Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu
objek.
{}
Pembuka dan penutup suatu class/method.
private int size;
Pendeklarasian variabel size dengan tipe data integer.
public BinaryHeap()
Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu
objek.
public BinaryHeap (Comparable[] array)
Merupakan pembuka sebuah kelas yang digunakan untuk membuat suatu
objek dengan menambahkan array untuk pemilihan pada menu saat
program dijalankan.
public boolean isEmpty()
Keadaan saat heap kosong.
public boolean isFull()
Keadaan saat heap penuh.
public void buildHeap()
Pembuatan heap baru.
for(int x = size/2; x > 0; x--) {
perculateDown(x); }
Untuk x=size/2,maka x>0 dan nilai x dikurangi satu.
private void perculateDown(int x) {Comparable temp
= heap[x];int child;
Pembuatan anak/cabang pada heap.
for(; 2*x <= size; x = child) {child = 2*x;
Untuk 2*x <=size,maka x =child dan child = 2*x.
public Comparable deleteMin()
Pembuatan fungsi deleteMin pada program.
if(size == 0);Comparable min = heap[1];heap[1] =
heap[size--] perculateDown(1);
Kondisi saat heap sebelum dihapus.
public void insert(Comparable y)
Pembuatan fungsi insert pada program.
private void doubleSize()
Pendeklarasian variabel Size dengan tipe data double.
Comparable[] old = heap;
Membandingkan heap lama dengan heap yang baru.
heap = new Comparable[heap.length*2];
Proses output heap setelah diproses oleh program.
public void heapSort()
Pembuatan fungsi pengurutan/sort pada program.
int arr[] = new int[500];
Pendeklarasian array dengan tipe data integer serta penetapan batas
karakter input sebanyak 500.
int swap, p, q, r;
Pendeklarasian variabel swap,p,q,r dengan tipe data integer.
for( p = 0; p < size; p++)
Untuk p=0,p<size,maka nilai p ditambah 1.
for (q = 0; q < size-1; q++)
Untuk q=0,q<size-1,maka nilai q ditambah 1.
for (r = 0; r < size-q-1; r++)
Untuk r=0,r < size-q-1,maka nilai r ditambah 1.
for(p = 0; p < size; p++) { heap[p+1] = arr[p+1];
}
Untuk p = 0,p<size,maka nilai p ditambah 1.
for(int s = 0; s < size; s++) {
System.out.print(heap[s+1]+ " "); }
Untuk s = 0,s<size,maka nilai s ditambah 1.
public void printHeap()
Pembuatan fungsi pencetakan heap kepada pengguna pada program.
System.out.println("\nHeap : ");
Program akan menampilkan heap yang telah diproses oleh program.
for (int i = 0; i < size; i++)
Untuk I = 0,i<size,maka nilai I ditambah 1.
public static void main(String[] args)
Merupakan pembuka suatu method.Method main ini akan dikompilasi yang
paling pertama. Method di atas berparameter string[] args,dengan args
sebagai nama dari objek array dan string.
Scanner input = new Scanner(System.in);
Program akan melakukan scan terhadap setiap input yang akan dilakukan
oleh pengguna.
System.out.println("\n--Binary Heap--");
Program akan mencetak "--Binary Heap--" ke layar.
BinaryHeap jalan = new BinaryHeap();
Setelah diberi input,maka program otomatis akan menampilkan menu
utama lagi.
System.out.println("\nPilihan Menu Binary Heap");
System.out.println("1. Insert");
System.out.println("2. Delete-
Min");System.out.println("3. Heap
Sort");System.out.println("4. Print
Heap");System.out.println("5. Check Empty");
System.out.println("6. Exit");
System.out.print("Silahkan Pilih Menu = ");
Program akan mencetak pilihan menu binary heap dengan pilihan menu
Insert,Delete-min,Heap Sort,Print Heap,Check Empty,Exit.
case 1:
{System.out.println("\n");System.out.println("--
Insert--");System.out.print("Masukkan Element =
");jalan.insert(input.nextInt());System.out.printl
n("Elemen Berhasil Dimasukkan");break;
Pada menu pertama program akan menampilkan pilihan menu insert,yaitu
menu yang berfungsi untuk memasukkan angka yang akan diurutkan
dengan menggunakan algoritma binary heap.
case 2: {
System.out.println("\n");System.out.println("--
Delete-Min --"); jalan.deleteMin();
System.out.println("Elemen terkecil Berhasil
dihapus"); break;
Pada menu kedua program akan menampilkan pilihan menu Delete-
Min,yang berfungsi untuk menghapus input yang dilakukan pengguna
sebelumnya.
case 3: { System.out.println("\n");
System.out.println("--Heap Sort--");
jalan.heapSort(); System.out.println("\n"); break;
Pada menu ketiga program akan menampilkan pilihan menu Heap Sort
yang berfungsi untuk mengurutkan input yang dimasukkan oleh pengguna
yang sebelumnya telah diproses dengan menggunakan algoritma binary
heap.
case 4: {
System.out.println("\n");System.out.println("--
Heap--"); jalan.printHeap(); break;
Pada menu keempat program akan menampilkan menu Print Heap yang
berfungsi untuk mencetak heap yang telah diproses oleh program dengan
mengunakan algoritma binary heap.
case 5:
{System.out.println("\n");System.out.println("Stat
us Empty = " + jalan.isEmpty());break;
Menu ini digunakan untuk menghapus semua input yang dilakukan oleh
pengguna.
case 6: { System.err.println("Program Telah
Berhenti"); System.exit(0);
Menu ini digunakan untuk keluar dari program.
Program binary heap ini digunakan untuk mengolah input data berupa
angka yang diolah menjadi heap dengan menggunakan algoritma binary heap.
Program ini selain memiliki kemampuan mengolah angka menjadi heap juga dapat
melakukan sorting binary heap.
Mula-mula dibentuk kelas BinaryHeap sebagai awal dari pembuatan
program.Lalu untuk batas karakter inputnya dibuat melalui source code private
static final int CAPACITY = 500;.
Pembuatan heap baru dilakukan oleh program melalui
public BinaryHeap() {
size = 0;
heap = new Comparable [CAPACITY];
}
Untuk membandingkan antara input angka yang satu dengan yang
lain,program ini menggunakan
public BinaryHeap (Comparable[] array) {
size = array.length;
heap = new Comparable[array.length+1];
}
Untuk menyatakan keadaan bahwa heap dalam keadaan kosong maka
program menggunakan
public boolean isEmpty() {
return size == 0;
}
Untuk menyatakan keadaan bahwa heap dalam keadaan penuh maka
program menggunakan
public boolean isFull() {
return size == heap.length;
}
Untuk membangun heap baru maka program menggunakan
public void buildHeap() {
for(int x = size/2; x > 0; x--) {
perculateDown(x);
}
}
Untuk menyatakan fungsi deletemin maka program ini menggunakan
public Comparable deleteMin() {
if(size == 0);
Comparable min = heap[1];
heap[1] = heap[size--];
perculateDown(1);
return min;
}
Untuk melakukan sorting pada heap dilakukan melalui
public void heapSort() {
int arr[] = new int[500];
int swap, p, q, r;
for( p = 0; p < size; p++) {
arr[p+1] = (int) heap[p+1];
}
for (q = 0; q < size-1; q++) {
for (r = 0; r < size-q-1; r++) {
if(arr[r+1] > arr[r+2]) {
swap = arr[r+1];
arr[r+1] = arr[r+2];
arr[r+2] = swap;
}
}
}
for(p = 0; p < size; p++) {
heap[p+1] = arr[p+1];
}
for(int s = 0; s < size; s++) {
System.out.print(heap[s+1]+ " ");
}
}
Untuk mencetak heap yang telah diproses menggunakan
public void printHeap() {
System.out.println("\nHeap : ");
for (int i = 0; i < size; i++)
System.out.println(heap[i+1]+ " ");
System.out.println();
}
Setelah semua source code diproses, maka hasil run program adalah
Mula-mula dilakukan pemilihan menu no.1 (insert). Angka yang
dimasukkan adalah 20, 37, 25, 63, 61, 92, 17, 21, 12, 55, 47, 45, 64, 83, 73. Setelah
di-input-kan semua data-datanya, maka yang harus dilakukan setelahnya adalah
melakukan heap sort. Untuk melakukan heap sort, dilakukan pemilihan menu no.3.
Setelah dilakukan pemilihan menu heap sort, maka program akan menampilkan
Output yang dikeluarkan adalah 12, 17, 20, 21, 25, 37, 45, 47, 55, 61, 63,
64, 73, 83, 92. Setelah menggunakan program, jika ingin keluar dari program,
maka yang harus dilakukan adalah memilih menu no.6 (exit). Setelah dipilih menu
exit, maka program akan berhenti bekerja.
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
SPLAY TREE
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 9 OKTOBER 2014
SOAL
1. Print Screen
2. Analisis
Program ini berguna untuk mengimplementasikan splay tree pada Java.
Program ini terdiri dari beberapa kelas, yaitu SplayNode, SplayTree, dan
Test_SplayTree. Di kelas SplayNode, terdapat konstruktor SplayNode dengan
objek left, right, dan parent dan variabel elemen bertipe integer.
Di kelas SplayTree, terdapat metode-metode yang dirujuk oleh menu pada
program ini. Metode SplayTree mengubah nilai variabel root menjadi null. Metode
isEmpty bertipe boolean, akan menentukan apakah splay tree berisi data atau null.
Metode clear berguna untuk menghapus seluruh data. Metode insert berguna untuk
menyisipkan data. Metode remove bertipe boolean berguna untuk mengecek
ketersediaan data yang akan dihapus. Metode remove bertipe void berguna untuk
menghapus data. Metode countNodes berguna untuk menghitung jumlah node
yang ada. Metode search berguna untuk mencari ketersediaan node di dalam splay
tree dengan mengembalikan kepada metode findNode. Metode findNode berguna
untuk menemukan node di dalam splay tree. Metode inorder berguna untuk
menampilkan urutan node dalam inorder. Metode preorder berguna untuk
menampilkan urutan node dalam preorder. Metode postorder berguna untuk
menampilkan urutan node dalam postorder.
Di dalam kelas Test_SplayTree berisi perintah untuk memindai masukan
dari pengguna dan mencetak tulisan ke layar. Menu 1 untuk memasukkan data dan
memanggil metode insert. Menu 2 untuk menghapus data, dengan memanggil
metode isEmpty terlebih dahulu, jika node masih null, maka menampilkan tulisan
“Tree Kosong”. Jika data sudah terisi, maka pengguna dapat memasukkan data
yang akan dihapus, kemudian program memanggil metode search untuk
mencarinya dan memanggil metode remove untuk menghapusnya. Jika data
berhasil dihapus oleh metode remove, maka muncul pesan bahwa data telah
dihapus. Jika metode search tidak berhasil menemukan data yang akan dihapus,
maka muncul pesan bahwa data tidak ditemukan. Menu 3 berguna untuk mencari
data dengan memanggil metode search. Menu 4 berguna untuk menghitung jumlah
node yang ada dalam splay tree dengan memanggil fungsi countNodes. Menu 5
berguna untuk mengecek status kekosongan pada splay tree dengan memanggil
metode isEmpty. Menu 6 untuk menghapus seluruh data dengan memanggil
metode clear. Menu 7 untuk keluar dari program. Jika salah memilih menu atau
angka yang dipilih di luar angka 1—7, maka akan muncul pesan bahwa masukan
salah dan pengguna boleh mencoba lagi. Di setiap kali selesai memilih menu dan
selesai melakukan perintah, maka program otomatis mencetak urutan node dalam
postorder, preorder, dan inorder dengan memanggil metode postorder, preorder,
dan inorder.
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
TRIES
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 16 OKTOBER 2014
SOAL
1. Print Screen
2. Analisis
Program ini berguna untuk memasukkan masukan berupa string dari
pengguna dan menghitung jumlah huruf pada masing-masing kata. Kemudian
pengguna dapat mencari kata apa yang terdapat dalam string tadi, program akan
mencarinya dan menemukannya di indeks tertentu.
Program ini terdiri dari dua kelas, yaitu PrefixTree dan TrieNode. Di kelas
PrefixTree, terdapat metode createTree yang berguna untuk membuat tree dengan
mengembalikan nilai ke TrieNode baru. Metode insertWord berguna untuk
menyisipkan kata. Metode find berguna untuk menemukan kata yang ingin dicari
pengguna di dalam kalimat yang dimasukkan sebelumnya. Metode printTree
berguna untuk mencetak jumlah huruf pada setiap kata yang dimasukkan
pengguna.
Di dalam metode main, terdapat perintah untuk memindai masukan dari
pengguna dan mencetak tulisan ke layar. Pada awalnya, program memanggil
metode createTree untuk membuat tree. Setelah itu, pengguna dapat memasukkan
kalimat ke dalam program. Program akan memanggil metode insertWord dan
menghitung jumlah huruf pada setiap kata yang dimasukkan. Setelah itu, program
meminta masukan dari pengguna terhadap kata apa yang ingin dicari oleh
pengguna dalam kalimat sebelumnya dengan memanggil fungsi searchWord. Jika
kata yang dicari pengguna terdapat dalam kalimat tersebut, maka program akan
menampilkannya dan menghitung di indeks berapa kata tersebut diawali. Jika kata
yang dicari pengguna tidak ditemukan program dalam kalimat tersebut, maka
program akan menampilkan pesan bahwa kata tidak dapat ditemukan.
Huruf Indeks ke-
m 1
a 2
h 3
a 4
s 5
i 6
s 7
w 8
a 9
10
Kelas TrieNode berguna untuk mendeklarasikan
beberapa variabel yang berguna untuk menjalankan
program. Contoh penggunaannya, pengguna memasukkan
string berupa “mahasiswa mipa merdeka”, maka program
akan menghitung jumlah huruf dari setiap kata, yaitu 9
huruf untuk “mahasiswa”, 4 huruf untuk “mipa”, dan 7
huruf untuk “merdeka”. Setelah itu program meminta
pengguna untuk memasukkan kata yang ingin dicari kalimat
tersebut. Jika pengguna ingin mencari kata “mipa”, maka
program akan mencarinya dalam kalimat tadi dan
menemukan bahwa huruf “m” dari kata “mipa” terdapat di
indeks ke-11, dengan catatan bahwa karakter spasi juga
dihitung sebagai indeks tersendiri.
Jika pengguna mencoba lagi memasukkan kalimat yang sama dan mencoba
mencari kata yang tidak ada dalam kalimat tersebut, misalnya kata “siswa”, maka
program akan menampilkan tulisan “The word was NOT found”, walaupun huruf-
huruf tersebut terdapat dalam kata mahasiswa secara berurutan, namun program
tidak membacanya sebagai satu kata yang utuh, sehingga tidak dianggap sebagai
salah satu kata yang terdapat dalam kalimat tersebut.
m 11
i 12
p 13
a 14
15
m 16
e 17
r 18
d 19
e 20
k 21
a 22
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
ALGORITMA GREEDY
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 23 OKTOBER 2014
1. Integer Knapsack
a. Print Screen
b. Analisis
Program ini berguna untuk mengimplementasikan algoritma Greedy pada
Java, yaitu memasukkan objek satu persatu. Setelah objek dimasukkan, tidak dapat
dikeluarkan lagi. Pada awalnya, program mendeklarasikan beberapa variabel.
Kemudian program menerima masukan dari pengguna berupa kapasitas
maksimum, jumlah barang, Wi (berat) dari masing-masing barang, dan Pi
(keuntungan) dari masing-masing barang.
Misalnya pengguna memasukkan kapasitas maksimum bernilai 16 dan
jumlah barang bernilai 4. Maka pengguna akan diminta memasukkan berat dan
keuntungan dari masing-masing barang sebanyak 4 kali.
Indeks ke- Wi Pi PWi = Pi / Wi
1 8 4 0.5
2 5 2 0.4
3 4 8 2.0
4 10 2 0.2
Pertama, program akan menentukan Greedy by Profit dengan mengurutkan
keuntungan (Pi) dari yang tertinggi ke yang terendah. Sehingga, program akan
mendapatkan barang indeks ke-3 dan 1 dengan total keuntungannya adalah 12 dan
total bobotnya adalah 12. Indeks ke-2 dan 4 sebagai urutan keuntungan selanjutnya
tidak dapat dimasukkan lagi. Karena jika salah satu dari keduanya dimasukkan,
maka total bobotnya (17) akan melebihi kapasitas maksimum yang ditentukan (16).
Kedua, program akan menentukan Greedy by Weight dengan mengurutkan
berat (Wi) dari yang terkecil ke yang terbesar. Sehingga, program akan
mendapatkan barang indeks ke-3 dan 2 dengan total bobotnya adalah 9 dan total
keuntungannya adalah 10. Indeks ke-1 sebagai urutan bobot selanjutnya tidak
dapat dimasukkan lagi. Karena jika dimasukkan, maka total bobotnya (17) akan
melebihi kapasitas maksimum yang ditentukan (16).
Terakhir, program akan menentukan Greedy by Density dengan
mengurutkan kepadatan dari yang terbesar ke yang terkecil. Sehingga, program
akan mendapatkan barang indeks ke-3 dan 1 dengan total bobotnya adalah 12 dan
total keuntungannya adalah 12. Indeks ke-2 sebagai urutan kepadatan selanjutnya
tidak dapat dimasukkan lagi. Karena jika dimasukkan, maka total bobotnya (17)
akan melebihi kapasitas maksimum yang ditentukan (16).
2. Pemilihan Aktivitas
a. Print Screen
b. Analisis
Program ini digunakan untuk mengimplementasikan algoritma pada Java,
yaitu berkaitan dengan masalah pemilihan aktivitas. Pada kasus ini, kita dapat
memilih aktivitas mana yang dapat dilakukan dengan mengetahui Si (waktu mulai)
dan Fi (waktu berakhirnya) aktivitas tersebut.
Misalnya, pengguna memasukkan total aktivitas sebanyak 3 dengan
masing-masing waktu mulai dan berakhirnya adalah 11 dan 15, 13 dan 21, serta 10
dan 12. Jika pengguna memasukkan nilai Fi yang lebih kecil daripada nilai Si,
maka program akan menampilkan pesan kesalahan dan meminta pengguna untuk
memasukkan kembali nilai yang benar.
Indeks ke- Si Fi
1 11 15
2 13 21
3 10 12
Selanjutnya, program akan mengurutkan aktivitas dari nilai Si yang terkecil
ke yang terbesar.
Indeks ke- Si Fi
1 10 12
2 11 15
3 13 21
Kemudian, program akan menentukan aktivitas mana yang dapat dilakukan
pengguna dengan tidak memilih aktivitas yang waktunya bertabrakan, sehingga
program memilih aktivitas dengan indeks ke-1 dan 3 dengan jumlah aktivitas 2.
3. Penukaran Uang
a. Print Screen
b. Analisis
Program ini digunakan untuk mengimplementasikan algoritma Greedy pada
Java, yaitu berkaitan dengan masalah penukaran uang, dengan memilih koin
dengan nilai terbesar dari himpunan koin yang tersisa.
Misalnya, pengguna akan memiliki 5 jenis koin dengan nominal yang
berbeda-beda (50, 100, 200, 500, dan 1000). Maka, program akan mengurutkan
nilai koin-koin tersebut dari yang terbesar ke yang terkecil. Setelah itu,
pengguna ingin mendapatkan uang sejumlah 4950 dari koin-koin tersebut,
kemudian program akan menjumlahkan koin-koin tersebut dengan fungsi
while. Sehingga jika nilai uang melebihi nilai total, maka perintah tersebut
akan berhenti dijalankan. Selanjutnya, program akan menampilkan urutan koin
yang dipakai untuk mendapatkan sejumlah uang tersebut dan menampilkan
jumlah minimal koin yang dibutuhkan.
4. Penjadwalan
a. Print Screen
b. Analisis
Program ini digunakan untuk mengimplementasikan algoritma Greedy pada
Java, yaitu berkaitan dengan masalah penjadwalan. Pada kasus ini, program
menggunakan konsep algoritma Greedy untuk meminimalisasi waktu dalam
sistem penjadwalan. Pengguna akan memilih pelanggan yang membutuhkan
waktu pelayanan terkecil di antara pelanggan lain yang belum dilayani.
Program ini akan mengeksekusi kelas Penjadwalan dan memanggil metode
utama yang bernama main. Selanjutnya, program akan mendeklarasikan
variabel-variabel yang digunakan dalam program ini. Selanjutnya, pengguna
memasukkan banyak proses, yaitu 3 yang masuk ke variabel n. Lalu, pengguna
memasukkan nilai variabel t dengan operasi perulangan.
Selanjutnya akan dilakukan proses pengurutan variabel t dari nilai terkecil
ke nilai terbesar dari nilai t. Selanjutnya akan dilakukan proses menentukan
penjadwalan. Dengan menginisialisasikan nilai jml = 0 dan tot = 0, maka
program melakukan proses perulangan. Setelah kondisi tidak memenuhi, maka
proses looping berhenti, dan program akan menampilkan nilai kemungkinan
total aktivitas minimum atau nilai akhir dari variabel tot yaitu 29.
5. Fractional Knapsack
a. Print Screen
b. Analisis
Program ini digunakan untuk mengimplementasikan algoritma Greedy pada
Java yang berkaitan dengan masalah fractional knapsack. Program
menggunakan konsep algoritma Greedy dengan memasukkan objek satu
persatu ke dalam knapsack. Setelah objek dimasukkan, objek tersebut tidak
bisa dikeluarkan lagi.
Program ini akan mengeksekusi kelas Fractional_knapsack dan memanggil
metode utama yang bernama main. Selanjutnya akan melakukan pembuatan
objek baru bernama fk di dalam kelas Fractional_knapsack. Kemudian
memanggil metode fill melalui objek fk.
Selanjutnya pengguna memasukkan jumlah barang, yaitu 3 yang masuk ke
variabel nItems. Lalu pengguna memasukkan berat dan keuntungan dari
masing-masing barang. Selanjutnya pengguna memasukkan kapasitas
maksimum, yaitu 20 yang masuk ke variabel W. Lalu program melakukan
proses untuk mencari solusi optimal.
Selanjutnya, program menentukan Greedy by profit dengan mencari nilai
keuntungan terbesar yaitu 25 dengan bobot 18. Karena masih memenuhi, lalu
mencari nilai keuntungan yang terbesar selanjutnya yaitu 24 dengan bobot 15.
Jika bobotnya dijumlahkan (18 + 15 = 33), maka kondisinya tidak memenuhi,
sehingga diambil sebagian saja, yaitu 24 x (20 - 18) / 15 = 24 x 2 / 15 = 3,2.
Maka menghasilkan keuntungan sebesar 25 + 3,2 = 28,2 dan bobot senilai 18 +
(2 / 15 x 15) = 18 + 2 = 20.
Kemudian, program menentukan Greedy by weight dengan mencari nilai
bobot yang terkecil, yaitu 10 dengan keuntungan 15. Karena masih memenuhi,
lalu mencari nilai bobot yang terkecil selanjutnya, yaitu 15 dengan keuntungan
24. Jika menjumlahkan bobotnya (10 + 15 = 25), maka kondisinya tidak
memenuhi, sehingga diambil sebagian saja, yaitu 15 x (20 - 10) / 15 = 15 x 2 /
3 = 10. Maka menghasilkan bobot bernilai 10 + 10 = 20 dan keuntungan
bernilai 15 + (2 / 3 x 24) = 15 + 16 = 31.
Lalu, program menentukan Greedy by density dengan mencari nilai
kepadatan yang terbesar, yaitu 1,6 dengan bobot 15. Karena masih memenuhi,
lalu mencari nilai kepadatan yang terbesar selanjutnya, yaitu 1,5 dengan bobot
10. Jika menjumlahkan bobotnya (15 + 10 = 25), maka kondisinya tidak
memenuhi, sehingga diambil sebagian saja, yaitu 10 x (20 - 15) / 10 = 10 x 1 /
2 = 5. Maka menghasilkan bobot senilai 15 + 5 = 20 dan keuntungan sebesar
24 + (1 / 2 x 15) = 24 + 7,5 = 31,5.
Dengan membandingkan hasil tersebut satu persatu, sehingga total hasil
optimal terletak pada nilai 31,5 dan total bobot optimal terletak pada nilai 20,
dengan solusi optimal pada barang ke-2 dan barang ke-3.
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
HUFFMAN CODE
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 20 NOVEMBER 2014
1. Integer Knapsack
a. Print Screen
b. Analisis
Program ini merupakan program sederhana yang berfungsi untuk
mengimplementasikan Huffman Code pada Java. Dalam pembuatannya, program
ini terbagi menjadi beberapa kelas yang terdapat dalam paket bernama Huffman.
Program ini juga mengimpor beberapa kelas dari koleksi perpustakaan Java, seperti
PriorityQueue dan Scanner. Program ini memiliki empat kelas dengan tipe,
metode, dan fungsi yang berbeda.
Kelas HuffmanTree bertipe abstrak mengimplementasikan antar muka
Comparable dengan tipe generik HuffmanTree. Kelas ini berfungsi memberikan
frekuensi dari kelas ini sendiri dengan mendeklarasikan variabel frequency bertipe
integer dan memproses metode HuffmanTree dengan parameter freq bertipe
integer. Parameter freq dinyatakan sebagai variabel frequency yang berarti nilai
freq sama dengan frequency.
Kelas HuffmanLeaf merupakan subkelas dari HuffmanTree dan memiliki
dua parameter, yaitu integer freq dan karakter val. Kelas ini beroperasi dengan
mengakses variabel freq pada superkelasnya dan memberikan nilai val kepada
value.
Kelas HuffmanNode merupakan subkelas dari HuffmanTree yang
mendeklarasikan variabel left dan right yang merupakan subpohon dari
HuffmanTree. Metode HuffmanNode dengan parameter Huffman Tree l dan
HuffmanTree r akan mengakses variabel l.frequency dan r.frequency dari
superkelasnya dan memberikan nilai l kepada left dan r kepada right.
Kelas HuffmanCode merupakan kelas publik yang dapat diakses oleh
metode dan kelas apapun dalam proyek ini. Kelas ini memiliki empat metode
dengan fungsi yang berbeda. Kelas ini mendeklarasikan variabel array string statis
bernama huruf dan kode dengan masing-masing variabel tersebut bernilai indeks
array 256. Kelas ini juga mendeklarasikan variabel integer statis bernama k
bernilai awal 0.
Di dalam kelas HuffmanCode terdapat metode buildTree yang membangun
sebuah tree dari HuffmanTree. Metode ini membuat objek baru bernama trees
dengan tipe PriorityQueue. Kemudian melakukan proses looping berdasarkan nilai
variabel charFreqs.length. Jika nilai charFreqs[i] bernilai lebih dari nol, maka
proses selanjutnya adalah mengakses metode offer pada objek trees dengan
membuat HuffmanLeaf baru berparameter charFreqs[i] dan char i. Program akan
melakukan assert terhadap trees.size dengan nilai lebih dari nol dan melakukan
looping sampai hanya tersisa satu tree. Metode ini akan mengembalikan nilai
trees.poll pada objek yang mengaksesnya.
Metode printCodes dalam kelas HuffmanCode dengan parameter
HuffmanTree tree dan StringBuffer prefix berfungsi untuk melakukan proses
dekode. Proses dilakukan dengan memberikan nilai tree tidak sama dengan null.
Jika nilai tree instanceof HuffmanLeaf sama dengan HuffmanLeaf tree, maka
program akan memberikan keluaran berupa nilai yang terdapat pada leaf.value,
leaf.frequency, dan prefix. Program akan memberikan nilai tambah kepada
variabel cetak dari nilai pada variabel leaf.value. Variabel huruf[k] diberi nilai
sama dengan variabel cetak dan variabel kode[k] diberikan nilai yang sama dengan
prefix.toString. Akan tetapi, jika nilai node pada HuffmanNode bernilai sama
dengan tree pada HuffmanNode, maka program akan memberikan nilai 0 pada
prefix.append dan mengakses prefix.deleteCharAt(prefix.length() - 1).
Metode yang lainnya adalah printAll yang berfungsi untuk mencetak hasil
dekode dari HuffmanTree. Metode ini membuat objek HashMap dengan parameter
generik String, String dengan nama compressed, mendeklarasikan nilai kosong dari
variabel string d, dan memberikan nilai compressed.put(huruf[i], kode[i]). Jika
nilai variabel y kurang dari h.length(), maka program akan menambahkan nilai
h.charAt(y) kepada variabel d dan menampilkan keluaran berupa hasil
pengaksesan compressed.get(d). Selanjutnya, program memberikan nilai kosong
pada variabel d.
Metode main yang merupakan metode terakhir dan utama berfungsi untuk
menjalankan program. Metode ini meminta pengguna untuk memasukkan string
yang akan didekode dan menyimpannya dalam variabel menggunakan perintah
Scanner. Metode ini juga mendeklarasikan nilai dari variabel array integer
charFreqs dengan indeks 256. Dengan menggunakan looping for (char c :
test.toCharArray), program membaca masing-masing karakter string yang
dimasukkan oleh pengguna dan merekam, menghitung, serta menyimpan
frekuensinya. Program akan membuat tree dari masing-masing karakter tersebut
dengan mengakses HuffmanTree, menampilkan hasil dari metode printCodes, dan
mencetak semua hasilnya, serta membuat dekode berdasarkan konsep tree yang
telah dibuat..
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
DISJOINT SET
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 4 DESEMBER 2014
1. UnionFind
a. Print Screen
b. Analisis
Program ini memiliki beberapa metode yang berguna untuk
mengimplementasikan disjoint set pada Java.
Metode String toString bersifat publik dan berguna untuk mengembalikan
nilai UnionFind yang nantinya akan digunakan pada metode utama.
Metode UnionFind bersifat publik, berparameter max yang bertipe integer,
dan berguna untuk membuat indeks max dari variabel _parent dan _rank dan
menyatakan nilai variabel i dengan fungsi perulangan terhadap variabel _parent
indeks ke-i.
Metode union bersifat publik, bertipe void, berparameter i dan j yang
bertipe integer, dan berguna untuk menggabungkan komponen yang ada di dalam
himpunan disjoint set.
Metode find bersifat publik, bertipe integer, berparameter i yang bertipe
integer, dan berguna untuk menemukan komponen yang ada di dalam himpunan
disjoint set dengan menyatakan bahwa nilai variabel p sama dengan variabel
_parent indeks ke-i, kemudian mengembalikan nilai i jika nilai variabel i sama
dengan p dan mengembalikan nilai variabel _parent indeks ke-i sama dengan
metode find berparameter p jika tidak sama.
Metode utama berguna untuk mencetak keluaran pada program. Pertama,
program membuat objek uf dari kelas UnionFind berparameter 5 dan mencetaknya
ke layar. Parent disimbolkan dengan huruf a, anggota disimbolkan dengan huruf p,
dan rank disimbolkan dengan huruf r.
a 0 1 2 3 4
p -1 -1 -1 -1 -1
r 0 0 0 0 0
Selanjutnya, program memanggil metode union melalui objek uf dengan
parameter 1 dan 2. Proses ini akan menggabungkan komponen ke-1 dan 2. Karena
rank ke-1 dan 2 memiliki nilai yang sama (0), maka program akan mengubah nilai
anggota ke-2 menjadi nilai komponen ke-1 (1) dan menambahkan 1 ke nilai rank
ke-1.
a 0 1 2 3 4
p -1 -1 1 -1 -1
r 0 1 0 0 0
Setelah itu, program memanggil metode union melalui objek uf dengan
parameter 3 dan 4. Proses ini akan menggabungkan komponen ke-3 dan 4. Karena
rank ke-3 dan 4 memiliki nilai yang sama (0), maka program akan mengubah nilai
anggota ke-4 menjadi nilai dari komponen ke-3 (3) dan menambahkan 1 ke nilai
rank ke-3.
a 0 1 2 3 4
p -1 -1 1 -1 3
r 0 1 0 1 0
Kemudian, program memanggil metode union melalui objek uf dengan
parameter 1 dan 0. Proses ini akan menggabungkan komponen ke-1 dan 0. Karena
nilai rank ke-1 lebih besar daripada nilai rank ke-0 (1>0), maka program akan
mengubah nilai anggota ke-0 menjadi nilai dari komponen ke-1 (1).
a 0 1 2 3 4
p 1 -1 1 -1 3
r 0 1 0 1 0
Selanjutnya, program memanggil metode union melalui objek uf dengan
parameter 1 dan 3. Proses ini akan menggabungkan komponen ke-1 dan 3. Karena
rank ke-1 dan 3 memiliki nilai yang sama (1), maka program akan mengubah nilai
anggota ke-3 menjadi nilai dari komponen ke-1 (1) dan menambahkan 1 ke nilai
rank ke-1.
a 0 1 2 3 4
p 1 -1 1 1 3
r 0 2 0 1 0
Terakhir, program memanggil metode find melalui objek uf dengan
parameter 4. Karena parent ke-4 bernilai sama dengan parameter (4), maka
program akan mengembalikan nilai kepada parameter (4) dan tidak terjadi
perubahan komponen.
a 0 1 2 3 4
p 1 -1 1 1 3
r 0 2 0 1 0
2. UnionFind2
a. Print Screen
b. Analisis
Program ini memiliki beberapa metode yang digunakan untuk
mengimplementasikan disjoint set pada Java.
Metode String toString bersifat publik dan berguna untuk mengembalikan
nilai UnionFind yang nantinya akan digunakan pada metode utama.
Metode UnionFind2 bersifat publik, berparameter max yang bertipe
integer, dan berguna untuk membuat indeks max dari variabel _parent dan _rank
dan menyatakan nilai variabel i dengan fungsi perulangan terhadap variabel
_parent indeks ke-i.
Metode union bersifat publik, bertipe void, berparameter i dan j yang
bertipe integer, dan berguna untuk menggabungkan komponen yang ada di dalam
himpunan disjoint set.
Metode find bersifat publik, bertipe integer, berparameter i yang bertipe
integer, dan berguna untuk menemukan komponen yang ada di dalam himpunan
disjoint set dengan mengembalikan nilai i jika nilai variabel i sama dengan _parent
indeks ke-i. Jika nilainya tidak sama, program akan membuat variabel integer baru
bernama result yang bernilai sama dengan metode find berparameter variabel
_parent indeks ke-i, menyatakan bahwa nilai variabel _parent indeks ke-i sama
dengan variabel result, dan mengembalikan nilai kepada result.
Metode utama berguna untuk mencetak keluaran pada program. Pertama,
program membuat objek uf dari kelas UnionFind berparameter 5 dan mencetaknya
ke layar. Parent disimbolkan dengan huruf p, anggota disimbolkan dengan huruf a,
dan rank disimbolkan dengan huruf r.
p 0 1 2 3 4
a -1 -1 -1 -1 -1
r 0 0 0 0 0
Selanjutnya, program memanggil metode union melalui objek uf dengan
parameter 1 dan 2. Proses ini akan menggabungkan komponen ke-1 dan 2. Karena
rank ke-1 dan 2 memiliki nilai yang sama (0), maka program akan mengubah nilai
anggota ke-2 menjadi nilai komponen ke-1 (1) dan menambahkan 1 ke nilai rank
ke-1.
p 0 1 2 3 4
a -1 -1 1 -1 -1
r 0 1 0 0 0
Setelah itu, program memanggil metode union melalui objek uf dengan
parameter 3 dan 4. Proses ini akan menggabungkan komponen ke-3 dan 4. Karena
rank ke-3 dan 4 memiliki nilai yang sama (0), maka program akan mengubah nilai
anggota ke-4 menjadi nilai dari komponen ke-3 (3) dan menambahkan 1 ke nilai
rank ke-3.
p 0 1 2 3 4
a -1 -1 1 -1 3
r 0 1 0 1 0
Kemudian, program memanggil metode union melalui objek uf dengan
parameter 1 dan 0. Proses ini akan menggabungkan komponen ke-1 dan 0. Karena
nilai rank ke-1 lebih besar daripada nilai rank ke-0 (1>0), maka program akan
mengubah nilai anggota ke-0 menjadi nilai dari komponen ke-1 (1).
p 0 1 2 3 4
a 1 -1 1 -1 3
r 0 1 0 1 0
Selanjutnya, program memanggil metode union melalui objek uf dengan
parameter 1 dan 3. Proses ini akan menggabungkan komponen ke-1 dan 3. Karena
rank ke-1 dan 3 memiliki nilai yang sama (1), maka program akan mengubah nilai
anggota ke-3 menjadi nilai dari komponen ke-1 (1) dan menambahkan 1 ke nilai
rank ke-1.
p 0 1 2 3 4
a 1 -1 1 1 3
r 0 2 0 1 0
Terakhir, program memanggil metode find melalui objek uf dengan
parameter 4. Karena parent ke-4 bernilai sama dengan parameter (4), maka
program akan mengembalikan nilai kepada parameter (4) dan tidak terjadi
perubahan komponen.
p 0 1 2 3 4
a 1 -1 1 1 3
r 0 2 0 1 0
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
DIVIDE AND CONQUER
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 11 DESEMBER 2014
1. Tes1
a. Print Screen
Tes1
MergeSort
BubbleSort
Output
b. Analisis
Program di dalam paket Tes1 yang memiliki beberapa kelas, yaitu Tes1,
MergeSort, dan BubbleSort ini berguna untuk mengurutkan data acak yang
awalnya tidak berurutan dengan algoritma pengurutan MergeSort dan BubbleSort.
Kelas Tes1 yang bersifat publik memiliki satu metode yang merupakan
metode utama. Metode ini menggunakan fungsi Random untuk membuat variabel
data bertipe integer yang memiliki array sebanyak variabel limit. Variabel limit
dideklarasikan bertipe integer dan bernilai 200.
Program akan mencetak 200 variabel data yang tersusun dalam array
menggunakan fungsi perulangan for. Dengan nilai awal variabel i = 0 dan selama
nilainya masih lebih kecil daripada limit (200), program akan mendeklarasikan
variabel data indeks ke-i menggunakan metode rnd.nextInt(limit) dan
menambahkan satu nilai kepada variabel i setiap selesai perulangan.
Program akan mendeklarasikan objek m, variabel mrg, dan memanggil
metode mergeSort dari kelas MergeSort. Dalam kelas ini, program akan
melakukan pengurutan data acak tersebut menggunakan algoritma MergeSort yang
menggunakan prinsip divide and conquer.
Contoh pengurutan data array acak {38, 27, 43, 3, 9, 82, 10} menggunakan
MergeSort adalah sebagai berikut:
Array tersebut dibagi menjadi dua bagian, jika jumlahnya ganjil, maka
bagian pertama memiliki array lebih banyak daripada bagian kedua {38, 27,
43, 3} dan {9, 82, 10}.
Masing-masing bagian tersebut dibagi lagi menjadi dua bagian, jika
jumlahnya ganjil, maka bagian pertama memiliki array lebih banyak
daripada bagian kedua {38, 27}, {43, 3}, {9, 82}, dan {10}.
Masing-masing bagian tersebut yang memiliki lebih dari satu array dibagi
lagi menjadi dua bagian {38}, {27}, {43}, {3}, {9}, {82}, dan {10}.
Setiap dua bagian array tersebut kemudian digabungkan dan diurutkan
sehingga menjadi {27, 38}, {3, 43}, {9, 82}, dan {10}.
Setiap dua bagian array tersebut kemudian digabungkan dan diurutkan lagi
sehingga menjadi {3, 27, 38, 43} dan {9, 10, 82}.
Semua array tersebut kemudian digabungkan dan diurutkan sehingga
menjadi {3, 9, 10, 27, 38, 43, 82}.
Program akan menampilkan hasil pengurutannya menggunakan fungsi
perulangan for. Dengan nilai awal variabel i = 0 dan selama nilainya lebih kecil
daripada mrg.length, maka akan mencetak variabel mrg indeks ke-i dan
menambah satu nilai kepada variabel i. Program juga akan menampilkan waktu
pemrosesannya menggunakan fungsi System.nanoTime().
Program akan mendeklarasikan objek b, variabel p, dan memanggil metode
bubbleSort dari kelas BubbleSort. Dalam kelas ini, program akan melakukan
pengurutan data acak tersebut menggunakan algoritma BubbleSort.
Contoh pengurutan data array acak (5 1 4 2 8) menggunakan BubbleSort
adalah sebagai berikut:
( 5 1 4 2 8 ) menjadi ( 1 5 4 2 8 ), membandingkan dua elemen pertama (5
dan 1) dan menukarnya karena 5 > 1.
( 1 5 4 2 8 ) menjadi ( 1 4 5 2 8 ), membandingkan elemen 5 dan 4 dan
menukarnya karena 5 > 4.
( 1 4 5 2 8 ) menjadi ( 1 4 2 5 8 ), membandingkan elemen ketiga 5 dan 2
dan menukarnya karena 5 > 2.
( 1 4 2 5 8 ) menjadi ( 1 4 2 5 8 ), membandingkan dua elemen terakhir (5
dan 8) dan tidak menukarnya karena telah berurutan (8 > 5).
( 1 4 2 5 8 ) menjadi ( 1 2 4 5 8 ), membandingkan elemen 4 dan 2 dan
menukarnya karena 4 > 2.
Program akan menampilkan hasil pengurutannya menggunakan fungsi
perulangan for. Dengan nilai awal variabel i = 0 dan selama nilainya lebih kecil
daripada p.length, maka akan mencetak variabel p indeks ke-i dan menambah
satu nilai kepada variabel i. Program juga akan menampilkan waktu
pemrosesannya menggunakan fungsi System.nanoTime().
2. Tes2
a. Print Screen
Tes2
QSDC
BSBF
Output
b. Analisis
Program di dalam paket Tes2 yang memiliki beberapa kelas, yaitu Tes2,
QSDC, dan BSBF ini berguna untuk mengurutkan data acak yang awalnya tidak
berurutan dengan algoritma pengurutan MergeSort dan BubbleSort.
Kelas Tes1 yang bersifat publik memiliki satu metode yang merupakan
metode utama. Metode ini menggunakan fungsi Random untuk membuat variabel
data bertipe integer yang memiliki array sebanyak variabel limit. Variabel limit
dideklarasikan bertipe integer dan bernilai 200.
Program akan mencetak 200 variabel data yang tersusun dalam array
menggunakan fungsi perulangan for. Dengan nilai awal variabel i = 0 dan selama
nilainya masih lebih kecil daripada limit (200), program akan mendeklarasikan
variabel data indeks ke-i menggunakan metode rnd.nextInt(limit) dan
menambahkan satu nilai kepada variabel i setiap selesai perulangan.
Program akan mendeklarasikan objek qsdc, variabel q, dan memanggil
metode sort dari kelas QSDC. Dalam kelas ini, program akan melakukan
pengurutan data acak tersebut menggunakan algoritma quicksort yang
menggunakan prinsip divide and conquer.
Contoh pengurutan data array acak (3, 7, 8, 5, 2, 1, 9, 4) menggunakan
algoritma quicksort adalah sebagai berikut:
Mengambil sebuah elemen, yang disebut dengan pivot, misalnya 4.
Mengurutkan list sehingga elemen dengan nilai yang lebih kecil daripada 4
berada sebelum 4, sedangkan seluruh elemen yang memiliki nilai yang
lebih besar daripada 4 berada setelahnya.
Membagi list menjadi dua buah sublist yang lebih kecil: elemen kecil dan
elemen besar.
Setelah pemisahan, 4 berada pada posisi akhirnya. Operasi ini disebut
partisi.
Sublist kemudian disortir secara rekursif dari elemen yang lebih kecil dan
sublist dari elemen yang lebih besar.
Program akan menampilkan hasil pengurutannya menggunakan fungsi
perulangan for. Dengan nilai awal variabel i = 0 dan selama nilainya lebih kecil
daripada q, maka akan mencetak variabel q indeks ke-i dan menambah satu nilai
kepada variabel i. Program juga akan menampilkan waktu eksekusinya
menggunakan fungsi System.nanoTime(). Dalam percobaan kali ini,
didapatkan waktu eksekusi sebesar 254.520 nanosekon.
Program akan mendeklarasikan objek bsbf, variabel p, dan memanggil
metode sort dari kelas BubbleSort. Dalam kelas ini, program akan melakukan
pengurutan data acak tersebut menggunakan algoritma bubble sort yang
menggunakan prinsip brute force.
Program akan menampilkan hasil pengurutannya menggunakan fungsi
perulangan for. Dengan nilai awal variabel i = 0 dan selama nilainya lebih kecil
daripada p.length, maka akan mencetak variabel p indeks ke-i dan menambah satu
nilai kepada variabel i. Program juga akan menampilkan waktu eksekusinya
menggunakan fungsi System.nanoTime(). Dalam percobaan kali ini, didapatkan
waktu eksekusi sebesar 21.201.145 nanosekon.
Dari kedua algoritma di atas, dapat disimpulkan bahwa waktu eksekusi
yang dilakukan oleh algoritma quicksort dengan prinsip divide and conquer
(QSDC) jauh lebih cepat daripada algoritma bubble sort dengan prinsip brute force
(BSBF). Hal ini dikarenakan algoritma QSDC memiliki proses yang lebih simpel
dibandingkan dengan algoritma BSBF.
0 5000000 10000000 15000000 20000000 25000000
Waktu Eksekusi (nanosekon)
Diagram Waktu Eksekusi Program
Quicksort (Divide and Conquer) Bubble Sort (Brute-force)
LAPORAN PRAKTIKUM
STRUKTUR DATA DAN ALGORITMA
PATTERN MATCHING
DISUSUN OLEH:
FEMBI REKRISNA GRANDEA PUTRA
M0513019
ASISTEN DOSEN:
1. DIAN SUPRABA (M0512012)
2. DWI PUTRI PERTIWI (M0512015)
3. RIO PAHLEVY RIDLO YUDHA BHAKTI (M0512048)
4. RIZAL KUSUMAJATI NUGROHO (M0512050)
JURUSAN INFORMATIKA
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SEBELAS MARET
SURAKARTA
KAMIS, 18 DESEMBER 2014
1. Brute
a. Print Screen
Output
b. Analisis
Kelas Brute bersifat publik terletak di dalam paket PatternMatching
berguna untuk mengimplementasikan algoritma Brute-Force di Java. Kelas ini
memiliki metode search1 dan main. Metode search1 memiliki parameter pat dan
txt bertipe string. Metode ini berguna untuk menemukan pattern (pola) yang
diinginkan dari sebuah teks.
Metode ini mendeklarasikan variabel M bertipe integer sebagai panjang
pola dan variabel N bertipe integer sebagai panjang teks. Secara sistematis,
langkah-langkah yang dilakukan algoritma ini dalam metode search1 pada saat
mencocokkan pola adalah:
1. Mulai mencocokkan pola pada awal teks dengan fungsi perulangan for,
mendeklarasikan nilai awal variabel i = 0 bertipe integer, nilai akhir
variabel i ≤ N – M, dan penambahan satu nilai pada variabel i.
2. Mendeklarasikan variabel j bertipe integer, dari kiri ke kanan, algoritma ini
akan mencocokkan karakter perkarakter pola dengan karakter di teks yang
bersesuaian dengan fungsi perulangan for, nilai awal variabel j = 0, nilai
akhir variabel j < M, dan penambahan satu nilai pada variabel j, sampai
salah satu kondisi berikut dipenuhi:
1. Karakter di pola dan di teks yang dibandingkan tidak cocok
(mismatch). Jika (txt.charAt(i + j) ≠ pat.charAt(j)), memanggil
fungsi break.
2. Semua karakter di pola cocok. Kemudian algoritma akan
memberitahukan penemuan di posisi ini. Jika nilai variabel j = M,
mengembalikan nilai ke variabel i sebagai indeks lokasi penemuan
pola pada teks.
3. Algoritma kemudian terus menggeser pola sebesar satu ke kanan, dan
mengulangi langkah ke-2 sampai pola berada di ujung teks.
Berikut adalah Algoritma Brute-Force yang sedang bekerja mencari string:
Usaha Ke-1
Teks a b a c a d a b ...
Pola a b a c a d
0 1 2 3 4 5
Pola ditemukan pada indeks ke-0 teks.
Metode utama bernama main mendeklarasikan isi variabel pat bertipe string
berupa pola “abacad” dan isi variabel txt bertipe string berupa teks
“abacadabrabracabracadabrabrabracad”. Metode ini akan memanggil variabel
offset1a bertipe integer untuk mencari variabel pat pada txt dan mencetak variabel
teks dan pola. Untuk menambahkan spasi, digunakan fungsi perulangan for dengan
mendeklarasikan nilai awal variabel i = 0 bertipe integer, nilai akhir variabel i <
offset1a, dan menambah satu nilai pada variabel i.
Untuk hasil akhirnya, jika nilai variabel offset1a = panjang teks, mencetak
tulisan “Tidak ditemukan”. Jika nilainya tidak sama, mencetak tulisan “Pattern
ditemukan pada index ke” diikuti indeks lokasi penemuan pola dalam teks, yaitu
variabel offset1a.
2. KMP
a. Print Screen
Output
b. Analisis
Kelas KMP dalam paket PatternMatching berguna untuk
mengimplementasikan algoritma Knuth-Morris-Pratt dalam Java. Kelas ini
memiliki metode kmpmatch yang memiliki parameter text (teks) dan pattern (pola)
bertipe string.
Secara sistematis, langkah-langkah yang dilakukan dalam metode ini pada
saat mencocokkan pola adalah:
1. Mulai mencocokkan pola pada awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter perkarakter
pola dengan karakter di teks yang bersesuaian, sampai salah satu kondisi
berikut dipenuhi:
1. Karakter di pola dan di teks yang dibandingkan tidak cocok
(mismatch).
2. Semua karakter di pola cocok. Kemudian algoritma akan
memberitahukan penemuan di posisi ini.
3. Algoritma kemudian menggeser pola berdasarkan tabel next, lalu
mengulangi langkah 2 sampai pattern berada di ujung teks.
Metode utama main berfungsi untuk menampilkan output. Metode ini
mendeklarasikan variabel text bertipe string berupa teks “abracadabra” dan
variabel pat bertipe string berupa teks “raca”, menampilkan output berupa teks dan
pattern dengan mendeklarasikan variabel integer posn dan memanggil metode
kmpmatch berparameter text dan pat, dan mencetak karakter kosong dengan fungsi
perulangan for. Metode ini akan mencetak tulisan “Tidak ditemukan” jika nilai
variabel posn = -1 dan tulisan “Pattern ditemukan pada index ke” diikuti dengan
indeks lokasi penemuan pola pada teks jika nilai variabel posn ≠ -1.
Jika kita melihat algoritma Brute-Force lebih mendalam, kita mengetahui
bahwa dengan mengingat beberapa perbandingan yang dilakukan sebelumnya kita
dapat meningkatkan besar pergeseran yang dilakukan. Hal ini akan menghemat
perbandingan, yang selanjutnya akan meningkatkan kecepatan pencarian.
Perhitungan penggeseran pada algoritma KMP adalah sebagai berikut, bila
terjadi ketidakcocokkan pada saat pattern sejajar dengan teks[i..i+n-1], kita bisa
menganggap ketidakcocokan pertama terjadi di antara teks[i+j] dan pattern[j],
dengan 0 < j < n. Berarti, teks[i..i+j-1] = pattern[0..j-1] dan a=teks[i+j] tidak sama
dengan b=pattern[j]. Ketika kita menggeser, sangat beralasan bila ada sebuah
awalan v dari pattern akan sama dengan sebagian akhiran u dari sebagian teks.
Sehingga kita bisa menggeser pattern agar awalan v tersebut sejajar dengan akhiran
dari u.
Dengan kata lain, pencocokkan string akan berjalan secara efisien bila kita
mempunyai tabel yang menentukan berapa panjang kita seharusnya menggeser
seandainya terdeteksi ketidakcocokkan di karakter ke-j dari pattern. Tabel itu harus
memuat next[j] yang merupakan posisi karakter pattern[j] setelah digeser, sehingga
kita bisa menggeser pattern sebesar j-next[j] relatif terhadap teks.
Jadi, dapat disimpulkan bahwa algoritma Knuth-Morris-Pratt relatif lebih
baik daripada algoritma Brute-Force.