Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma?

1. AUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah
2. BSetiap program komputer yang memiliki antarmuka grafis
3. CStruktur data yang menyimpan bilangan
4. DBahasa pemrograman yang dirancang untuk menulis rumus matematika

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

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

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

1. AO(V × E)
2. BO(V²)
3. CO(V + E)
4. DO(E log V)

Apa artinya suatu masalah memiliki optimal substructure?

1. ASetiap submasalah memiliki ukuran yang sama
2. BSolusi optimal dapat dibangun dari solusi optimal submasalahnya
3. CMasalah itu dapat diselesaikan dalam waktu konstan
4. DMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah

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

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas terpendek terlebih dahulu
2. BPilih aktivitas yang dimulai paling awal
3. CPilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Perkalian Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apa hasilnya?

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n^{log₂ 3}), sekitar n^1,585
4. DΘ(n³)

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. ADapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan
2. BSelalu dapat diselesaikan dalam O(V + E)
3. CMasalah itu NP-hard
4. DMasalah itu undecidable