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 diperlukan pada komputer yang lambat
3. CWaktu yang diharapkan pada input acak berukuran n
4. DWaktu maksimum yang diperlukan atas semua input berukuran n

Apa tiga langkah algoritma divide and conquer?

1. ABaca, hitung, tulis
2. BDivide, conquer, combine (bagi, taklukkan, gabungkan)
3. CUrutkan, cari, kembalikan
4. DTebak, periksa, ulangi

Bagaimana cara kerja selection sort?

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

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ASemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
2. BLogaritma selalu dibulatkan menjadi bilangan bulat
3. CLogaritma dengan basis berbeda hanya berbeda faktor konstan
4. DBasis hanya berpengaruh untuk n kecil

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

1. APohon rentang minimum
2. BLintasan terpendek berdasarkan jumlah sisi dari simpul awal
3. CLintasan terpendek pada graf yang memiliki bobot sisi negatif
4. DUrutan topologis pada semua graf

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

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

Algoritma dynamic programming Held–Karp menyelesaikan travelling salesman problem secara eksak. Berapa waktu eksekusinya untuk n kota?

1. AO(n³)
2. BO(n!)
3. CO(2^n²)
4. DO(n² 2ⁿ)

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. A3-SAT, dengan setiap klausa berisi tepat tiga literal
2. B2-SAT, dengan setiap klausa berisi paling banyak dua literal
3. CSAT umum pada formula dalam bentuk normal konjungtif
4. DCircuit satisfiability