Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Apa yang dimaksud dengan algoritma brute force?

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

Apa syarat binary search terhadap inputnya?

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

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

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

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

1. AUrutan topologis pada semua graf
2. BLintasan terpendek pada graf yang memiliki bobot sisi negatif
3. CPohon rentang minimum
4. DLintasan terpendek berdasarkan jumlah sisi dari simpul awal

Apa artinya suatu masalah memiliki optimal substructure?

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

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

1. ASelalu memilih elemen pertama
2. BMemilih pivot secara acak seragam
3. CMengurutkan input sebelum menjalankan quicksort
4. DMenggunakan rekursi hanya pada sisi kiri

Pengurutan topologis hanya mungkin dilakukan untuk:

1. AGraf berarah asiklik (DAG)
2. BGraf tak berarah
3. CGraf dengan bobot negatif
4. DGraf lengkap