Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

1. AArray hanya boleh berisi bilangan positif
2. BArray tidak boleh berisi lebih dari 1000 elemen
3. CPanjang array harus pangkat dua
4. DArray harus terurut

Apa arti f(n) = Θ(g(n))?

1. Af selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah
2. Bf tumbuh benar-benar lebih cepat daripada g
3. Cf tumbuh benar-benar lebih lambat daripada g
4. Df tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang mencoba semua kandidat solusi yang mungkin
2. BAlgoritma yang selalu memakai rekursi
3. CAlgoritma yang menebak jawaban secara acak
4. DAlgoritma yang berjalan di banyak prosesor

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. ALintasan terpendek berdasarkan jumlah sisi dari simpul awal
2. BUrutan topologis pada semua graf
3. CLintasan terpendek pada graf yang memiliki bobot sisi negatif
4. DPohon rentang minimum

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. AHanya input acak
2. BSatu loop saja
3. CSubmasalah yang tumpang tindih dan substruktur optimal
4. DTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah

Apa artinya suatu masalah memiliki optimal substructure?

1. AMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
2. BSetiap submasalah memiliki ukuran yang sama
3. CMasalah itu dapat diselesaikan dalam waktu konstan
4. DSolusi optimal dapat dibangun dari solusi optimal submasalahnya

Dua hal apa yang harus ditunjukkan untuk membuktikan bahwa masalah keputusan X adalah NP-complete?

1. AX tidak memiliki algoritma polinomial, dan X decidable
2. BX berada di P, dan X dapat direduksi ke SAT
3. CX berada di NP, dan masalah NP-complete yang sudah dikenal dapat direduksi ke X dalam waktu polinomial
4. DX dapat direduksi ke masalah di P, dan X berada di NP

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 intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial
4. DMasalah undecidable berada di NP, sedangkan masalah intractable di P