Profitina

Tulang punggung teori dari seluruh kurikulum: cara memodelkan masalah komputasi secara presisi, merancang algoritma untuknya, membuktikan algoritma itu benar, dan bernalar formal tentang bagaimana waktu jalannya bertumbuh — sebelum satu baris kode produksi pun ditulis.

Ringkasan

Desain dan Analisis Algoritma (DAA) dimulai dari model RAM dan notasi asimtotik (Big-O/Θ/Ω), lalu berkembang ke algoritma-algoritma yang jadi kanon di setiap kurikulum ilmu komputer: insertion sort dan pencarian sebagai studi kasus pertama, merge sort lewat rekurensi dan pola divide-and-conquer, heapsort dan priority queue, quicksort, binary search tree beserta saudaranya yang seimbang, AVL tree, dynamic programming, algoritma greedy, dan satu busur penuh algoritma graf — minimum spanning tree lewat algoritma Kruskal dan Prim, shortest path dari satu sumber lewat algoritma Dijkstra dan Bellman-Ford, analisis amortized, dan shortest path antar semua pasangan simpul. Empat bab Practice Problems ditempatkan di titik-titik jeda alami sepanjang urutan itu, sehingga setiap blok teori langsung diuji dengan kumpulan soal terpandu sebelum kuliah berpindah ke gagasan berikutnya.

Yang Akan Anda Pelajari

• Bernalar formal tentang waktu jalan memakai notasi asimtotik, dan menyelesaikan rekurensi yang menggambarkan algoritma divide-and-conquer.
• Membandingkan algoritma pengurutan — insertion sort, merge sort, heapsort, quicksort — berdasarkan trade-off yang sesungguhnya, bukan hafalan aturan praktis.
• Membangun, mencari, dan menyeimbangkan ulang binary search tree, termasuk rotasi AVL.
• Merancang solusi dynamic programming dan greedy, serta menentukan dengan tepat mana yang sesungguhnya dibutuhkan sebuah soal.
• Menghitung minimum spanning tree dengan algoritma Kruskal dan Prim, serta shortest path dengan algoritma Dijkstra, Bellman-Ford, dan pendekatan all-pairs.
• Menerapkan analisis amortized untuk menilai biaya sesungguhnya dari serangkaian operasi, bukan sekadar kasus terburuk tunggal.

Isi Buku

1. Foundations of Algorithm Design and Analysis — model RAM, arti sesungguhnya dari kebenaran dan efisiensi, dan cara berpikir yang mendasari seluruh bab berikutnya.
2. Analyzing Algorithms: The RAM Model, Insertion Sort, and Searching — algoritma pertama di kuliah ini, dianalisis baris demi baris.
3. Asymptotic Notation, Recurrences, and Merge Sort — Big-O/Θ/Ω diformalkan, dan divide-and-conquer diperkenalkan lewat merge sort.
4. Practice Problems: Foundations Through Merge Sort — kumpulan soal terpandu yang merangkum blok pertama kuliah.
5. Heapsort, Priority Queues, and Quicksort — dua algoritma pengurutan lagi dan struktur data heap di balik priority queue.
6. Binary Search Trees and AVL Trees — pohon pencarian terurut, dan cara rotasi AVL menjaganya tetap seimbang.
7. Dynamic Programming — memecah masalah menjadi subproblem yang tumpang tindih dan menyelesaikan tiap subproblem tepat sekali.
8. Practice Problems: Heapsort Through Dynamic Programming — titik konsolidasi kedua.
9. Greedy Algorithms — kapan pilihan terbaik secara lokal di setiap langkah juga menghasilkan jawaban optimal secara global.
10. Graphs and Minimum Spanning Trees: Kruskal’s Algorithm — representasi graf, dan algoritma MST pertama.
11. Prim’s Algorithm for Minimum Spanning Trees — algoritma MST kedua, dan kapan sebaiknya dipilih dibanding Kruskal.
12. Practice Problems: Greedy Algorithms Through Minimum Spanning Trees — titik konsolidasi ketiga.
13. Single-Source Shortest Paths: Dijkstra’s Algorithm and Bellman-Ford — dua algoritma shortest-path klasik, dan kapan masing-masing dibutuhkan.
14. Amortized Analysis — menghitung biaya serangkaian operasi secara jujur, bukan mengalikan kasus terburuk.
15. All-Pairs Shortest Paths — memperluas penalaran shortest-path dari satu sumber ke setiap pasangan simpul.
16. Practice Problems: Shortest Paths Through All-Pairs Shortest Paths — kumpulan soal penutup, kumulatif untuk seluruh blok algoritma graf.