Hasani, Abdul Majid (2018) Penerapan Teknik Dekomposisi Square Root dan Algoritma Mo's pada Rancangan Algoritma Studi Kasus: SPOJ Klasik Counting Diff-Pairs. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5114100097-Undergraduate_Theses.pdf - Accepted Version Download (10MB) | Preview |
Abstract
Abstrak—Diberikan sebuah sekuen bilangan A dengan jumlah N , M baris kueri, dan selisih mutlak bernilai k. Terdapat operasi kueri untuk mencari jumlah pasangan angka dalam jarak tertentu di sekuen bilangan A yang memiliki selisih mutlak sama dengan atau lebih dari k.
Pada penelitian ini akan dirancang penyelesaian masalah yang disampaikan pada paragraf pertama dengan menggunakan algoritma Square Root Decomposition, Mo’s Algorithm, dan
struktur data Fenwick Tree. √Solusi yang didesain memiliki kompleksitas waktu O((N +M ) N K log mv), dimana N adalah
jumlah elemen pada b√aris sekuen yang diberikan, M adalah
jumlah operasi kueri, N adalah konstanta, K adalah jumlah langkah peyelesaian, dan log mv adalah kompleksitas Fenwick Tree.
Algoritma yang didesain dapat menyelesaikan permasalahan yang diberikan dengan benar. Waktu eksekusi program yang mengimplementasi algoritma yang dirancang tidak melebihi batas waktu eksekusi program yang telah diberikan, yaitu 1.78 detik. Sehingga dapat disimpulkan algoritma yang didesain dapat menyelesaikan permasalahan yang diberikan.
======================================================================================================
Given a sequence of number A with total of N, M sequence of
query, and absolute difference of k. There is operation of query for searching total of pair of number with absolute difference of k or greater than k.
Offline Query is technique for solving given query at the same time. Square Root Decomposition is optimization technique used for dividing a number sequence into certain number of blocks. The number of blocks are obtained from square root of total number in
number sequence. Mo's Algorithm is query optimization technique that develop Square Root Decomposition concept. This algorithm reduce complexity time for solving number of query problem with variative range. Given query will be sorted into certain order so that the answer of previous query will be used for answering the next query because its range is near.
In this final project, the writer will design and analyze an algorithm to solve the problem that stated in the first paragraph using Mo's Algorithm technique and Square Root Decomposition. The solution will run in O ((N+M)pN K log mv) time complexity where N is the total number of given number sequence, M is the total of given queries, pN is constant value, K is total steps, and log mv is Fenwick Tree's Complexity.
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Additional Information: | RSIf 513.23 Has p-1 3100018075065 |
| Uncontrolled Keywords: | fenwick tree, mo's algorithm, offline query, square root decomposition |
| Subjects: | T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms |
| Divisions: | Faculty of Information Technology > Informatics Engineering > 55201-(S1) Undergraduate Thesis |
| Depositing User: | Abdul Majid Hasani |
| Date Deposited: | 21 Feb 2018 07:39 |
| Last Modified: | 10 Apr 2020 22:41 |
| URI: | http://repository.its.ac.id/id/eprint/50820 |
Actions (login required)
 |
View Item |