Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan memoisasi?

1. AMembebaskan memori setelah fungsi selesai
2. BMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
3. CMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
4. DMenulis komentar di samping setiap baris kode

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

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

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

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

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 memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
4. DMasalah itu dapat diselesaikan dalam waktu konstan

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

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

Berapa kompleksitas waktu dari: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. AMasalah itu undecidable
2. BDapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan
3. CSelalu dapat diselesaikan dalam O(V + E)
4. DMasalah itu NP-hard

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, sehingga batas bawah itu salah
3. CTidak, karena insertion sort bukan pengurutan berbasis perbandingan
4. DYa, tetapi hanya untuk array yang lebih pendek dari 100