Penerapan Teknik Dekomposisi Square Root dan Algoritma Mo's pada Rancangan Algoritma Studi Kasus: SPOJ Klasik Counting Diff-Pairs

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.

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

Download (10MB) | Request a copy

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)
Uncontrolled Keywords: fenwick tree, mo's algorithm, offline query, square root decomposition
Subjects: T Technology > T Technology (General)
T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK5105.546 Computer algorithms
Divisions: Faculty of Information Technology > Informatics Engineering > (S1) Undergraduate Theses
Depositing User: Abdul Majid Hasani
Date Deposited: 21 Feb 2018 07:39
Last Modified: 21 Feb 2018 07:39
URI: http://repository.its.ac.id/id/eprint/50820

Actions (login required)

View Item View Item