Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada input terkecil
2. BWaktu yang diharapkan pada input acak berukuran n
3. CWaktu yang diperlukan pada komputer yang lambat
4. DWaktu maksimum yang diperlukan atas semua input berukuran n

Strategi desain apa yang digunakan merge sort?

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

Pertumbuhan O(2ⁿ) disebut apa?

1. AEksponensial
2. BLinear
3. CPolinomial
4. DLogaritmik

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

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

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

Berapa kompleksitas waktu kasus terburuk quicksort?

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

Bagaimana algoritma Bellman–Ford mendeteksi siklus berbobot negatif yang dapat dicapai dari sumber?

1. AAlgoritma menghitung siklus dengan depth-first search
2. BAlgoritma memeriksa apakah ada sisi berbobot negatif
3. CSetelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
4. DAlgoritma menjalankan Dijkstra dua kali dan membandingkan kedua hasil jaraknya

Bagaimana travelling salesman problem diklasifikasikan?

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