PROJEK HCI

 

Laporan HCI

Trofí

Anggota Kelompok :

• Charleen - 2301863811
• Cheryl Angelica - 2301855854
• Hendrik Purnama - 2301855816
• Philips – 2301877344

I.               Strategic Objective

Kelompok kami mengangkat tema Empowering the Society dari 4 tema yang telah disediakan. Empowering the Society atau pemberdayaan masyarakat merupakan sebuah upaya yang dilakukan dalam rangka mengembangkan potensi masyarakat dan mengatasi berbagai permasalahan yang ada di dalam masyarakat. Kami mengangkat tema ini karena kami ingin membantu meringankan permasalahan yang ada di masyarakat khususnya Indonesia walaupun permasalahan tersebut sederhana. Kami berharap solusi yang kami tawarkan dapat benar-benar bermanfaat bagi masyarakat banyak.

 

II.            Problem

Banyak orang yang mengalami kesulitan dalam menemukan tempat makan atau restoran yang benar-benar menyajikan makanan yang lezat. Belum lagi jika orang tersebut berada di tempat yang asing atau sedang bepergian ke luar kota (travelling) sehingga mereka tidak tahu makanan apa saja yang tersedia di lokasi tersebut. Jika masuk ke tempat makan secara acak, belum tentu tempat makan tersebut menyediakan makanan yang diinginkan, rasa yang lezat, dan menyediakan pelayanan yang baik.

 

III.          Solution

Solusi yang telah kami sediakan untuk mengatasi permasalahan yang dijabarkan diatas adalah menyediakan layanan pencarian makanan secara online. Zaman sekarang, teknologi sudah sangat berkembang dan maju. Hampir setiap orang di dunia, termasuk Indonesia sudah menggunakan internet. Menurut laporan yang dirilis oleh layanan manajemen konten HootSuite, pengguna internet di Indonesia pada awal 2021 ini mencapai 202.6 juta jiwa. Ini artinya penggunaan internet di Indonesia pada awal 2021 mencapai 73.7%. Kami memanfaatkan perkembangan ini untuk membantu mengatasi permasalahan yang kami angkat. Oleh karena itu, kami menyediakan layanan pencarian tempat makanan dalam satu website yang bernama trofí.

 

IV.          Establishing Requirements

Trofi berasal dari bahasa Yunani yang berarti makanan. Website ini berisi informasi tentang tempat makan di seluruh Indonesia. Baik tempat makan ternama maupun tidak ternama. Informasi yang dimaksud seperti letak tempat makan, jam operasi, nomor telepon, menu, rentang harga, dan website yang dimiliki oleh tempat makan tersebut (jika ada). Tidak hanya menyediakan informasi mengenai tempat makan, di dalam website ini pengguna dapat berinteraksi dengan memberikan rating dan review kepada tempat makan yang telah mereka kunjungi. Pengguna juga dapat memasukkan gambar makanan ataupun tempat makan tersebut untuk dilihat oleh pengguna lain yang sedang mencari tempat makan yang pas. Target pengguna kami dalam pembuatan website trofí ini adalah orang yang sedang kesulitan dalam mencari tempat makan. Website ini dapat digunakan oleh semua rentang umur yang telah dapat menggunakan internet, baik muda maupun tua.   

 

V.              Designing Alternatives

A.    Conceptual Design

Pengguna dapat berinteraksi langsung dengan website trofí ini. Contohnya adalah seperti pengguna dapat menekan tombol-tombol yang ada pada website dan mengetik tempat makan ataupun makanan yang ingin dicari oleh pengguna. Website trofí  terdiri dari beberapa halaman dan di halaman tersebut terdapat tombol yang dapat ditekan oleh pengguna. Ketika pengguna menekan tombol yang ada pada website trofí maka pengguna akan dibawa ke halaman lain dari website trofi tersebut.

 

B.    Physical Design

Warna utama yang kita pakai untuk membuat user interface dari trofí ini adalah merah seperti pada header dan tombol-tombol pada website.

Berikut merupakan beberapa tombol dan icon yang digunakan pada website trofí.

  

Berikut merupakan header yang dipakai untuk website trofí.

 

Gambar-gambar yang dipakai merupakan gambar makanan dan tempat yang berasal dari pengguna ataupun website trofí sendiri.

 

II.            Prototyping

Kami membuat prototype design dengan menggunakan tools Figma. Berikut merupakan User Interface yang telah kami buat untuk trofí:

-       Homepage :

    

    Ini adalah tampilan homepage trofí disaat pengguna membuka website ini. Pada halaman ini terdapat pencarian nama makanan ataupun tempat makan yang ingin pengguna cari dan juga ada daerah dimana mereka berada. Ada juga tombol ‘Write a review’ yang nanti jika kita tekan, website akan memandu pengguna ke halaman log in dan pengguna harus mendaftar jika tidak mempunyai akun. Lalu konten pada homepage trofí menampilkan makanan yang dekat dengan pengguna. Selain itu, terdapat juga pencarian berdasarkan kategori makanan yang diinginkan oleh pengguna. Jika pengguna sudah masuk ke dalam akun yang telah dibuat, maka di sebelah kanan atas homepage trofí berubah menjadi profile / akun pengguna.

                -       Sign Up Page:

    Halaman sign up akan muncul ketika pengguna ingin mendaftarkan akun dengan menekan tombol sign up yang terdapat di kanan atas homepage. Pengguna juga dapat mendaftarkan diri melalui facebook ataupun google.

-      Log in Page:

    Halaman log in akan terbuka ketika pengguna mengklik tombol ‘log in’ yang ada pada home page di sebelah kanan atas atau mengklik tombol ‘Write a review’ ketika pengguna belum masuk ke dalam akun yang telah dibuat. Pengguna juga dapat masuk ke akun trofí melalui facebook dan google jika mereka mendaftarkan diri melalui kedua platform tersebut. Jika terjadi kesalahan pada email dan password maka terdapat error message yaitu ‘invalid email or password’.

 

-      Search Page:

Pengguna dapat melakukan pencarian tempat makan ataupun makanan melalui homepage. Ketika mengklik tombol search maka akan terbuka tampilan search page.

Pada halaman search trofí, pengguna bisa melakukan pencarian dan menemukan tempat makan yang dicari. Agar dapat melihat informasi dari tempat makan yang ada, pengguna harus memilih salah satu dari tempat makan yang disediakan oleh website trofí.

Pengguna dapat melihat rating yang diberikan pengguna lain (yang ditampilkan merupakan rata-rata dari rating tersebut). Lalu ada opsi untuk Add Review dan juga Get direction untuk tahu dimana restaurant yang menyediakan makanan yang kita cari. Disini juga terdapat informasi lengkap tentang tempat makan tersebut seperti alamat, jam operasi, nomor kontak, dan website yang dimiliki oleh tempat makan tersebut (jika ada). Pengguna dapat menggunakan fitur bookmark untuk menyimpan data tempat makan yang dipilih oleh mereka dan share untuk membagikan kepada pengguna lain agar dapat melihat tempat makan tersebut melalui website trofí.

Jika website tidak dapat menyediakan makanan atau tempat makan yang dicari oleh pengguna, maka tampilan halaman search akan terdapat tulisan ‘Result Not Found’.

Jika pengguna membuka See More maka pengguna dapat akan diarahkan ke halaman Restaurant Info.

-       Restaurant info page:

    Halaman restaurant info akan terbuka jika pengguna mengklik see more pada search page. Informasi tentang tempat makan yang ada diperjelas dan ditambah dengan average price. Pengguna juga dapat melihat reviews dari pengguna lain dan menu dengan harga yang terdapat pada tempat makan tersebut.

-      Add Review:

    Modal add review akan muncul ketika pengguna mengklik tombol add review pada halaman restaurant info ataupun pada detail search page. Modal add review disajikan kepada pengguna untuk berbagi informasi. Disini pengguna tentunya bisa memberikan rating terhadap makanan yang pengguna coba ataupun secara keseluruhan tempat makannya. Pengguna dapat membuat review dengan memberikan gambar makanan ataupun tempat makan yang ada.

Jika pengguna tidak mengisi rating maka akan muncul error message 

    ‘This must not be empty’

    Jika pengguna berhasil memasukkan review maka akan muncul success message 

    ‘Your review has been added successfully’.

 

-      History Page:

Halaman history akan muncul ketika pengguna mengklik tombol akun yang ada pada kanan atas setiap halaman. Halaman history ini dibuat agar pengguna dapat melihat review-review dari tempat makan yang dilihat sebelumya. Disini pengguna bisa kembali ke halaman restaurant info yang memiliki review tersebut dan tentunya review ini dapat di sortir dengan berbagai parameter namun normalnya akan di set paling baru sebagai default dari parameter sort trofí.

-      Saved Place Page:

Halaman saved place akan muncul ketika pengguna mengklik tombol akun pada kanan atas yang ada pada setiap halaman. Halaman saved place ini merupakan halaman yang menyimpan semua bookmark yang dipilih di halaman search dan halaman restaurant info. Kegunaan utama fungsi ini tentunya untuk mengecek ulang atau mengecek kembali tempat yang pernah pengguna simpan untuk dilihat kembali.

 

III.           Evaluating

Evaluasi dari website trofí dilakukan dengan menggunakan evaluasi heuristic dimana heuristic evaluation itu sendiri merupakan proses dimana kami akan menilai usability dari UI. Terdapat 3 tahap yang kami lakukan yaitu briefing session, evaluation period, dan debriefing session.

 

1.     Briefing Session

Disini kami membagi tugas kepada masing-masing anggota untuk mengevaluasi system, kami berbagi tugas mengenai apa saja yang harus dilakukan dan juga apa saja poin yang harus diperhatikan.

 

2.     Evaluation Period

Disini kami menggunakan poin-poin yang heuristic evaluation seperti clarity, minimize unnecessary complexity and cognitive load, provide user with context, dan promote a pleasurable and positive user experience untuk panduan bagaimana cara mengevaluasi sistem kami dan mencatat apa saja masalah yang ada.

 

3.     Debriefing Session

Disini kami kembali diskusi bersama untuk menampilkan masalah yang ditemukan dan juga mencari solusi yang bisa kami pakai untuk menyelesaikan masalah-masalah tersebut.

Rangkuman Final Data Struct

Nama : Charleen
NIM : 2301863811
Kelas : CB01
Nama Dosen : 
- Ferdinand Ariandy Luwinda (D4522)
- Henry Chong (D4460)

Kelas : LB08
Nama Dosen :
- Diana (D4458)

AVL TREE

Pengertian AVL Tree :
AVL Tree adalah Binary Search Tree yang memiliki perbedaan tinggi/ level maksimal 1 antara subtree kiri dan subtree kanan. AVL Tree muncul untuk menyeimbangkan Binary Search Tree. Dengan AVL Tree, waktu pencarian dan bentuk tree dapat dipersingkat dan disederhanakan.

Contoh AVL Tree

Tree diatas adalah AVL karena perbedaan tinggi kanan dan kiri subtrees untuk setiap nodes sama dengan satu atau dibawah satu. 

Contoh bukan AVL Tree

Tree diatas bukan AVL karena perbedaan tinggi kanan dan kiri subtrees untuk 11 dan 30 diatas satu.

Mengapa AVL Tree?
Sebagian besar operasi Binary Search Tree (search,insertion,deletion,dll) membutuhkan O(h) waktu dimana h adalah ketinggian BST, bahkan bisa O(n) untuk Binary Tree yang miring. Jika ketinggian pohon disesuaikan menjadi O(log n) setelah semua operasi insertion dan deletion, maka bisa dipastikan batas atas O(Log n) untuk semua operasi. Ketinggian AVL Tree selalu O(Log n) dimana n adalah jumlah node di pohom.

Insertion
Untuk memastikan Tree tetap AVL Tree setelah semua insertion, kita harus menggunakan operasi insertion standar BST untuk penyeimbangan. Berikut adalah 4 operasi dasar yang bisa dilakukan untuk menyeimbangkan Tree tanpa melanggar properti Tree (keys(left) < key(root) < keys(right))

Single Rotation
1. Left-left rotation
Jika Tree tidak seimbang, ketika sebuah node di insert ke subtree kanan nya subtree kanan, maka kita lakukan Single Left Rotation.

Di contoh, node A menjadi tidak seimbang karena sebuah node di insert ke subtree kanan nya subtree kanan A. Rotation dilakukan dengan membuat A subtree kiri dari B.

2. Right-right rotation
AVL Tree akan menjadi tidak seimbang apabila sebuah node di insert ke subtree kiri nya subtree kiri. Tree akan membutuhkan Single right rotation.

Seperti digambar, node yang tidak seimbang akan menjadi anak kanan dari anak kiri dengan melakukan Single right rotation.

Double Rotation
3. Left-right rotation
Double rotation agak sedikit lebih kompleks dibandingkan single rotation. Agar lebih mengerti, kita harus membahas setiap langkah satu persatu. Left-right rotation adalah kombinasi left rotation diikuti right rotation.

Sebuah node di insert ke subtree kanan nya subtree kiri. Itu menyebabkan C menjadi node tidak seimbang. Skenario ini membuat AVL melakukan Left-right rotation.

Pertama kita lakukan left rotation di subtree kiri dari C. Ini membuat A menjadi subtree kiri dari B. 

Node C masih belum seimbang, tetapi sekarang karena subtree kiri dari subtree kiri.

Sekarang kita lakukan right rotation ke Tree, membuat B menjadi root baru di subtree ini. C sekarang menjadi subtree kanan dari subtree kirinya.

    

Tree sudah seimbang.

4. Right-left rotation
Double rotation kedua, adalah kombinasi dari right rotation dilanjutkan dengan left rotation.

Sebuah node telah di insert ke subtree kiri dari subtree kanan. Ini menyebabkan A menjadi tidak seimbang. 

Pertama kita lakukan right rotation di node C, membuat C menjadi subtree kanan dari subtree kiri nya sendiri (B). Sekarang B menjadi subtree kanan nya A. 

Node A masih belum seimbang karena subtree kanan dari subtree kanan, sehingga membutuhkan left rotation.

Left rotation dilakukan dengan membuat B menjadi root node yang baru dari subtree. A menjadi subtree kiri dari subtree kanan B.

Tree sudah seimbang.

Deletion
Menghapus sebuah node di AVL Tree mirip dengan BST. Deletion bisa mengganggu keseimbangan AVL Tree, maka Tree harus diseimbangkan setelahnya dengan melakukan rotation. 

Terdapat 2 kasus yang biasanya terjadi saat operasi delete dilakukan, yaitu :

- Jika node yang akan dihapus berada pada posisi leaf atau node tanpa anak, maka dapat langsung di hapus.
- Jika node yang akan dihapus memiliki anak, maka proses penghapusannya harus di cek kembali untuk menyeimbangkan Tree dengan AVL.

Rotation yang digunakan sama dengan insertion, yaitu :
1. Left Rotation
2. Right Rotation
3. Left-right Rotation
4. Right-left Rotation

Contoh Deletion:

Kita mau delete node 30 di tree diatas

Disini, node B mempunyai faktor keseimbangan 0, maka Tree di rotate dengan right rotation. Node B menjadi root, sedangkan A dipindahkan ke kanan. Anak kanan dari node B menjadi anak kiri node A.

2-3 Tree (B-Tree)

2-3 Tree adalah salah satu tipe struktur data yang setiap node internal memiliki satu elemen data dan dua anak atau dua elemen data dan tiga anak. Jika sebuah node berisi satu elemen data value kiri, ia memiliki dua subtree yaitu kiri dan tengah. Sedangkan jika sebuah node berisi dua elemen data value kiri dan value kanan, ia memiliki tiga subtree yaitu kiri, tengah dan kanan. Keuntungan dari 2-3 Tree adalah lebih seimbang bila dibandingkan dengan Binary Search Tree.

INSERTION

Tahap / Aturan dalam melakukan insertion:

1.      Pertama kita harus mencari dimana data tersebut harus diletakkan di 2-3 Tree menggunakan searching, maka akan ditemukan 1 leaf yang tepat untuk melakukan insertion.

Ada 3 kemungkinan kasus dalam insertion

(1)   Insert di node yang hanya ada 1 elemen data

(2)   Insert di node yang memiliki 2 elemen data yang parent nya hanya memiliki 1 elemen data

(3)   Insert di node yang memiliki 2 elemen data dan parent nya juga memilki 2 elemen data

2.      Jika leaf yang dituju memiliki 2 node, maka kita cukup insert data baru tersebut, sehingga menjadi 3 node.

3.      Jika leaf yang dituju sudah memiliki 3 node. Maka simulasikan dengan memasukkan data baru diantara data A dan B (A dan B adalah dua data yang terdapat di 3 node tersebut). Nilai data yang berada di tengah-tengah antara nilai A, B, dan data baru akan naik ke parent dan membagi 2 sisanya menjadi 2 node. Secara rekursif memperbaiki pada parent nya.

DELETION

Tahap / Aturan dalam melakukan delete

1.      Seperti BST, pertama kita harus melakukan searching untuk leaf yang memiliki data yang kita cari.

2.      Jika leaf nya memiliki 3 node, maka kita tinggal melakukan operasi delete dan dijadikan 2 node.

3.      Jika leaf nya memiliki 2 node:

-          Jika parent memiliki 3 node, maka ambil 1 nilai dari 3 node tersebut. Jika sibling nya 3 node, maka dorong nilai tersebut dari sibling ke parent untuk membuat parent menjadi 3 node lagi. Jika sibling nya adalah 2 node, buat parent nya menjadi 2 node dan gabungkan node dengan sibling nya.

-          Jika parent nya 2 node, jika sibling nya 3 node, maka ambil satu nilai dari parent dan dorong satu nilai dari sibling ke parentnya sendiri. Hal lainnya yaitu mengabungkan parent dengan sibling. 

Red Black Tree

Red Black Tree adalah salah satu tipe self-balancing BST (disebut juga simetris binary B-tree) yang kompleks dengan menggunakan warna merah dan hitam. Meskipun RBT rumit, tetapi sangat efisien saat melakukan insert, delete, search.

Karakteristik Red Black Tree:

1.      Setiap node berwarna merah (Red) atau hitam (Black).

2.      Root node selalu berwarna hitam.

3.      Setiap node leaf juga berwarna hitam.

4.      Node yang berwarna merah akan memiliki 2 child berwarna hitam (node merah tidak boleh memiliki child merah).

5.      Jumlah node hitam sama dari root ke eksternal node.

6.      Node yang berada dibawah root apabila di level yang sama, disebut juga sibling.

7.      Tree seimbang apabila selisih level antara subtree kanan dan kiri root hanya berselisih 2.

Insertion pada RBT

Insertion pada Red Black Tree memiliki beberapa aturan, yaitu:

1.      Node yang di-insert awalnya akan diberi warna merah kecuali root. (Apabila melanggar karakteristik RBT baru diubah warnanya).

2.      Jika parent dari node yang baru di-insert berwarna hitam maka tidak terjadi pelanggaran.

3.      Jika parent dari node yang di-insert berwarna merah juga maka akan dilakukan rotasi atau pewarnaan ulang, cara-nya sebagai berikut:

-          Jika node yang di-insert memiliki paman/uncle (sibling dari parent) yang berwarna merah. Maka ubah warna parent dan uncle menjadi hitam dan kakek dari node tersebut menjadi merah (kecuali jika kakek adalah root).

-          Jika node yang di-insert memiliki parent merah tetapi paman-nya berwarna hitam (atau NULL), maka bisa dilakukan single atau double rotation. Ganti pivot terakhir menjadi hitam dan anaknya menjadi merah.

4.      Perlu diingat bahwa node yang tidak memiliki leaf harus berwarna hitam.

Deletion pada RBT

            Berikut cara melakukan deletion pada Red Black Tree:

1.      Delete dilakukan seperti pada Binary Search Tree

2.      Jika node yang ingin di-delete berwarna merah, maka tinggal kita ganti node yang ingin dihapus dengan childnya yang berwarna hitam.

3.      Jika node yang ingin di-delete berwarna hitam, maka ganti node yang ingin dihapus dengan childnya dan ubah warna childnya menjadi warna hitam.

4.      Jika node yang ingin di-delete dan childnya sama-sama berwarna hitam, maka yang harus kita lakukan adalah :

a.       Ganti node yang ingin dihapus dengan childnya, lalu, ganti childnya sehingga mempunyai token double black (N).

b.      Jika siblingnya berwarna merah tukar warna N dan parentnya, lalu rotate di parentnya.

c.       Jika sibling, child kiri, dan child kanan berwarna hitam, maka ganti warna sibling menjadi merah.

d.      Jika sibling berwarna hitam, child kiri dan child kanan nya berwarna merah, maka lakukan single atau double rotation.

5.      Jika node yang ingin di-delete adalah root, maka token double black bisa dihapus.

HEAP

Heap adalah struktur data tree yang merupakan complete binary tree (bukan binary search tree). Heap memiliki beberapa properties yaitu :

1. Min Heap

• Setiap node lebih kecil dari masing-masing childnya.
• Root memiliki nilai terkecil. Nilai terbesar terletak di leaf node.

 

2. Max Heap

• Setiap node lebih besar daripada childnya.
• Root memiliki nilai terbesar. Nilai terkecil terletak di leaf node.

3. Min-Max Heap

• Heap dengan Min Heap pada level genap dan Max Heap pada level ganjil.

Heap dapat diimplementasikan dengan array juga linked list.

Aplikasi pada heap :

1. Priority Queue

- Selection Algorithm

- Dijkstra's Algorithm

- Prim Algorithm

2. Heap Sort

Implementasi Heap menggunakan array;

- Array dimulai dengan indeks ke 1

- Rumus umum aplikasi heap dengan array (x adalah current node) :

Parent(x) = x/2

Left-child(x) = 2*x

Right-Child(x) = 2*x+1

Min Heap (Ascending Order) :

- Insertion pada Min Heap

1. Insert node selalu berurutan dari level paling rendah dengan urutan kiri ke kanan.

2. New node selalu menjadi leaf node.

3. Sesuaikan sesuai properti heap secara rekursif.

- Deletion pada Min Heap

1. Node yang dihapus selalu root karena node yang paling kecil, lalu diganti dengan node yang paling terakhir di insert.

2. Sesuaikan dengan properti heap secara rekursif.

Hapus node 7

7 diganti dengan elemen terakhir

Max Heap (Descending Order) :

- Insertion pada Max Heap

1. Periksa apakah node yang akan dimasukkan sudah lebih kecil dibandingkan parentnya.

2. Apabila node yang dimasukkan lebih besar daripada parentnya, maka swap posisi node tersebut dengan parentnya.

3. Begitu seterusnya sampai root merupakan data paling besar.

- Deletion pada Max Heap

1. Jika ingin menghapus root maka yang perlu dilakukan adalah menggantikan root dengan menggunakan node paling terakhir dari tree.

2. Jika root masih lebih kecil daripada child-nya, maka swap root dengan child-nya.

3. Begitu seterusnya sampai data di root merupakan data terbesar.

Min-Max Heap

- Insertion pada Min-Max Heap

Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:

1. Parent

2. Grand Parent

- Deletion pada Min-Max Heap

Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebagai berikut:

1. Grand child

2. Child (grand child disesuaikan dengan parentnya)

TRIES

- Tries adalah binary tree yang dilakukan untuk menyimpan array asosiatif.

- Properties pada tries :

1. Setiap node merepresentasikan satu huruf.

2. Root selalu merepresentasikan node kosong.

- Aplikasi pada trees adalah fitur auto complete yang ada pada browser.

~ Thankyou ~