Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Kompleksitas ruang (space complexity) mengukur:

1. AJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
2. BJumlah baris kode
3. CRuang disk yang dipakai file program setelah dikompilasi
4. DUkuran fisik komputer

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu konstan
2. BTidak memiliki solusi
3. CHanya dapat diselesaikan dengan mencoba setiap kemungkinan
4. DDapat diselesaikan dalam waktu polinomial

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

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

Apa yang diukur oleh analisis amortisasi?

1. ABiaya algoritma pada input terbaik
2. BBiaya yang diharapkan atas input acak
3. CBiaya satu operasi yang paling mahal di mana pun dalam urutan itu
4. DBiaya rata-rata per operasi atas urutan operasi kasus terburuk

Algoritma greedy:

1. ASelalu memberikan solusi optimal
2. BHanya menggunakan rekursi
3. CMengambil pilihan terbaik secara lokal pada setiap langkah
4. DMencoba setiap solusi yang mungkin

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. ABilangan negatif tidak dapat disimpan dalam priority queue
2. BSimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek
3. CAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif
4. DAlgoritma itu hanya bekerja pada graf tak berarah

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

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