Skip to content

Latest commit

 

History

History
199 lines (161 loc) · 9.35 KB

README.md

File metadata and controls

199 lines (161 loc) · 9.35 KB
Raw

CourseScheduler - BackEnd

Course Scheduler Web

Table of Contents

  1. General Info
  2. Creator Info
  3. Features
  4. Technologies Used
  5. Setup
  6. Usage
  7. Algorithm
  8. Video Capture
  9. Screenshots
  10. Structure
  11. Project Status
  12. Room for Improvement
  13. Acknowledgements
  14. Contact

General Information

Sebuah aplikasi berbasis website sederhana yang dapat digunakan untuk melakukan pencarian data mata kuliah agar memperoleh nilai maksimal dengan memanfaatkan algoritma dynamic programming, menambah data mata kuliah via text field dan JSON file, menampilkan data mata kuliah dan melakukan penghapusan data mata kuliah. Website ini dibangun dengan React sebagai Framework FrontEnd, Golang sebagai Framework BackEnd, dan MySQL sebagai database. Repository Backend dan Frontend terpisah satu sama lain. Tugas ini digunakan untuk memenuhi Tugas 8 Seleksi Lab IRK tahun 2023.

Creator Information

Nama NIM E-Mail
Mohammad Rifqi Farhansyah 13521166 [email protected]

Features

  • Mencari data mata kuliah pada SearchPage agar mendapatkan nilai maksimal dengan algoritma dynamic programming
  • Menambahkan data mata kuliah dengan TextField atau JSON File pada Add Page
  • Melihat data mata kuliah dan menghapus data mata kuliah pada Data Page

Technologies Used

Note: The version of the libraries above is the version that we used in this project. You can use the latest version of the libraries.

Setup

  1. Clone Repository ini dengan menggunakan command berikut 
    git clone https://github.com/rifqifarhansyah/CourseScheduler_Backend.git
  2. Buka Folder "coursescheduler_backend" di Terminal
  3. Jalankan script docker dengan menjalankan 
    docker compose build
  4. Lalu jalankan program dengan perintah 
    docker compose up
  5. Program backend akan otomatis dijalankan pada localhost (default PORT:5001)
  6. Atau dengan cara lain yaitu membuka pranala berikut ini

Usage

  1. Untuk mencari mata kuliah yang menghasilkan nilai maksimal, masuk ke Search Page lalu isi seluruh text field yang diminta, kemudian tekan tombol search
  2. Untuk menambahkan mata kuliah, masuk ke Add Page lalu pilih metode yang hendak digunakan, apabila menggunakan metode text field, isi seluruh text field yang diminta, kemudian tekan tombol add
  3. Apabila penambahan mata kuliah dilakukan via JSON File, maka terlebih dahulu cek JSON Example, sesuaikan format JSON masukan, lalu tekan Choose File untuk memilih file JSON yang hendak digunakan
  4. Untuk melihat data mata kuliah yang ada, masuklah ke Data Page
  5. Sementara itu, penghapusan data mata kuliah dapat dilakukan dengan menekan icon kotak sampah di samping tiap data mata kuliah pada data page

Algorithm

Deskripsi Umum Algoritma Dynamic Programming

Algoritma Dynamic Programming adalah sebuah metode untuk memecahkan masalah yang bisa dipecahkan dengan cara memecahkannya menjadi submasalah yang lebih kecil, kemudian menyimpan solusi dari setiap submasalah yang telah dipecahkan untuk menghindari perhitungan yang berulang. Teknik ini umumnya digunakan untuk mengoptimalkan masalah di mana solusi optimal dapat dicapai dengan menggabungkan solusi dari submasalah yang lebih kecil.

Penerapan Algoritma Dynamic Programming pada Program

Pada kode program ini, terdapat fungsi searchCourses yang menggunakan algoritma Dynamic Programming untuk menyelesaikan masalah Knapsack (rucksack) dengan sedikit variasi. Masalah Knapsack umumnya adalah masalah di mana kita memiliki beberapa item dengan nilai tertentu dan kapasitas tertentu di dalam knapsack, dan kita perlu memilih kombinasi item yang menghasilkan nilai maksimum tanpa melebihi kapasitas knapsack.

Dalam kasus kode di bawah, kita memiliki sejumlah mata kuliah dengan bobot SKS tertentu dan nilai prediksi untuk setiap mata kuliah. Tujuan dari algoritma ini adalah untuk memilih kombinasi mata kuliah yang memiliki bobot SKS maksimum yang tidak melebihi batas maksimum yang telah ditentukan, dengan nilai prediksi total yang maksimal.

Analisis Penerapan Algoritma Dynamic Programming

  1. Langkah Persiapan
  • Mata kuliah yang relevan dengan jurusan dan fakultas masukan diambil menggunakan fungsi getCoursesByJurusanFakultas. Kemudian, mata kuliah yang sesuai dengan semester yang diinginkan (semesterPengambilan) dipilih dan disimpan dalam validCourses.
  1. Inisialisasi DP Table
  • dp adalah tabel dua dimensi untuk menyimpan nilai prediksi maksimum yang dapat dicapai dengan memilih kombinasi mata kuliah tertentu, dengan jumlah SKS yang telah ditentukan. dp[i][w] akan berisi nilai prediksi maksimum dengan mempertimbangkan i mata kuliah pertama dan memiliki total SKS maksimum w.
  1. Dynamic Programming - Proses Pengisian DP Table
  • Melalui iterasi untuk setiap mata kuliah dan total SKS yang mungkin, tabel dp diisi dengan nilai prediksi maksimum. Jika SKS dari mata kuliah ke-i (validCourses[i-1].JumlahSks) lebih kecil dari atau sama dengan total SKS w, maka ada dua pilihan: Memasukkan mata kuliah ke-i dalam kombinasi dengan mempertimbangkan nilai prediksi getKonversiValue(validCourses[i-1].PrediksiNilai) atau tidak memasukkan mata kuliah ke-i dalam kombinasi.Pilihan terbaik diambil menggunakan fungsi max untuk memperbarui nilai dp[i][w].
  1. Memilih Mata Kuliah yang Menghasilkan Nilai Prediksi Maksimum
  • Setelah tabel dp terisi, kita dapat menemukan kombinasi mata kuliah dengan nilai prediksi maksimum yang tidak melebihi batas SKS (maxSKS). Mata kuliah yang terpilih disimpan dalam selectedCourses dengan membalik iterasi melalui tabel dp.
  1. Hasil
  • selectedCourses berisi daftar mata kuliah yang dipilih yang akan dikembalikan sebagai respons dari fungsi searchCoursesAPI.

Analisis Kompleksitas

Untuk menganalisis kompleksitas algoritma di atas, kita perlu mempertimbangkan dua tahap utama dari algoritma tersebut:

  1. Inisialisasi DP Table: Algoritma melakukan inisialisasi tabel dp dengan ukuran n+1 (jumlah mata kuliah + 1) baris dan maxSKS+1 kolom, di mana n adalah jumlah mata kuliah yang sesuai dengan semester yang diinginkan. Oleh karena itu, kompleksitas inisialisasi tabel adalah O(n * maxSKS).

  2. Proses Pengisian DP Table: Algoritma menggunakan dua loop bersarang untuk mengisi nilai-nilai tabel dp. Loop pertama memiliki n iterasi, dan loop kedua memiliki maxSKS iterasi. Dalam setiap iterasi, terdapat operasi konstan yang dilakukan (cek kondisi, pemilihan nilai maksimum dengan fungsi max, dan operasi aritmatika lainnya). Oleh karena itu, kompleksitas pengisian tabel adalah O(n * maxSKS).

Oleh karena kedua tahap tersebut dilakukan secara terpisah (tidak bersarang), kompleksitas keseluruhan algoritma adalah penjumlahan dari kedua kompleksitas tersebut:

Kompleksitas Total = O(n * maxSKS) + O(n * maxSKS) = O(n * maxSKS)

Jadi, kompleksitas algoritma Dynamic Programming di atas adalah O(n * maxSKS), dengan n adalah jumlah mata kuliah yang sesuai dengan semester yang diinginkan dan maxSKS adalah kapasitas maksimum SKS yang diizinkan.

Video Capture

CourseScheduler Gif

Screenshots

Gambar 1. Search Page

Gambar 2. Add Page via Text Field

Gambar 3. Add Page via JSON File

Gambar 4. JSON File Example

Gambar 5. Data and Remove Page

Gambar 6. Searching Result

Structure

│   .env
│   docker-compose.yml
│   Dockerfile
│   go.mod
│   go.sum
│   main
│   main.go
│   README.md
│
├───img
│       CourseScheduler.gif
│       SS1.png
│       SS2.png
│       SS3.png
│       SS4.png
│       SS5.png
│       SS6.png
│
└───tes
        tes1.json
        tes2.json

Project Status

Project is: complete

Room for Improvement

Perbaikan yang dapat dilakukan pada program ini adalah:

  • Meningkatkan efektifitas algoritma dynamic programming

Acknowledgements

  • Terima kasih kepada Tuhan Yang Maha Esa

Contact

Kontak Saya : [email protected]
2023