Ujian Algoritma dan Pemrograman Dinamis

Wahyu sedang berbelanja di pasar dan ingin mendapatkan keuntungan maksimal dengan memilih buah-buahan terbaik satu per satu. Apa prinsip utama dari strategi yang digunakan Wahyu jika ia selalu memilih buah terbaik yang tersedia pada setiap langkah?

• Memecah masalah menjadi submasalah yang tumpang tindih

• Memilih solusi optimal lokal pada setiap langkah

• Menggunakan tabel untuk menyimpan hasil perhitungan

• Menggunakan rekursi untuk menyelesaikan masalah

Dewi sedang berbelanja di sebuah toko dan hanya memiliki tas dengan kapasitas terbatas. Ia ingin memilih barang-barang yang akan dimasukkan ke dalam tasnya agar mendapatkan nilai total tertinggi tanpa melebihi kapasitas tas. Dalam situasi ini, teknik pemrograman dinamis digunakan untuk:

• Memilih item dengan berat paling ringan

• Menghindari perhitungan ulang submasalah yang sama

• Mengurutkan item berdasarkan nilai

• Menggunakan rekursi tanpa batasan

Rudi memiliki 3 piring yang disusun bertingkat di satu rak dan ingin memindahkannya ke rak lain dengan aturan hanya boleh memindahkan satu piring pada satu waktu dan tidak boleh meletakkan piring yang lebih besar di atas piring yang lebih kecil. Berapa minimum langkah yang diperlukan Rudi untuk memindahkan semua piring tersebut?

• 5

• 6

• 7

• 8

Hadi sedang menghitung jumlah kelinci di peternakannya setiap bulan. Ia tahu bahwa jumlah kelinci pada bulan ke-n adalah jumlah kelinci pada dua bulan sebelumnya. Rumus rekurensi yang digunakan Hadi adalah:

Dian sedang membangun jaringan jalan antar kota dengan menggunakan algoritma Kruskal. Untuk memastikan tidak ada jalan yang membentuk siklus, struktur data apa yang sering digunakan Dian?

• Stack

• Queue

• Union-Find

• Linked List

Siti memiliki sebuah tas dengan kapasitas tertentu dan ingin mengisi tas tersebut dengan barang-barang yang memiliki nilai dan berat berbeda. Siti ingin memaksimalkan nilai barang yang dibawa tanpa melebihi kapasitas tas. Manakah dari berikut ini yang merupakan contoh masalah yang dapat diselesaikan dengan algoritma greedy?

• Knapsack Fractional

• Tower of Hanoi

• Fibonacci

• Merge Sort

• 3

• 5

• 8

• 13

Dedi sedang mencoba menghitung jumlah cara untuk mencapai ujung tangga dengan langkah 1 atau 2 anak tangga setiap kali. Ia menyadari bahwa beberapa cara untuk mencapai anak tangga tertentu melibatkan perhitungan yang sama berulang kali. Dalam konteks ini, istilah "overlapping subproblems" berarti:

• Submasalah tidak pernah berulang

• Submasalah yang sama dihitung berulang kali

• Semua submasalah berbeda

• Tidak ada submasalah

Angga ingin membangun jaringan jalan terpendek yang menghubungkan beberapa desa. Langkah pertama yang harus dilakukan Angga menurut algoritma Kruskal adalah:

• Mengurutkan semua edge berdasarkan bobot

• Memilih node dengan derajat tertinggi

• Membuat pohon spanning acak

• Menghapus edge terberat

Dewi memiliki 4 piring yang disusun bertingkat dari yang terbesar hingga terkecil di satu rak. Berapa banyak langkah minimum yang diperlukan Dewi untuk memindahkan semua piring tersebut ke rak lain dengan aturan hanya satu piring yang boleh dipindahkan dalam satu waktu dan tidak boleh meletakkan piring yang lebih besar di atas piring yang lebih kecil?

• 8

• 12

• 15

• 16