Contoh Soal Ujian Tengah Semester Strategi Algoritma

Contoh Soal Ujian Tengah Semester Strategi Algoritma - Berikut contoh soal UTS Strategi Algoritma. Berdoalah terlebih dahulu agar Anda sukses dalam ujian ini!

1. (Brute Force + Divide and Conquer) Diberikan sebuah larik (array) integer dengan n elemen. Anda diminta menghitung jumlah (summation) seluruh elemen di dalam larik

1. Jika diselesaikan dengan algoritma Brute-Force, jelaskan algoritmanya seperti apa (tidak perlu pseudo-code) dan berapa kompleksitas waktunya dalam nota Big-Oh?
2. Desain algoritma divide and conquer (tidak harus berupa pseudo-code) untuk menghitung jumlah semua elemen di dalam larik. Beri contoh penjelasan algoritma anda dengan array 8 elemen. Selanjutnya tentukan relasi rekurens kompleksitas waktunya dihitung dari banyaknya operasi penjumlahan, lalu selesaikan relasi rekurens tersebut (boleh pakai Teorema Master). Apakah solusinya lebih baik daripada Algoritma Brute-Force?

2. (Divide and Conquer) Aplikasikan Teorema Master untuk menentukan notasi Big-Oh dari relasi rekurens berikut:

1. T(n) = 10T(n/3) + 17n1.2
2. T(n) = 7T(n/3) + n3
3. T(n) = T(2n/3) + 1
4. T(n) = 9T(n/3) + Ön 

3. (Decrease and Conquer) Temukan tahap-tahap menemukan elemen median dari larik berikut

12, 5, 8, 15, 18, 21, 6, 10, 4

dengan algoritma decrease and conquer yang memanfaatkan proses partisi pada Algoritma Quick Sort.

Sekian Contoh Soal Ujian Tengah Semester Strategi Algoritma.