Eksperimen Divide & Conquer.docx

DIVIDE AND CONQUER Design & Analysis of Algorithms – B

Anggota Kelompok:

1. 2. 3. 4.

Xxx Yyy Zzz Www

(NIM) (NIM) (NIM) (NIM)

1. Buatlah sebuah method yang mengimplementasikan Bubble Sort untuk mengurutkan elemen-elemen dari sebuah array. Gunakan method tersebut untuk mengurutkan array-array dengan ukuran 𝑛 dan 3 jenis berbeda: elemen array sudah urut (sorted array), elemen array terbalik (reversed array), elemen array acak (random array). Ukur waktu yang dibutuhkan untuk mengurutkan, kemudian ulangi untuk 𝑛 yang berbeda. Lengkapi tabel berikut kemudian plot hasilnya dalam sebuah grafik.

𝒏

Durasi (ns) Sorted Array

Reversed Array

1 2 5 10 20 50 100 1000 10000

Pseudocode Bubble Sort: procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i] > A[i+1] then swap(A[i], A[i+1]) swapped = true end if end for n = n - 1 until not swapped end procedure

Random Array

Berikut kerangka awal dari program yang harus kalian modifikasi dan jalankan. import java.util.Random; public class BubbleSort { public static int[] bubbleSort(int[] arr) { return arr; // TODO implement this method } public static int[] generateSortedArray(int n) { int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = i; } return arr; } public static int[] generateReversedArray(int n) { int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = n - i; } return arr; } public static int[] generateRandomArray(int n) { Random rand = new Random(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = rand.nextInt(n); } return arr; } public static void main(String[] args) { int n = 5; // size of array, replace as needed int[] arr = generateRandomArray(n); // TODO replace as needed System.out.println("Size of array: " + n); System.out.println("Original array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); long startTime = System.nanoTime(); int[] sorted = bubbleSort(arr); long duration = System.nanoTime() - startTime; System.out.println("Sorted array: "); for (int i = 0; i < sorted.length; i++) { System.out.print(sorted[i] + " "); } System.out.println(); System.out.println("Time taken: " + duration + " ns"); } }

2. Buatlah sebuah method yang mengimplementasikan Merge Sort untuk mengurutkan elemen-elemen dari sebuah array. Gunakan method tersebut untuk mengurutkan array-array dengan ukuran 𝑛 dan 3 jenis berbeda: elemen array sudah urut (sorted array), elemen array terbalik (reversed array), elemen array acak (random array). Ukur waktu yang dibutuhkan untuk mengurutkan, kemudian ulangi untuk 𝑛 yang berbeda. Lengkapi tabel berikut kemudian plot hasilnya dalam sebuah grafik. Bandingkan hasilnya dengan Bubble Sort.

𝒏

Durasi (ns) Sorted Array

Reversed Array

1 2 5 10 20 50 100 1000 10000

Pseudocode Merge Sort: MergeSort(a[]) 1. IF Length(a[]) < 2 THEN RETURN a[]. 2. Partition a[] evenly into two arrays b[], c[]. 3. b[] = MergeSort(b[]) 4. c[] = MergeSort(c[]) 5. RETURN Merge(b[], c[]). Merge(b[], c[]) 1. a[] = empty 2. i = 1, j = 1 3. WHILE i <= Length(b[]) OR j <= Length(c[]) 4. IF b[i] < c[j] THEN 5. a.append(b[i]); i = i+1 6. ELSE 7. a.append(c[j]); j = j+1 8. RETURN a[]

(Base Case) (Divide) (Conquer) (Merge)

Random Array

Berikut kerangka awal dari program yang harus kalian modifikasi dan jalankan. import java.util.Random; public class MergeSort { public static int[] mergeSort(int[] arr) { return arr; // TODO implement this method } public static int[] generateSortedArray(int n) { int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = i; } return arr; } public static int[] generateReversedArray(int n) { int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = n - i; } return arr; } public static int[] generateRandomArray(int n) { Random rand = new Random(); int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = rand.nextInt(n); } return arr; } public static void main(String[] args) { int n = 5; // size of array, replace as needed int[] arr = generateRandomArray(n); // TODO replace as needed System.out.println("Size of array: " + n); System.out.println("Origginal array: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); long startTime = System.nanoTime(); int[] sorted = mergeSort(arr); long duration = System.nanoTime() - startTime; System.out.println("Sorted array: "); for (int i = 0; i < sorted.length; i++) { System.out.print(sorted[i] + " "); } System.out.println(); System.out.println("Time taken: " + duration + " ns"); } }

3. Buatlah sebuah method yang mengimplementasikan Binary Search untuk mencari posisi sebuah nilai dalam sebuah array. Gunakan method tersebut untuk mencari sebuah nilai acak dalam array dengan ukuran 𝑛. Nilai yang dicari bisa ada dalam array maupun tidak. Jika tidak ada dalam array, maka method seharusnya mengembalikan nilai -1. Ukur waktu yang dibutuhkan untuk mencari nilai tersebut, kemudian ulangi untuk 𝑛 yang berbeda. Lengkapi tabel berikut kemudian plot hasilnya dalam sebuah grafik.

𝒏

Durasi (ns) Nilai Yang Dicari Ada

Nilai Yang Dicari Tidak Ada

1 2 5 10 20 50 100 1000 10000

Pseudocode Binary Search: /* Searches value 'x' in sorted array a[left], a[left+1], ..., a[right]. Returns the index of 'x' in array, or -1 if it cannot be found. */ search(a, left, right, x) if left > right then return -1 mid := left+floor((right-left) / 2) if a[mid] = x then return mid else if a[mid] > x then return search(a, left, mid-1, x) else return search(a, mid+1, right, x)

Berikut kerangka awal dari program yang harus kalian modifikasi dan jalankan. import java.util.Random; public class BinarySearch { public static int binarySearch(int val, int[] arr) { return -1; // TODO implement this method } public static int[] generateSortedArray(int n) { int[] arr = new int[n]; for (int i = 0; i < arr.length; i++) { arr[i] = i; } return arr; } public static void main(String[] args) { int n = 5; // size of array, replace as needed int[] arr = generateSortedArray(n); System.out.println("Size of array: " + n); // cold startup, to be fair binarySearch(1, new int[] {1}); Random rand = new Random(); int inArray = rand.nextInt(n); int notInArray = rand.nextBoolean() ? -1 : n; long startTime = System.nanoTime(); int pos = binarySearch(inArray, arr); long duration = System.nanoTime() - startTime; System.out.println("Time for finding value in array: " + duration + " ns"); startTime = System.nanoTime(); pos = binarySearch(notInArray, arr); duration = System.nanoTime() - startTime; System.out.println("Time for finding value not in array: " + duration + " ns"); } }

4. Buatlah sebuah method yang mengimplementasikan Exponentiation by Squaring untuk menghitung 𝑥 𝑛 . Gunakan method tersebut untuk menghitung 3𝑛 dengan nilai 𝑛 yang berbeda-beda. Ukur waktu yang dibutuhkan, kemudian ulangi untuk 𝑛 yang berbeda. Lengkapi tabel berikut kemudian plot hasilnya dalam sebuah grafik. Bandingkan hasilnya dengan metode exponentiation biasa (iterative).

𝒏

Exponentiation Method Iterative

Squaring

1 2 5 10 50 100 1000 10000 100000

Pseudocode Exponentiation by Squaring: Function exp_by_squaring(x, n) if n = 0 then return 1; else if n = 1 then return x ; else if n is even then return exp_by_squaring(x * x, n / 2); else if n is odd then return x * exp_by_squaring(x * x, (n - 1) / 2);

Berikut kerangka awal dari program yang harus kalian modifikasi dan jalankan. import java.math.BigInteger; public class Exponentiation { public static BigInteger expBySquaring(BigInteger x, int n) { return BigInteger.ONE; // TODO implement this method } public static BigInteger iterativeExp(BigInteger x, int n) { BigInteger res = BigInteger.ONE; for (int i = 0; i < n; i++) { res = res.multiply(x); } return res; } public static void main(String[] args) { BigInteger x = BigInteger.valueOf(3); // base int n = 5; // power, replace as needed long startTime = System.nanoTime(); BigInteger res = iterativeExp(x, n); long duration = System.nanoTime() - startTime; System.out.println("Time taken by iterative exp: " + duration + " ns"); startTime = System.nanoTime(); res = expBySquaring(x, n); duration = System.nanoTime() - startTime; System.out.println("Time taken by exp by squaring: " + duration + " ns"); } }