Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Apa yang dimaksud dengan memoisasi?

1. AMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
2. BMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
3. CMembebaskan memori setelah fungsi selesai
4. DMenulis komentar di samping setiap baris kode

Bagaimana cara kerja selection sort?

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

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. ASubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
2. BMerge sort sudah O(n)
3. CDynamic programming hanya bekerja pada masalah graf, bukan pada array
4. DMerge sort tidak memiliki struktur rekursif

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
2. BInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
3. CInsertion sort adalah O(n log n) pada kasus terburuk
4. DInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

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

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

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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