Nugrohadi, Prasetyo (2018) Penerapan Teknik Heavy-Light Decomposition dan Struktur Data Fenwick Tree pada Rancangan Algoritma: Studi Kasus SPOJ Klasik 28079 Maximum Child Sum. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5114100070-Undergraduate_Thesis.pdf - Accepted Version Download (2MB) | Preview |
Abstract
Permasalahan SPOJ Klasik 28079 berjudul “Maximum Child Sum” mengangkat pencarian penyelesaian cara mencari child dari suatu node yang memiliki struktur tree dengan jumlah maksimal di antara child lainnya.
Dengan struktur tree yang dinamis dan query yang dilakukan harus diselesaikan dengan batasan waktu yang ditentukan, maka perlu diterapkan teknik khusus dalam perancangan algoritma penyelesaian permasalahan tersebut. Beberapa hal yang harus diperhatikan adalah mengenai cara mengatasi operasi yang dilakukan pada dua perintah yang berbeda, yaitu query dan insert. Operasi query akan mengeluarkan index node yang merupakan child dengan jumlah subtree maksimal dari suatu node, sedangkan operasi insert akan menambahkan node baru dengan nilai dan parent tertentu.
Tugas akhir ini telah berhasil menerapkan struktur data Fenwick Tree dan teknik Heavy-Light Decomposition untuk menyelesaikan permasalahan tersebut dengan kompleksitas O(Q*sqrt(N)*log(N)), dimana Q adalah banyaknya operasi dan N adalah banyaknya vertex.
===================================================================================================================
Classical SPOJ problems 28079 entitled "Maximum Child Sum" raised the issue of settlement by finding child of a node that has a tree structure with the maximum number among the other child.
With a dynamic tree structure and queries that must be done with the specified time limit, it is necessary to apply a special technique in designing the algorithm to solve the problem. Some things to note are on how to solve the operations performed on two different commands, namely query and insert. The query operation will output the index node which is the child with the maximum number of subtrees of a node, while the insert operation will add a new node with certain values and parent.
This final project has successfully applied Fenwick Tree Data Structure and Heavy-Light Decomposition technique to solve the problem with the complexity of O (Q * sqrt (N) * log (N)), where Q is the number of operation(s) and N is the number of vertice(s).
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.73 Nug p-1 3100018074607 |
| Uncontrolled Keywords: | Acyclic Graph; Fenwick Tree; Heavy-Light Decomposition; Tree |
| Subjects: | Q Science > QA Mathematics > QA76.9 Computer algorithms. Virtual Reality. Computer simulation. |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Prasetyo Nugrohadi |
| Date Deposited: | 23 Mar 2018 07:43 |
| Last Modified: | 07 Sep 2020 03:30 |
| URI: | http://repository.its.ac.id/id/eprint/50452 |
Actions (login required)
 |
View Item |