Desain Dan Analisis Algoritma Pemrograman Dinamis Model Tree Pada Penyelesaian Permasalahan URI Online Judge 2911 INK COLORS

Permasalahan tugas akhir ini bermula dari adanya permasalahan Ink Colors pada situs URI Online Judge. Permasalahan tersebut menggambarkan sebuah tree yang akan dicari berapa jumlah tree berbentuk Stick Man maksimal yang ada pada tree tersebut. Pemrograman dinamis adalah sebuah paradigma untuk mendapatkan nilai optimal dari beberapa kemungkinan jawaban, dimana permasalahan tersebut memiliki submasalah tumpang tindih dan struktur optimal. Algoritma pemrograman dinamis pada struktur data tree dapat diimplementasikan dengan beberapa cara, salah satunya adalah dengan menggunakan pemrograman dinamis dalam proses penggabungan nilai submasalah pada chidren suatu vertex. Pada tugas akhir ini, permasalahan Ink Colors ini akan didesain dan diimplementasikan dengan pendekatan pemrograman dinamis dalam proses penggabungan submasalah pada children suatu vertex. Solusi yang dikembangkan berjalan dengan kompleksitas waktu O(N) dimana N adalah jumlah vertex pada tree. Solusi yang dibuat cukup efisien dengan rata-rata waktu penyelesaian 0,0624 detik dan 0,0476 detik bila tree direpresentasikan dalam bentuk left child right sibling. ================================================================================================================== This thesis starts with an Ink Colors problems on URI Online Judge. The problem describes a tree that we will try to find a maximum Stick Man shaped tree on that tree. Dynamic programming is a paradigm to gain optimal value from several possible answer, where the problem has overlapping subproblem and optimal structure. Dynamic programming on a tree data structure algorithm can be implemented with several ways, one of them is using dynamic programming in the process of merging subproblems value in children of each vertex. In this thesis, Ink Colors problem will be designed and implemented with a dynamic programming approach in the process of merging subproblems value on each children. The time complexity of the solution is O(N), where N is the number of vertex in the tree. The solution made is quite efficient with an average completion time of 0.0624 seconds and 0.0476 seconds if the tree represented in the form of left child right sibling