Implementasi Struktur Data Rope pada Studi Kasus Permasalahan SPOJ Alphabetic Rope

Rahmi, Desy Nurbaiti (2018) Implementasi Struktur Data Rope pada Studi Kasus Permasalahan SPOJ Alphabetic Rope. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.

[img] Text
5114100030-Undergraduate_Theses.pdf
Restricted to Repository staff only

Download (4MB) | Request a copy

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)
Uncontrolled Keywords: concatenation, rope, split, string
Subjects: T Technology > T Technology (General)
Divisions: Faculty of Information Technology > Informatics Engineering > (S1) Undergraduate Theses
Depositing User: Desy Nurbaiti Rahmi
Date Deposited: 12 Apr 2018 04:45
Last Modified: 12 Apr 2018 04:45
URI: http://repository.its.ac.id/id/eprint/50680

Actions (login required)

View Item View Item