Mata Kuliah Semester 4: Perancangan dan Analisis Algoritma

gambar: lfgtech-solutions.com

Perancangan dan Analisis Algoritma atau PAA adalah mata kuliah semester 4 yang merupakan lanjutan dari kuliah pemrograman sebelumnya. Kuliah ini memberikan pengetahuan tentang macam-macam algoritma dan efisiensinya.

Jadi, dalam satu permasalahan bisa terdapat lebih dari satu algoritma, dan algoritma-algoritma tersebut memiliki efektivitas yang berbeda-beda.

Mungkin kalau inputannya sedikit, perbedaan efektivitas ini tidak terlalu terlihat. Namun, kalau diimplementasikan untuk tujuan yang lebih besar (dengan inputan lebih besar) perbedaan efektivitas ini bisa sangat berpengaruh.

Contoh ekstremnya adalah algoritma Travelling Salesman Problem yang memiliki efektivitas sangat rendah, sehingga jika inputan kotanya banyak, komputer bisa memerlukan waktu bertahun-tahun untuk menemukan solusinya.

Nah, di kuliah ini kita diajarkan untuk menghitung waktu tersebut dan menentukan efisiensinya.

Di kuliah ini tidak ada praktikum, tapi kita akan mendapat banyak tugas ngoding algoritma-algoritma yang berbeda. Misalnya waktu saya kemarin, tugas ngodingnya ada:

• Bubble sort dan aneka program sorting (kode di sini)
• algoritma Sieve of Eratosthenes
• pencarian FPB dengan algoritma euclid dkk
• pemrograman tree (binary tree(kode), BFS, DFS, dll)
• fibonacci
• tower of hanoi (applet di sini)
• knapsack problem
• travelling salesman problem
• matrix multiplication
• convex hull (applet di sini)
• fake coin (applet di sini) (kode di sini)
• josephus problem
• game of nim (applet di sini)
• permutation dan combination
• dkk

Algoritma-algoritma di atas juga diklasifikasikan menjadi jenis-jenis algoritma berdasarkan desain:

• Brute force
• Greedy method
• Divide and conquer
• Reduction
• Dinamic programming, dll

Bahasa yang dipakai: C, C++, C++/CLI (bagi yang pengen programnya ada gambarnya)
Buku: Design and Analysis of Algorithm by Anany Levitin (reccommended)