AKBAR, SHAFRIZAL FADILLAH (2026) IMPLEMENTASI ALGORITMA GREEDY PLACEMENT DENGAN HEURISTIK INTERSEKSI MAKSIMUM PADA GAME CROSSWORD. S1 thesis, Universitas Mercu Buana Jakarta.
|
Text (HAL COVER)
01 COVER.pdf Download (3MB) | Preview |
|
![[img]](https://repository.mercubuana.ac.id/style/images/fileicons/text.png) |
Text (BAB I)
02 BAB 1.pdf Restricted to Registered users only Download (95kB) |
|
|
Text (BAB II)
03 BAB 2.pdf Restricted to Registered users only Download (189kB) |
|
|
Text (BAB III)
04 BAB 3.pdf Restricted to Registered users only Download (323kB) |
|
|
Text (BAB IV)
05 BAB 4.pdf Restricted to Registered users only Download (277kB) |
|
|
Text (BAB V)
06 BAB 5.pdf Restricted to Registered users only Download (86kB) |
|
|
Text (DAFTAR PUSTAKA)
08 DAFTAR PUSTAKA.pdf Restricted to Registered users only Download (135kB) |
|
|
Text (LAMPIRAN)
09 LAMPIRAN.pdf Restricted to Registered users only Download (492kB) |
Abstract
English vocabulary mastery is a fundamental component in academic learning; however, conventional passive and monotonous methods remain a major obstacle that reduces students' motivation and learning effectiveness. This research develops a web-based educational Crossword game designed to support English vocabulary learning for university students in general. The primary challenge in Crossword game development is the automatic puzzle generation that must be efficient, dense, and valid in real-time. This research implements a Greedy algorithm based on the Length-first Greedy Crossword Placement approach with a Maximum Intersection heuristic on a Laravel-based backend, where each new word is placed at the position that produces the highest number of letter intersections with words already placed in the grid. The word list is sorted in descending order by length (longestfirst) prior to the placement process, and a random restart mechanism is applied to address the inherent local limitations of the Greedy algorithm. This research adopts a Research and Development (R&D) approach using the ADDIE model. Functional testing was conducted using the Black Box Testing method, while puzzle quality was evaluated through placement rate, intersection count, and grid density metrics over 10 iterations for each theme-level combination. Test results indicate an average placement rate of 94.26% across all combinations, with average intersections increasing from 3.65 at the Beginner level to 6.95 at the Expert level, and grid density ranging from 13.12% to 24.62%. All major system features operated according to specification based on Black Box Testing results. This system is expected to serve as an interactive, modern, and effective English vocabulary learning media solution for university students. Kata kunci: Greedy Algorithm, Maximum Intersection, Crossword Puzzle, Educational Game, Laravel, Vocabulary. Penguasaan kosakata bahasa Inggris merupakan komponen fundamental dalam pembelajaran akademik, namun metode konvensional yang bersifat pasif dan monoton menjadi kendala utama yang menurunkan motivasi dan efektivitas belajar mahasiswa. Penelitian ini mengembangkan game edukatif berbasis web berupa permainan Crossword yang dirancang untuk mendukung pembelajaran kosakata bahasa Inggris bagi mahasiswa secara umum. Tantangan utama dalam pengembangan game Crossword adalah pembangkitan puzzle secara otomatis yang efisien, padat, dan valid secara waktu nyata. Penelitian ini mengimplementasikan algoritma Greedy dengan pendekatan Length-first Greedy Crossword Placement dan heuristik Maximum Intersection pada backend berbasis Laravel, di mana setiap kata baru ditempatkan pada posisi yang menghasilkan jumlah perpotongan huruf (intersection) terbanyak dengan kata-kata yang sudah ada di grid. Daftar kata diurutkan secara menurun berdasarkan panjang (longest-first) sebelum proses penempatan, dan mekanisme random restart diterapkan untuk mengatasi keterbatasan lokal algoritma Greedy. Penelitian ini menggunakan pendekatan Research and Development (R&D) dengan model ADDIE. Pengujian fungsionalitas dilakukan menggunakan metode Black Box Testing, sementara kualitas puzzle dievaluasi melalui pengukuran metrik placement rate, jumlah intersection, dan kerapatan grid pada 10 iterasi untuk setiap kombinasi tema dan level kesulitan. Hasil pengujian menunjukkan rata-rata placement rate sebesar 94,26% di seluruh kombinasi tema dan level, dengan rata-rata intersection meningkat dari 3,65 pada level Beginner hingga 6,95 pada level Expert, serta kerapatan grid berkisar antara 13,12% hingga 24,62%. Seluruh fitur utama sistem berjalan sesuai spesifikasi berdasarkan hasil Black Box Testing. Sistem ini diharapkan menjadi solusi media pembelajaran kosakata bahasa Inggris yang interaktif, modern, dan efektif bagi mahasiswa. Kata kunci: Algoritma Greedy, Maximum Intersection, Crossword Puzzle, Game Edukatif, Laravel, Kosakata.
Actions (login required)
 |
View Item |
