Lembar kerja Algoritma & kompleksitas dengan jawaban

Strategi desain apa yang digunakan merge sort?

1. ADivide and conquer (bagi dan taklukkan)
2. BDynamic programming
3. CBrute force
4. DPilihan greedy

Bagaimana cara kerja selection sort?

1. ABerulang kali menukar elemen bersebelahan yang urutannya salah
2. BMembagi array menjadi dua bagian lalu menggabungkannya
3. CBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
4. DMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser

Apa yang dimaksud dengan memoisasi?

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas terpendek terlebih dahulu
2. BPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel
3. CPilih aktivitas yang dimulai paling awal
4. DPilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Apa yang diukur oleh analisis amortisasi?

1. ABiaya algoritma pada input terbaik
2. BBiaya yang diharapkan atas input acak
3. CBiaya rata-rata per operasi atas urutan operasi kasus terburuk
4. DBiaya satu operasi yang paling mahal di mana pun dalam urutan itu

Bagaimana travelling salesman problem diklasifikasikan?

1. AVersi keputusannya di P tetapi versi optimasinya NP-complete
2. BMasalah ini undecidable
3. CVersi keputusannya NP-complete dan versi optimasinya NP-hard
4. DMasalah ini berada di P karena algoritma Dijkstra menyelesaikannya dengan mengunjungi setiap kota satu kali

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. AHanya masalah itu yang pindah ke P
2. BSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear
3. CHalting problem menjadi decidable
4. DSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP