Rahmi, Desy Nurbaiti (2018) Implementasi Struktur Data Rope pada Studi Kasus Permasalahan SPOJ Alphabetic Rope. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5114100030-Undergraduate_Theses.pdf - Accepted Version Download (4MB) | Preview |
Abstract
Permasalahan alphabetic rope merupakan sebuah permasalahan yang melibatkan sebuah rentang pencarian. Tipe query secara umum dibagi menjadi dua yaitu, operasi pencarian dan perubahan. Operasi perubahan pada suatu rentang akan menyebabkan perubahan hasil pencarian selanjutnya. Untuk menangani berbagai permasalahan pada operasi alphabetic rope yang harus dilakukan sehingga dibutuhkan struktur data yang mampu mendukung operasi-operasi tersebut dengan efisien.
Pada Tugas Akhir ini akan dirancang penyelesaian permasalahan alphabetic rope antara lain operasi pencarian karakter pada indeks ke-y pada konfigurasi rope saat ini, operasi memotong segmen rope pada indeks ke-x sampai y dan menggabungkan pada bagian depan rope, dan operasi memotong segmen rope
pada indeks ke-x sampai y dan menggabungkan pada bagian belakang rope. Struktur data klasik yang biasa digunakan dalam penyelesaian permasalahan ini adalah stuktur data String. Namun penggunaan algoritma String masih kurang efisien dalam hal kecepatan dan kebutuhan memori.
Pada Tugas Akhir ini digunakan struktur data Rope untuk menyelesaikan operasi-operasi tersebut. Hasil uji coba menunjukkan program menghasilkan jalur yang benar dan memiliki pertumbuhan waktu secara logaritmik dengan kompeksitas waktu sebesar O(log N) per query.
==========================================================================================================
Alphabetic rope computation is a problem which involves a specific
range of data. Generally it divide by two type of query, range
search and update. An update operation would have an impact for
the following range search query. To handle various problem in
alphabetic rope, an efficient data structure is needed to support the
operations.
This undergraduate thesis will be designed problem solving for
alphabetic rope query variation such as find the y-th position on
current rope, cut the rope segment from x-th to y-th to join at the
front of rope and cut the rope segment from x-th to y-th and join
at the back of rope. Well known data structures, e.g string are
commonly used for solving the this problem. But those algorithm
were not efficient enough in the term of running time and memory
usage.
In this undergraduate thesis Rope data structure will be used
instead for solving those alphabetic rope variations. The program
had been tested and proved that it produces correct result and
running in
O
(
log
N
)
per query.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 005.73 Rah i |
| Uncontrolled Keywords: | concatenation, rope, split, string |
| Subjects: | T Technology > T Technology (General) |
| Divisions: | Faculty of Information and Communication Technology > Informatics > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Desy Nurbaiti Rahmi |
| Date Deposited: | 12 Apr 2018 04:45 |
| Last Modified: | 23 Sep 2020 01:59 |
| URI: | http://repository.its.ac.id/id/eprint/50680 |
Actions (login required)
 |
View Item |