Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa arti f(n) = Θ(g(n))?

1. Af tumbuh benar-benar lebih lambat daripada g
2. Bf tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g
3. Cf tumbuh benar-benar lebih cepat daripada g
4. Df selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar log₂ n
2. BSekitar n
3. CSekitar n / 2
4. DSekitar n²

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 3 koin; optimalnya 2
2. BGreedy memakai 2 koin; optimalnya 2
3. CGreedy memakai 3 koin; optimalnya 3
4. DGreedy memakai 4 koin; optimalnya 3

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. ALinear
2. BKonstan
3. CLogaritmik
4. DEksponensial

Algoritma greedy:

1. AMencoba setiap solusi yang mungkin
2. BMengambil pilihan terbaik secara lokal pada setiap langkah
3. CSelalu memberikan solusi optimal
4. DHanya menggunakan rekursi

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, karena insertion sort bukan pengurutan berbasis perbandingan
2. BTidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
3. CYa, tetapi hanya untuk array yang lebih pendek dari 100
4. DYa, sehingga batas bawah itu salah

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

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