Soal UAS Matematika Diskrit TA 2007-2008
Ujian Akhir Semester
Semester Genap
Tahun Akademik 2007/2008
Kode Mata Kuliah: MA-203
Nama Mata Kuliah: Matematika Diskrit
Program Studi: Teknik Informatika
Hari/Tanggal Ujian: Selasa / 6 Mei 2008
Dosen: Jasman Pardede, S.Si, M.T
Sifat Ujian: Open Book
1. Diketahui 16 buah koin uang logam. Satu dari enam belas koin itu ternyata palsu. Koin palsu ternyata lebih ringan dari koin yang asli. Misalkan tersedia sebuah timbangan neraca yang sangat teliti. Buatlah pohon keputusan untuk mencari uang palsu dengan cara menimbang paling banyak 4 kali saja.
2. Diberikan kode Huffman sebagai berikut:
j : 0000, a : 101, n : 11, g : 0001, m : 0010, e : 100, c : 0011, t : 0100, o : 0101, k : 011
a. Gambarkan pohon Huffman yang merepresentasikan kode tersebut.
b. Decode rangkaian bit berikut: 00001011100011011100101001100110101110100100011. (Jawabannya harusnya: “jangan mencontek“)
3. Diberikan jaringan komputer seperti pada gambar di bawah ini. Dimana setiap simpul menyatakan komputer dan garis yang menghubungkan antar komputer merupakan kabel data. Tentukanlah panjang kabel data minimum yang diperlukan sehingga setiap komputer dapat terhubung dengan komputer yang lain.
Soal No. 3 UAS Matematika Diskrit Tahun Akademik 2007/2008
4. Tuliskan notasi Tetha-Besar untuk setiap fungsi dibawah ini:
a. T(n) = 6n² 3n + n5 5n + 9 log n
b. T(n) = (3 log n) (n-1)! + 4n4 + 9n
5. Diberikan algoritma 1 dan algoritma 2 seperti yang ditunjukkan dibawah ini.
Algoritma 1
public void quick(int bt_bawah, int bt_atas){
int pivot, dummy;
int i, j;
public int[] A;
if(bt_bawah<bt_atas){
i = bt_bawah;
j = bt_atas;
pivot = A[j];
do{
while(i<j && A[i]<=pivot)
i++;
while(j>i && A[j]>=pivot)
j- -;
if(i<j){
dummy = A[i];
A[i] = A[j];
A[j] = dummy;
}
}while(i<j);
dummy = A[j];
A[j] = A[bt_atas];
A[bt_atas] = dummy;
if(j-bt_bawah<bt_atas-i){
quick(bt_bawah, j-1);
quick(i+1, bt_atas);
}else{
quick(i+1, bt_atas);
quick(bt_bawah, j-1);
}
}
}
Algoritma 2
public static void bubble(){
public static int[] A = new int[n];
for(int i=1; i<n-1; i++){
for(int j=i; j<n; j++){
if(A[i-1] > A[j]){
int dummy = A[i-1];
A[i-1] = A[j];
A[j] = dummy;
}
}
}
}
a. Nyatakan kompleksitas waktu asimtotik dari kedua algoritma dalam notasi O-Besar, Ω-Besar, dan Θ-Besar.
b. Tentukan algoritma yang paling baik dari kedua algoritma tersebut dan jelaskan alasan Anda.
NB:
- Soal diatas adalah soal UAS Matematika Diskrit tahun akademik 2007-2008 (Angkatan 2006), soal UAS Matematika Diskrit tahun akademik 2008-2009 (Angkatan 2007) tidak ada.
- Antara soal angkatan 2006 dengan 2007 hanya terdapat sekitar 2 soal yang mirip (2 soal tersebut hampir 100% sama).
- Untuk soal nomor 5, soal angkatan 2007 membandingkan algoritma Quick Sort dengan Heap Sort (sedikit berbeda dengan soal angkatan 2006).
- Kalau gak salah soal angkatan 2007 tahun lalu ada tentang membuat pohon biner dari suatu ekspresi aritmatika, jadi coba pelajari.
- Jangan terlalu berharap pada soal ini.
- Selamat ujian! Semoga Anda tidak memperdalam tahun depan, dan kalau pun Anda memperdalam tahun depan percayalah bahwa, “… masa depan sungguh ada, dan harapanmu tidak akan hilang”.
masa soalnya doank
jelek ah….