UTS Analisis dan Strategi Algoritma 2026

Gunakan NIM dan nama sendiri untuk jawaban pribadi. Sebagai ilustrasi, pakai tepat larik yang tercetak pada soal: [4,10,38,4,7,14,8,2,11,2]. Contoh tercetak tidak konsisten dengan aturan F, G, H sebagai tiga digit terakhir NIM yang dicontohkan; hitung ulang ketiga digit dari NIM sendiri bila menerapkan definisinya.

1a. Maksimum

Pisahkan larik menjadi dua hingga tiap bagian bersatu elemen; gabungkan dengan max(kiri, kanan). Bagian kiri [4,10,38,4,7] menghasilkan 38, kanan [14,8,2,11,2] menghasilkan 14, sehingga maksimum 38. Rekurensi $T(n)=2T(n/2)+O(1)=O(n)$ untuk pembagian seimbang; tepat $n-1$ perbandingan.

1b. Merge sort

Pisah menjadi [4,10,38,4,7] dan [14,8,2,11,2], lalu teruskan sampai masing-masing elemen tunggal. Penggabungan terurut menghasilkan kiri [4,4,7,10,38], kanan [2,2,8,11,14], dan hasil akhir [2,2,4,4,7,8,10,11,14,38]. $T(n)=2T(n/2)+O(n)=O(n\log n)$ dan ruang bantu $O(n)$.

1c. Cari G

Pada larik contoh tercetak G = 8. Dengan indeks mulai 1, linear search memeriksa 2, 2, 4, 4, 7, 8 dan berhasil di posisi 6; terburuk $O(n)$, strategi sekuensial. Binary search memeriksa posisi 5 (7), lalu 8 (11), lalu 6 (8): $O(\log n)$, decrease-and-conquer. Random search memilih indeks acak. Jika sampling independen dengan pengembalian, peluang sukses satu percobaan = 1/10 dan setelah k percobaan $1-(9/10)^k$; tidak ada batas waktu terburuk deterministik jika boleh mengulang selamanya. Jika mengacak seluruh indeks tanpa pengembalian, sukses paling lambat 10 pemeriksaan dan peluang setelah k percobaan adalah k/10 untuk $k\le10$. Kompleksitas dan peluang berubah jika target muncul lebih dari sekali.

2. Pemisahan

Tafsirkan “jumlah elemen unik” sebagai banyaknya nilai berbeda, bukan jumlah numerik nilainya. Untuk setiap batas $i=1,\ldots,n-1$, hitung banyak nilai berbeda pada prefiks dan sufiks lalu bandingkan. Strategi exhaustive scan dengan himpunan; prahitung jumlah berbeda prefiks dan sufiks agar total waktu dan ruang $O(n)$ (atau $O(n)$ waktu dan $O(n)$ ruang memakai sifat terurut).

function bisaPisah(L):
  pref[0] ← 0; suf[n+1] ← 0
  for i ← 1 to n: pref[i] ← pref[i-1] + (i=1 or L[i] ≠ L[i-1] ? 1 : 0)
  for i ← n downto 1: suf[i] ← suf[i+1] + (i=n or L[i] ≠ L[i+1] ? 1 : 0)
  for i ← 1 to n-1:
    if pref[i] = suf[i+1]: return i
  return tidak_ada

Untuk larik terurut tadi, pada batas 6 bagian kiri [2,2,4,4,7,8] memiliki empat nilai berbeda dan kanan [10,11,14,38] juga empat. Jadi jawabannya bisa, dengan pemisahan setelah posisi 6. Duplikat yang melintasi batas dihitung sekali di masing-masing sisi.