Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma brute force?

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

Bagaimana cara kerja selection sort?

1. AMembagi array menjadi dua bagian lalu menggabungkannya
2. BBerulang kali menukar elemen bersebelahan yang urutannya salah
3. CMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
4. DBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(mn)
4. DO(m + n)

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 100
2. BSekitar 20
3. CSekitar 1,000
4. DSekitar 500,000

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

1. AHalting problem menjadi decidable
2. BHanya masalah itu yang pindah ke P
3. CSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
4. DSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. ABilangan negatif tidak dapat disimpan dalam priority queue
2. BSimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek
3. CAlgoritma itu hanya bekerja pada graf tak berarah
4. DAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif