Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Apa yang dimaksud base case pada fungsi rekursif?

1. AKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
2. BPemanggilan yang memakai memori paling banyak
3. CBaris pertama fungsi
4. DKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A6 detik
2. B9 detik
3. C12 detik
4. D3 detik

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(m + n)
3. CO(mn log n)
4. DO(mn)

Bagaimana algoritma Prim membangun minimum spanning tree?

1. AMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
2. BMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
3. CMenghapus sisi termahal sampai tidak ada siklus tersisa
4. DMenjalankan breadth-first search dan menyimpan pohon BFS

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. AHanya input acak
2. BTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
3. CSubmasalah yang tumpang tindih dan substruktur optimal
4. DSatu loop saja

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

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n log² n)
4. DΘ(n)

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

1. AKarena algoritma ini hanya berlaku untuk W = 0
2. BW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
3. CKarena n selalu kecil
4. DKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input