Penyelesaian Permasalahan: SPOJ 36941 - And Queries Menggunakan Algoritma Pemrograman Dinamis Bitmasks

Samsico, Alexander Weynard (2025) Penyelesaian Permasalahan: SPOJ 36941 - And Queries Menggunakan Algoritma Pemrograman Dinamis Bitmasks. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 5025211014-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 2025. Download (7MB) | Request a copy

Abstract

Studi kasus SPOJ 36941 – AND Queries merupakan salah satu permasalahan yang dirancang untuk menguji kemampuan pemrograman di SPOJ, situs yang berisi berbagai permasalahan pemrograman. Studi kasus ini meminta untuk menyelesaikan kueri yang masing-masing berisi dengan V dan K. Setiap kueri meminta untuk menghitung hasil setiap bilangan dari array A yang di-AND dengan V menghasilkan 1 bit berjumlah K untuk setiap kueri.
Tugas akhir ini mengacu pada penyelesaian kueri dalam studi kasus SPOJ 36941 – AND Queries. Permrogaman Dinamis Sum Over Subsets merupakan cabang dari Pemrograman Dinamis Bitmask yang memanfaatkan suatu subset dari bilangan set sehingga menemukan hasil jumlah subset dari suatu bilangan yang dapat membantu penyelesaian permasalahan studi kasus SPOJ 36941 – AND Queries. Strategi penyelesaian dapat dimulai dari menerima masukan kemudian dilanjutkan dengan pengelompokkan subset, pemodelan pemrograman dinamis, dan dilakukan substitusi melalui Pemrograman Dinamis Sum Over Subsets untuk mendapatkan hasil akhir yang sebenarnya.
Metode pengujian pada tugas akhir ini terdiri dari pengujian kebenaran, yaitu mengirimkan kode sumber program dari implementasi desain algoritma ke situs penilaian daring Sphere Online Judge (SPOJ) dan pengujian kinerja untuk mengukur efektivitas dari algoritma dengan kompleksitas yang diharapkan. Berdasarkan hasil pengujian, perancangan algoritma Pemrograman Dinamis Bitmasks berhasil menyelesaikan permasalahan dengan waktu minimum 1,01 detik dan waktu rata-rata 1,121 detik dengan penggunaan memori yang konstan yaitu 12 MB. Hasil ini menunjukkan bahwa desain algoritma efektif dan efisien dalam menyelesaikan permasalahan studi kasus SPOJ 36941 – AND Queries.
=======================================================================================================================================
The case study SPOJ 36941 – AND Queries is one of the problems designed to test programming skills on SPOJ, a site containing a wide variety of programming challenges. This case study requires solving queries, each consisting of values V and K. Each query asks to count how many numbers in an array A, when bitwise AND-ed with V, result in a value that has exactly K bits set to 1.
This final project refers to solving the queries in the SPOJ 36941 – AND Queries case study. The Sum Over Subsets Dynamic Programming is a branch of Bitmask Dynamic Programming, which utilizes subsets of a number set to find the sum of those subsets. This technique helps solve the problem posed in the SPOJ 36941 – AND Queries case study. The problem-solving strategy begins by receiving input, followed by grouping subsets, modeling dynamic programming, and applying substitution using the Sum Over Subsets Dynamic Programming approach to obtain the final result.
The testing method in this final project consists of correctness testing, which involves submitting the program’s source code from the algorithm design implementation to the online judge site Sphere Online Judge (SPOJ), and performance testing to measure the effectiveness of the algorithm based on the expected complexity. Based on the test results, the Bitmask Dynamic Programming algorithm design successfully solved the problem with a minimum runtime of 1.01 seconds and an average runtime of 1.121 seconds, with constant memory usage of 12 MB. These results indicate that the algorithm design is effective and efficient in solving the SPOJ 36941 – AND Queries case study.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	and, bitmask, bitwise, pemrograman dinamis, pemrograman dinamis sum over subsets, subset, and, bitmask, bitwise, bitmask, dynamic programming, sum over subsets dynamic programming, subset
Subjects:	T Technology > T Technology (General) > T57.83 Dynamic programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	Alexander Weynard Samsico
Date Deposited:	03 Jul 2025 11:21
Last Modified:	03 Jul 2025 11:21
URI:	http://repository.its.ac.id/id/eprint/119334

Actions (login required)

View Item