Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

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

Apa yang dimaksud dengan algoritma?

1. AUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah
2. BStruktur data yang menyimpan bilangan
3. CBahasa pemrograman yang dirancang untuk menulis rumus matematika
4. DSetiap program komputer yang memiliki antarmuka grafis

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar n / 2
2. BSekitar √n
3. CSekitar n
4. DSekitar log₂ n

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

1. ASubmasalah yang tumpang tindih dan substruktur optimal
2. BTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
3. CSatu loop saja
4. DHanya input acak

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

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

Definisi kelas NP manakah yang benar?

1. AMasalah yang tidak dapat diselesaikan dalam waktu polinomial
2. BMasalah keputusan yang jawaban "ya"-nya dapat diverifikasi dalam waktu polinomial jika diberi sertifikat
3. CMasalah yang tidak dapat diselesaikan algoritma apa pun
4. DMasalah yang tidak polinomial

Algoritma Strassen mengalikan matriks memakai 7, bukan 8, perkalian rekursif blok berukuran setengah. Berapa waktu eksekusinya?

1. AΘ(n^{log₂ 7}), sekitar n^2,81
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n³)