Ujian Akhir Semester Ganjil 2013/2014 Kode/nama mata kuliah : Dosen koordinator : Waktu pengerjaan : Sifat ujian :
AIF204 – Desain & Analisis Algoritma Joanna Helga, M.Sc. 120 menit Open 4 halaman A4 (dikumpulkan saat ujian selesai)
1. [20] Priority Queue ADT Priority Queue dapat diimplementasikan menggunakan berbagai cara. Beberapa diantaranya yang telah kita pelajari adalah menggunakan array, linked-list, dan heap. Sebuah alternatif lainnya adalah dengan menggunakan struktur data Binary Search Tree, yaitu tree yang setiap node-nya memiliki maksimal 2 anak, dan memenuhi syarat: untuk setiap node x, keturunan pada sub-pohon kiri x memiliki key yang lebih kecil dari x, dan keturunan pada sub-pohon kanan memiliki key yang lebih besar atau sama dengan x. Jawablah pertanyaan-pertanyaan berikut secara singkat ! a. [5] Dimanakah letak element dengan key paling besar pada BST ? Leaf paling kanan b. [15] Bagaimanakah cara mengimplementasikan method-method max-priority queue (MAXIMUM, EXTRACT-MAX, INSERT,INCREASE-KEY), dan berapakah kompleksitasnya masing-masing ? MAXIMUM : dengan menelusuri tree terus ke kanan sampai ujung, kemudian mengembalikan nilainya O(h), dimana h adalah tinggi tree (expected O(lg n)) EXTRACT-MAX : dengan menghapus anak paling kanan dan mengembalikan nilainya O(h) INSERT : sama dengan insert pada BST O(h) INCREASE-KEY : delete dulu node-nya, ganti key-nya, kemudian insert lagi O(h) 2. [15] Huffman Encoding Kompresilah teks berikut ini dengan menggunakan algoritma Huffman:
ULARMELINGKARLINGKARDIPAGAR a. [5] Gambarkan pohon Huffman-nya ! Frekuensi huruf: U L A R M 1 3 5 4 1
E 1
I 3
N 2
G 3
K 2
D 1
P 1
Salah satu alternatif pohon huffman:
b. [5] Tuliskan representasi biner pohon Huffman pada soal (a). 00001K01U1M1G01R001E1D01P1N01A01L1I c. [5] Tuliskan hasil kompresi teks “ULARMELINGKAR” dalam bentuk biner! 00010 110 10 010 00011 01100 110 111 01111 001 0000 10 010 U L A R M E L I N G K A R 3. [15] Dynamic Programming Spongebob kembali mengikuti permainan maze piramida. Kali ini ruangan-ruangan maze berbentuk segitiga. Ruangan yang berwarna putih memiliki sebuah pintu satu arah ke lantai bawahnya. Ruangan yang berwarna abu-abu memiliki 2 buah pintu satu arah, yaitu menuju ruang kanan dan ruang kirinya. Pintu-pintu tersebut satu arah, yang artinya jika Spongebob sudah melewati pintu tersebut, ia tidak dapat kembali lagi. Tujuan permainan ini adalah mendapat point sebanyak-banyaknya. Spongebob mulai dari ruangan di lantai paling atas, dan dia dapat keluar di ruangan manapun di paling bawah.
a. [10] Bagaimana menyelesaikan masalah ini dengan cara dynamic programming? Nilai apa saja yang perlu disimpan, dan bagaimana menghitungnya? Ruangan putih hanya memiliki satu pintu, karena itu nilai ruangan putih pasti diambil dari ruangan di bawahnya ditambah nilai dia sendiri. Ruangan abu-abu memiliki dua alternatif, karena itu nilainya diambil dari nilai dia sendiri ditambah maksimum nilai ruang kiri atau kanannya. Solusi greedy dapat terjebak pada local maximum, karena itu kita menggunakan bottom-up DP. Nilai setiap ruangan dihitung dari bawah ke atas. b. [5] Berapa nilai maksimal yang dapat diraih Spongebob pada piramida di atas ? 45 4. [10] Dijkstra’s SSSP Algorithm Simulasikan algoritma SSSP Dijkstra pada graph berikut ini (mulai dari node G) ! Lengkapilah tabel perubahan key yang telah disediakan!
G
Node A
∞ 4
Perubahan key
Shortest path dari G 4
B
∞ 10
10
C
∞ 10
10
D
∞ 5
5
E
∞ 9
9
F
∞ 12 8
8
G
0
0
H
∞ 3
3
[20] Greedy-Coins Collector(UAS1xxyyy.jar) Patrick sedang berkunjung ke Texas, kampung halaman sahabatnya, Shandy. Mata uang Texas memiliki 4 jenis koin, yaitu 1ȼ, 5 ȼ, 10 ȼ, dan 25 ȼ. Patrick ingin menukarkan uang kertas sebesar N ȼ yang ia miliki dengan koin-koin tersebut. Karena muatan kantongnya terbatas, ia ingin agar jumlah koin yang ia kantongi sesedikit mungkin. Bantulah Patrick agar ia mendapatkan sesedikit mungkin koin ketika ia menukarkan uang sejumlah N ȼ tersebut! Input: Baris pertama dari input adalah T (1≤T≤1,000), jumlah kasus yang akan diperiksa. T baris berikutnya masingmasing terdiri dari sebuah bilangan bulat N (1≤N≤1,000,000) yaitu nilai uang yang akan ditukarkan oleh Patrick. (Untuk semua kasus, hanya terdapat 4 jenis koin, masing-masing dengan nominal 1 ȼ, 5 ȼ, 10 ȼ, dan 25 ȼ). Output: Untuk setiap kasus, keluarkan satu baris yang merupakan jumlah koin minimum yang diterima Patrick ketika menukarkan uang sejumlah N ȼ ! Sample Input
Sample Output
2 6 30
2 2
Keterangan output : Uang 6 ȼ dapat ditukar dengan 1 ȼ + 5 ȼ. Uang 30 ȼ dapat ditukar dengan 25 ȼ dan 5 ȼ. Pseudocode: COIN(n) ctr = 0 ctr = ctr + n = n%25 ctr = ctr + n = n%10 ctr = ctr + n = n%5 ctr = ctr + return ctr
n/25 n/10 n/5 n
[20] Dynamic Programming-History Grading(UAS2xxyyy.jar) Dalam sebuah kuis mata pelajaran sejarah, para siswa diminta untuk menentukan urutan dari n buah peristiwa bersejarah sesuai urutan waktunya. Siswa yang mengurutkan n peristiwa tersebut dengan tepat pasti mendapatkan nilai sempurna. Guru sejarah yang baik hati, tidak ingin memberi nilai 0 untuk siswasiswa yang mengurutkan peristiwa-peristiwa itu secara tidak tepat. Karena itu, ia memberi penilaian sebagai berikut: 1 poin untuk tiap peristiwa-peristiwa yang berada pada urutan yang benar relatif terhadap peristiwa lainnya. Sebagai contoh, diberikan 4 peristiwa yang terjadi pada tahun 1945, 1945, 1985, dan 1988. Peristiwaperistiwa ini dinomori dari 1 hingga 4 secara berurutan, maka: Peristiwa #1 1945 Peristiwa #2 1945 Peristiwa #3 1985 Peristiwa #4 1988 Urutan peristiwa yang benar adalah 1, 2, 3, 4, atau 2, 1, 3, 4, karena peristiwa #1 dan #2 memiliki tahun yang sama. Jika seorang siswa menjawab 3, 1, 2, 4, maka tahunnya adalah: 1985, 1988, 1945, 1945. Nilai yang diperolehnya adalah 2, yaitu antara 1985 dan 1988 diangap benar, atau 1945 dan 1945 dianggap benar. Hint: gunakan algoritma LIS. Tugas Anda adalah membuat program untuk menghitung nilai siswa berdasarkan jawaban yang dia berikan. Input: Baris pertama dari input adalah bilangan bulat N (1≤N≤500), yang merupakan banyaknya peristiwa yang diujikan. N baris berikutnya adalah bilangan bulat yang merupakan tahun terjadinya peristiwa-peristiwa secara terurut. Baris pertama merupakan tahun dari peristiwa nomor 1, baris kedua merupakan tahun dari peristiwa nomor 2, dan seterusnya hingga peristiwa nomor N. Selanjutnya, input merupakan bilangan bulat T (1≤T≤500), yaitu jumlah siswa yang mengikuti kuis. Sebanyak T baris berikutnya, input berisi N buah nomor peristiwa yang merupakan jawaban siswa yang mengikut kuis. Output: Untuk setiap jawaban siswa, tampilkan nilai yang diperoleh oleh siswa tersebut dalam satu baris. Contoh Input 1: 4 1945 1945 1960 1988 3 1 3 2 4 3 2 1 4 2 1 3 4
Contoh Output 3 3 4
Solusi: Ubah input menjadi tahun, kemudian lakukan algoritma LIS, tapi ganti tanda < menjadi <=
