Lembar kerja Algoritma & kompleksitas dengan jawaban

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

Berapa nilai log₂ 1024?

1. A512
2. B12
3. C32
4. D10

Algoritma pengurutan mana yang memilih pivot dan mempartisi array menjadi elemen yang lebih kecil dan lebih besar?

1. AQuicksort
2. BBubble sort
3. CInsertion sort
4. DMerge sort

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 3 koin; optimalnya 3
2. BGreedy memakai 2 koin; optimalnya 2
3. CGreedy memakai 4 koin; optimalnya 3
4. DGreedy memakai 3 koin; optimalnya 2

Rekurens T(n) = 2T(n − 1) + O(1) menghasilkan apa?

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

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu berjalan dalam waktu O(1)
2. BFungsi itu otomatis mengembalikan 0
3. CFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)
4. DKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman

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

Apa perbedaan antara masalah undecidable dan masalah intractable?

1. AKeduanya berarti masalah itu sama sekali tidak memiliki algoritma
2. BTidak ada algoritma yang menyelesaikan masalah undecidable untuk semua input, sedangkan masalah intractable dapat diselesaikan tetapi terlalu lambat
3. CMasalah undecidable berada di NP, sedangkan masalah intractable di P
4. DMasalah intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial