Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

1. AO(log n)
2. BO(n log n)
3. CO(n)
4. DO(1)

Apa tiga langkah algoritma divide and conquer?

1. AUrutkan, cari, kembalikan
2. BTebak, periksa, ulangi
3. CBaca, hitung, tulis
4. DDivide, conquer, combine (bagi, taklukkan, gabungkan)

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada komputer yang lambat
2. BWaktu yang diharapkan pada input acak berukuran n
3. CWaktu yang diperlukan pada input terkecil
4. DWaktu maksimum yang diperlukan atas semua input berukuran n

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(mn)
2. BO(2^m+n)
3. CO(m + n)
4. DO(mn log n)

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. ADynamic programming hanya bekerja pada masalah graf, bukan pada array
2. BMerge sort tidak memiliki struktur rekursif
3. CMerge sort sudah O(n)
4. DSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

1. AO(n²)
2. BO(1)
3. CO(log n)
4. DO(n)

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

1. AMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
2. BMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
3. CMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
4. DMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

1. AKarena n selalu kecil
2. BW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
3. CKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
4. DKarena algoritma ini hanya berlaku untuk W = 0