Aturan Pemasukan Jawaban

1. Jawaban boleh dibuat menggunakan word-processor atau ditulis tangan+scan asalkan jelas dan mudah terbaca. Maaf jangan mengirimkan file dalam format .docx atau .doc, Saya tidak menggunakan Microsoft Word.
2. Pastikan nama file dalam lampiran berisi nomor pr, NIM, dan nama. Misalkan pr1-2301189999-Bond.pdf
3. Softcopy jawaban dikirim ke mailbox [email protected] dalam bentuk lampiran.
4. Pastikan jawaban anda sudah terkirim paling lambat pada tanggal 29 September 2018

Soal PR

1. Diberikan input satu kata dengan panjang l karakter dan matrik m × n karakter. Apakah ada rangkaian karakter yang berdampingan dalam matrik tersebut yang membentuk kata tersebut? Didalam matrik. setiap karakter berdampingan dengan 8 karakter lain. Misalnya, diberikan instan input “kucing” dan matrik tts (3×4) sbb:

   k a r d
   u c u g
   m i n l

   Dimulai dari huruf k, turun 1x, ke kanan 1x, turun lagi 1x, ke kanan 1x, dan naik miring ke kanan 1x, diperoleh “kucing”, sehingga untuk instan ini jawaban yang diperoleh adalah “ya ada kata kucing tersebut dalam matrik yang diberikan”

   1. Buat algoritma untuk soal ini
   2. Buktikan bahwa algoritma yang anda buat mampu menemukan kata yang diminta jika kata tersebut ada, dan dapat menjawab “tidak” jika tidak ada kata tersebut dalam matrik.
   3. Hitung kompleksitas algoritma yang anda ajukan, terhadap parameter l, m, dan n.

2. Diketahui ada n data dalam array sudah dalam keadaan terurut. Masih ada lg n data lagi (yang belum tentu terurut) yang perlu digabungkan dengan data awal tersebut, sehingga jumlah data menjadi (n + lg n). Apa cara yang efisien untuk menggabungkan keduanya? Buat algoritmanya berdasarkan ide2 dibawah ini, hitung kompleksitas worst-case jumlah operasi perbandingan  yang dilakukan, dan bandingkan kompleksitas algoritma-algoritma tersebut.

   1. Lakukan proses Insertionsort yang biasa terhadap sisa data lg n tersebut terhadap n data yang sudah terurut.
   2. Ada dua proses dalam satu loop dalam pada proses Insertionsort, yaitu sequential search mencari posisi yang tepat untuk data yang akan disisipkan, dan (sambil) menggeser untuk menyediakan tempat bagi data tersebut. Jika kedua proses ini dipisah, dan searching menggunakan proses binary search! dimana menggeser satu blok data (diasumsikan) dapat dilakukan lebih cepat, akan diperoleh variasi solusi lain untuk menyisipkan lg n data tambahan ini.
   3. Urutkan sisa data lg n tersebut secara terpisah, dan kemudian lanjutkan dengan proses merging untuk menggabungkan keduanya.
   4. Buat solusi berdasarkan ide anda sendiri, dan usahakan untuk mendapatkan kompleksitas jumlah perbandingan yang lebih baik lagi.

3. Implementasi algoritma pada sistem eksekusi yang berbeda akan memberikan kinerja yang berbeda pula. Misalnya, sebuah program dalam bahasa Go akan bekerja beberapa kali lebih cepat dari pada program dalam bahasa Python, walaupun algoritma yang digunakan sama. Begitu juga, program yang sama tetapi dijalankan di mesin yang berbeda akan memberikan kinerja yang berbeda pula, yang disebabkan perbedaan arsitektur komputer, jumlah prosesor, clock CPU, buffer, kecepatan memori, beban sistem saat tersebut, dll.
   Jika n adalah besar masukan, untuk setiap pertanyaan dibawah, jelaskan yang mana dan pada besar masukan berapa pada akhirnya akan mempunyai kinerja yang lebih baik?

   1. Ada dua buah program yang menyelesaikan masalah yang sama; A dalam bahasa Python dengan kompleksitas O(n²+ lg n), dan B dalam bahasa Go dengan kompleksitas O(n²√n). Menggunakan komputer yang sama, dalam suatu eksperimen, waktu eksekusi A adalah 1.5 detik sedangkan B adalah 0.32 detik untuk 1024 data. Jika eksperimen diulang dengan 4096 data, ternyata waktu eksekusi A menjadi 10 detik!
   2. A dan B adalah program dengan algoritma yang berbeda dan dijalankan pada komputer yang berbeda pula. A mempunyai kompleksitas O(√3ⁿ) dan B dengan kompleksitas O(√2ⁿ). Komputer A berkemampuan 30x lebih cepat daripada komputer B. Jika eksperimen dijalankan menggunakan 10 data, program A dapat selesai dalam waktu 1 detik sedangkan B dalam waktu 1 menit.
   3. Lihat soal diatas, bagaimana situasinya apabila program B berhasil di-port (dijalankan) di komputer A?