1 of 15

Bagian 6: Decrease and Conquer

S1-Informatika UNDIP

2026

2 of 15

Definisi

  • Decrease and conquer: metode desain algoritma dengan mereduksi persoalan menjadi beberapa subpersoalan yang lebih kecil, tetapi selanjutnya hanya memproses satu sub-persoalan saja.

​

  • Berbeda dengan divide and conquer yang memproses semua sub-persoalan dan menggabung semua solusi setiap sub-persoalan.

3 of 15

Decrease and conquer terdiri dari dua tahapan:

  1. Decrease: mereduksi persoalan menjadi beberapa persoalan yang lebih kecil (biasanya dua subpersoalan).
  2. Conquer: memproses satu sub-persoalan secara rekursif.
  3. Tidak ada tahap combine dalam decrease and conquer.

4 of 15

Tiga varian decrease and conquer

  1. Decrease by a constant: ukuran instans persoalan direduksi sebesar konstanta yang sama setiap iterasi algoritma. Biasanya konstanta = 1. 🡪 Exponentiation
  2. Decrease by a constant factor: ukuran instans persoalan direduksi sebesar faktor konstanta yang sama setiap iterasi algoritma. Biasanya faktor konstanta = 2. 🡪 Binary Search
  3. Decrease by a variable size: ukuran instans persoalan direduksi bervariasi pada setiap iterasi algoritma. 🡪 Quick Sort

5 of 15

6 of 15

7 of 15

8 of 15

Bagian 7: Probabilistic Analysis and Randomized Algorithms

S1-Informatika UNDIP

2026

9 of 15

Probabilistic Analysis

Probabilistic Analysis adalah teknik analisis algoritma dengan menggunakan probabilitas pada input.

  • Algoritma tetap deterministik (tidak acak)
  • Tetapi kita mengasumsikan input bersifat acak

​

Tujuannya untuk:

  • Menghitung rata-rata kinerja algoritma
  • Bukan hanya kasus terbaik atau terburuk

10 of 15

Contoh

Hiring Problem

  • Ada n kandidat
  • Kandidat datang dalam urutan acak
  • Kandidat ke-i akan di-hire jika dia lebih baik dari i-1 kandidat sebelumnya

​

P(hire kandidat ke-i) = 1/i

​

11 of 15

Randomized Algorithm

Randomized Algorithm adalah algoritma yang menggunakan random (acak) dalam prosesnya

  • Input tetap
  • Tapi hasil atau waktu bisa berbeda

​

12 of 15

Randomized Effect

  • Dunia nyata jarang worst-case
  • Random membantu menghindari worst-case
  • Probabilitas membantu memahami performa sebenarnya

13 of 15

Contoh 1

  • A = [9, 3, 7, 1, 8, 2, 6, 5]
  • Urutkan array menggunakan Randomized QuickSort.

​

Randomized Algorithm

  • Pivot dipilih acak.
  • Tiap run bisa beda langkah.

​

Probabilistic Analysis

  • Berapa kemungkinan pivot bagus?
  • Pivot dikatakan baik jika membagi array kira-kira seimbang.

​

​

​

14 of 15

Contoh 2

  • Randomized Search

A = [9, 3, 7, 1, 8, 2, 6, 5]

  • cari 8

​

  • Jumlah langkah sangat bervariasi
  • Probabilitas ketemu dalam 1 langkah: P = 1/n

​

15 of 15

TUGAS

  • Setiap kelompok (3–4 mahasiswa).
  • Tentukan 3 persoalan komputasi dan selesaikan pada data minimal 30 baris (n=30) menggunakan algoritma Decrease and Conquer jenis berikut:
  • decrease by a constant,
  • decrease by constant factor,
  • decrease by variable size = gunakan algoritma sejenis Randomized Sort / Search, tambahkan analisis probabilistiknya dan buktikan randomized algoritmanya.
  • Buat laporan dengan menyertakan notasi fungsional algoritma, hitung kompleksitasnya, serta ilustrasikan langkah algoritma, dan eksperimen probabilistik (no.3), lalu upload ke drive masing-masing (pastikan dapat diakses terbuka).
  • Kumpulkan melalui spreadsheet kolektif Kormat (isi: nama kelompok, anggotanya, link laporan) maksimal sebelum jadwal UTS.
  • Dilarang plagiasi.