HELLO

Graph adalah data struktur yang bersifat abstrak, di dalam graph suatu titik disebut vertex dan garis penghubung setiap vertex disebut dengan edges, sedangkan degree adalah berapa banyak jumlah edges yang terhubung dengan sebuah vertex.

Selain itu, juga terdapat 2 jenis graph yaitu directed graph dan undirected graph, dimana

Directed graph adalah graph yang edgenya memiliki arah.

Undirected graph hanya memiliki edge berupa garis saja.

Untuk menemukan minimm spanning tree di dalam graph dapat digunakan 2 metode yaitu:

Prim algorithm

Kruskal algorithm

PRIM ALGORITHM

Algotima untuk prim adalah dengan cara memilih 1 titik awal kemudian kita menentukan lagi jalan berikutnya yang harus diambil dengan fee atau cost terkecil. Sehingga pada intinya prim algorithm memiliki cara menentukan jalan step by step.

KRUSKAL ALGORITHM

Algoritma kruskal sedikit berbeda dengan prim meskipun mereka memiliki tujuan yang sama yaitu untuk mendapatkan cost atau fee terkecil untuk dadpat mengelilingi semua vertex yang ada. Pada kruskal yang dilakukan adalah mengumpulkan terlebih dahulu edge edge dengan cost terkecil kemudian barulah setial edge edge tersebut dihubungkan.

Selain itu juga ad acara untuk menemukan the shortest path dimana disebut Dijkstra

Di dalam Dijkstra biasanya akan sedikit berbeda, dimana biasanya kita akan mencari jalan dengan cost terkecil untuk menuju suatu vertex yang telah ditentukan.

Misalnya:

Temukan shoetest path menuju F dari A

maka jawabannya adalah

A-C-D-E-F dengan cost terkecil yaitu 5.

HEAP adalah complete binary tree.

Terdapat 3 jenis heap yaitu:

Min heap

Max heap

Min-max heap

MIN HEAP adalah tree yang memiliki root berupa anggota terkecil dibandingkan denga child-childnya.

Sehingga ketika kita ingin mencari data terkecil, hanya perlu untuk melakukan pop pada data paling atas/ rootnya saja.

Setiap node di Min heap pasti lebih kecil dibangdingkan dengan childnya.

Elemen terbesar di dalam Min heap terdapat pada salah satu leaf node.

Untuk memudahkan penulisan code Min heap cukup gunakan array.

Gambar diatas merupakan salahsatu contoh Min heap yang benar.

INSERT PADA MIN HEAP

Dalam memasukkan data ke dalam Min heap, yang perlu kita lakukan adalah

Selalu memeriksa apakah node yang di push sudah lebih besar dibandingkan parentnya.

Apabila node yang di push lebih kecil daripada parentnya, maka swap posisi node tersebut dengan parentnya.

Begitu seterusnya.

DELETE PADA MIN HEAP

apabila yang ingin dihapus adalah rootnya maka yang perlu dilakukan adalah

Menggantikan root dengan menggunakan node paling terakhir dari tree.

Membandingkan apakah root sudah lebih kecil daripada childnya.

Jika root masih lebih besar daripada childnya, maka swap root dengan childnya,

Begitu seterusnya sampai data di root adalah angka terkecil.

MAX HEAP

MAX HEAP adalah tree yang memiliki root berupa anggota terbesar dibandingkan denga child-childnya.

Sehingga ketika kita ingin mencari data terbesar, hanya perlu untuk melakukan pop pada data paling atas/ rootnya saja.

Setiap node di Max heap pasti lebih besar dibangdingkan dengan childnya.

Elemen terkecil di dalam Max heap terdapat pada salah satu leaf node.

Untuk memudahkan penulisan code Min heap cukup gunakan array.

Gambar diatas merupakan salahsatu contoh Max heap yang benar.

INSERT PADA MAX HEAP

Contoh push angka 10,20,30,40,15,35.45

Dalam memasukkan data ke dalam Max heap, yang perlu kita lakukan adalah

Selalu memeriksa apakah node yang di push sudah lebih kecil dibandingkan parentnya.

Apabila node yang di push lebih besar daripada parentnya, maka swap posisi node tersebut dengan parentnya.

Begitu seterusnya sampai rootnya merupakan data terbesar.

DELETE PADA MAX HEAP

apabila yang ingin dihapus adalah rootnya maka yang perlu dilakukan adalah

Menggantikan root dengan menggunakan node paling terakhir dari tree.

Membandingkan apakah root sudah lebih besar daripada childnya.

Jika root masih lebih kecil daripada childnya, maka swap root dengan childnya,

Begitu seterusnya sampai data di root adalah angka teresar.

MIN MAX HEAP

Merupakan heap yang memiliki kondisi yang berbeda beda di setiap levelnya, dimana paling atas atau rootnya adalah min, baris ke dua adalah max, ke 3 adalah min, dan seterusnya.

Contoh:

untuk insert dan deletion di dalam Min Max heap memiliki cara yang sama dengan Min heap dan Max heap, yang membedakan di sini adalah baris yang min level dibandingkan dengan baris yang min level, baris yang max level dibandingkan dengan baris yang max level.

TRIE

Trie merupakan salah satu konsep yang sering diimplementasikan ke dalam auto complete pada search engine google.

Trie digunakan untuk menyimpan associative array sehingga dengan begitu dapat diingat string apasaja yang sering diinput orang.

HASHING

Hashing adalah transformasi dari string menjadi nilai yang biasanya lebih pendek dan biasanya digunakan untuk mengindeks dan mengambil item dalam database karena lebih cepat untuk menemukan item menggunakan kunci hash lebih pendek daripada untuk menemukannya menggunakan nilai asli.

Hashing table adalah tabel (array) di mana kita menyimpan string asli, index dari table adalah hashed key dan valuenya adalah original string.

Contoh hashing table

Red Black Tree 

Tree yang proses insertnya masih sama dengan binary tree

Binary tree yang nodenya memiliki warna,merah dan hitam

Memiliki root yang selalu berwatna hitam

Setiap node yang baru dimasukkan memiliki warna merah

Node externalnya berwarna hitam

Node berwarna merah tidak boleh memiliki child berwarna merah

External node merupakan leaf nodes yang secara fisik sebenarnya external nodes tidak ada.

External node ada untuk membantu mempermudah algoritma RBT.

Warna default external node adalah hitam.

Insertion

Bila node yang dimasukkan ternyata memiliki parent berwarna hitam, maka tidak terjadi violation

Bila node yang dimasukkan memiliki parent berwarna merah, lihatlah uncle dari node tersebut. Apabila unclenya juga berwarna merah maka lakukan

Bila node yang dimasukkan memiliki parent berwarna merah, lihatlah uncle dari node tersebut. Apabila unclenya berwarna hitam maka lakukan

single rotation bila

double rotation bila

Deletion

Cara penghapusannya memiliki step yang sama dengan BST namun terdapat beberapa ketentuan tambahan yaitu

Bila a adalah double black node dan memiliki saudara yang berwarna merah maka

Bila a adalah double black node dan memiliki saudara berwarna hitam, maka lihatlah terlebih dahulu anak dari saudara tersebut. Bila berwarna hitam maka

Bila a adalah double black node dan memiliki saudara berwarna hitam, maka lihatlah terlebih dahulu anak daru saudara tersebut. Bila berwarna merah maka

2-3 tree

2-3 tree bukanlah binary tree

ketentuan dalam 2-3 tree:

1. Bila node non-leaf memiliki 2 data maka node tersebut harus mamiliki 3 child

2. Bila node non-leaf memiliki 1 data maka node tersebut harus mamiliki 2 child

Insertion

bila node yang dimasukkan lebih kecil daripada parentnya maka node tersebut harus menjadi left child

bila node yang dimasukkan lebih besar daripada parentnya maka node tersebut harus menjadi right child

bila node yang dimasukkan berada di antara kedua node yang menjadi parentnya maka node tersebut harus menjadi middle child

apabila node telah terisi penut oleh 2 data dan harus dimasuki lagi oleh 1 data yang baru, seperti contou memasukkan angka 75

maka karena angka 80 berada di antara 75 dan 90, sehingga angka 80 harus dinaikkan ke atas, masuk ke dalam node yang telah berisi data 70

Sedangkan 75 dan 90 masing2 membentuk node baru yang berisikan oleh 1 data

(setiap ada 3 data memenuhi 1 node, 1 data yang bread di tengah dinaikkan ke atas, sedangkan 2 data lainnya masing2 membentuk node baru)

Deletion

Untuk deletion di dalam 2-3 tree boleh menggunakan cara apa saja asalkan masih tetap memenuhi persyaratan persaratan 2-3 tree seperti yang tertera di atas

Contoh delete 50 pada

Dapat dilakukan dengan mengganti angka 50 dengan menggunakan anak kiri yang memiliki angka paling besar (40) ataupun anak kanan yang memiliki angka paling kecil (60)

Setelah itu node yang berisikan data 20 dan 30 hanya memiliki 2 child, agar memenuhi start 2-3 tree yang berlaku maka salah satu dari mereka harus turun menjadi child (b0leh 20 maupun 30).

Bila yang diturunkan ialah 20 maka 20 harus berada di camping kanan angla 15 agar memenuhi persyaratan yang berlaku.

• Binary search tree adalah Tree yang akan lebih memduahkan dalam mencari sebuah data yang diinginkan, karena BST memiliki child kiri yang lebih kecil daripada parentnya sedangkan child kanan lebih besar daripada parentnya.

• Sedangkan AVL tree adalah tree yang merupakan Binary Search Tree yang di buat balanced.

Di dalam AVL tree akan terdapat:

• Height node yang dimulai dari 1
• Balanced factor yang merupakan angka yang didapat dari hasil pengurangan child kiri dikurang dengan child kanan
• Dimana balanced factor dari setiap node haruslah “0” atau “1”, bila melebihi angka “1” berarti terjadi violation dan tree harus dibuat balance agar menjadi AVL tree yang baik dan benar

Dimana angka yang berwarna hitam ialah height sedangkan angka yang berwarna merah adalah balanced factornya.

INSERTION

Aturan insert di dalam AVL tree sama saja dengan BST namun yang membedakan ialah, setiap kali kita selesai memasukkan angka, yang harus dilakukan adalah menghitung balanced factornya untuk menentukan apakah tree sudah balance atau tidak.

• Apabila terjadi violation berarti tree tersebut belumlah balance.

Untuk menyeimbangkan tree:

• Setelah mendapatkan data mana yang terjadi violation, ambil lah 2 jalur pertama menuju nide yang paling terakhir di insert
• Kemudian akan terjadi 2 kemungkinan yaitu: Apakah itu single rotation atau double rotation
• Bila single rotation, cara menyelesaikannya ialah
• 
• Bila double rotation, cara menyelesaikannya ialah
• 
• Contoh insetion dalam AVL tree

DELETION

Begitu juga dengan delete, caranya masi sama dengan BST hanya saja setiap kita menghapus nodenya, kita harus memeriksa ulang apakah terjadi violation

Contoh delete 50

disini terdeteksi bahwa di angka 55 terjadi violation, dan itu adalah single rotation maka:

kemudian, tidak selesai begitu saja, kita harus memeriksa ulang semua balannced factornya lagi

karena di node angka 50 terjadi violation, langkah yang harus dilakukan ialah mencari 2 buah child yang memiliki height yang paling besar.

Dapat dilihat pada gambar, child tersebut adalah 25 dan 40.

Dengan begitu harus diseimbangkan dengan double rotaion agar treenya balance menjadi

BST (Binary Search Tree)

Di dalam BST, data akan lebih mudah untuk dicari karena semua data telah terurut, berbeda dengan binary tree.

Terdapat 3 operasi di dalam BST yaitu:

1. Insert : push data
2. Search : mencari data
3. Delete : pop data

INSERT

Dalam pushing data, terdapat ketentuan yaitu

edge sebelah kiri untuk angka yang lebih kecil dari induknya

edge sebelah kanan untuk angka yang lebih besardari induknya

contoh push angka: 5,9,2,3,4.

SEARCH

Memiliki konsep yang sama dengan pop

Apabila data yang dicari lebih besar, maka lakukan pemcarian pada edge sebelah kanan dari induknya

Namun sebaliknya bila data yang dicari kebil kecil, lakukan pencarian pada edge sebelah kiri dari induknya.

Contoh:

search 4

DELETE

Pada BST delete dilakukan dengan:

Apabila node yang akan dihapus tidak memiliki anak sama sekali maka node tersebut dapat secara langsung dihilangkan

Bila node yang dihapus merupakan suatu bagian dari sebelah kiri root

Bila memiliki 2 anak maka tempatkan anak yang lebih kecil untuk menggantikan yang telah dihapus

Bila memiliki 1 anak maka child dari node tersebut digunakan untuk mengganikan node yang telah dihapus

Bila node yang dihapus merupakan bagian dari sebelah kanan root

Bila memiliki 2 anak maka tempatkan anak yang lebih besar untuk menggantikan node yang telah dihapus

Bila memiliki 1 anak maka child dari node tersebut digunakan untuk mengganikan node yang telah dihapus

Tree adalah kumpulan dari satu node atau lebih

Root    = node yang berada paling atas dari sebuah tree

Edge    = garis yang menghubungkan induk dengan anak induknya

Leaf     = sebuah node yang tidak memiliki anak (children)

Sibling= node yang memiliki induk yang sama

Degree= level atau tingkatan

Height = degree paling maksimum sebuah node di dalam tree

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

TIPE-TIPE TREE

Perfect             : masing masing node memiliki 2 anak ; jumlah kiri dan kanan seimbang

Complete        : hampir sempurna ;  hanya terdapat beberapa node yang tidak memiliki anak

Skewed           : setiap node hanya memiliki 1 anak

Balance

• Cara menghitung maksimal node yang dimiliki tree berdasarkan heightnya

[2^h+1 -1]

dimana h ialah untuk height da perhitungan height dimulai dari 0.

• Cara menghitung minimal height berdasarkan jumpah node yang dimiliki

² log(n)

dimana n adalah jumlah node

• Cara menghitung maksimal height berdasarkan jumpah node yang dimiliki

n-1

dimana n adalah jumlah node

p=parent

indeks untuk root selalu 0

indeks untuk anak sebelah kiri menggunakan rumus 2p+1

indeks untuk anak sebelah kanan menggunakan rumus 2p+2

untuk mencari indeks parent dari sebuah node menggunakan rumus (p-1)/2

EXPRESSION TREE CONCEPT 

• infix

• prefix

menggunakan konsep (print left right)

selalu dimulai dari print induknya setelah itu,

print anak sebelah kirinya(level 1) (+),

kemudian jika anak sebelah kirinya itu memiliki anak lagi,print lagi anak sebelah kirinya(a),

setelah itu bila sudah tidak memiliki anak, print siblingnya(b)

setelah itu lanjut dengan hal yang sama dilakukan kepada anak sebelah kanan(level 1)(/)

jadi selesaikan terlebih dahulu seluruh edge sebelah kiri jika sudah ter print semua, kembali ke induk kemudian selesaikan edge sebelah kanan, begitu seterusnya.

sehingga menghasilkan *+ab/-cde

• postfix

menggunakan konsep (left right print) dilihat dari degree paling bawah, selalu selesaikan anak sebelah kiri terlebih dahulu kemudian dilanjut dengan anak sebelah kanan barulah naik ke induknya, begitu seterusnya.

sehingga menghasilkan ab+cd-e/*

Push:

• Enstack
• Enqueue

Pop:

• Destack
• Dequeue

STACK

• <LIFO> Last In First Out
• anggota teratas dari sebuah stack dinamakan TOP
• apabila TOP= NULL maka stack dinyatakan kosong

1. push (menambah anggota)

• pada saat melakukan push, dimulai dengan rumus TOP=TOP-1
• dan ketika TOP+1>=MAX maka push akan berhenti dan stack dinyakan penuh

2. pop (menguragni anggota)

• pada saat melakkan pop, digunakan tumus TOP-1
• dan ketika TOP bernilai TOP=-1, maka stack dinyatakan telah kosong

3. Infix,Prefix,dan Postfix

• Infix ialah operasi matematika seperti yang biasa kita kenal

Contoh:1+2   ;   2*3

• Prefix berbeda dengan infix, dimana prefix menggunakan rumus operator operand operand

Contoh: 1+2 menjadi + 1 2   ;   2*3 menjadi * 2 3

• sedangkan Postfix menggunakan rumus operand operand operator

Contoh: 1+2 menjadi 1 2 +   ;   2*3 menjadi 2 3 *

• Komputer akan lebih mudah menyelesaikan operasi matematika postfix dan prefix dibandingkan infix.

DFS (Depth First Search) dan BFS (Breadth First Search)

• DFS=>mencari ke dalam<depth>(Stack)

• BFS=>mencari ke samping(Queue)

QUEUE

• <FIFO> First In First Out
• Rear digunakan untuk menunjukkan anggota yang paling terakhir masuk
• Front digunakan untuk menunjukkan anggota paling depan/yang pertama masuk
• Apabila front=rear maka queue dinyatakan kosong

1. Push

• Pada saat queue kosong, rumusnya adalah Front=Rear=-1
• Dan pada saat rear+1>=maksimal anggota queue, maka push akan berhenti

2. Pop

• Pop akan dilakukan dengan mengurangi anggota
• Dan akan berhenti apabila Front+1>=Rear

Yang membedakan ialah, pop pada Queue dilakukan dari anggota paling awal/depan/angota front, oleh karena itu setelah anggotanya semua di pop dan front bertemu dengan rear, tidak dapat lagi di push, oleh karena itu kita harus menggunakan circular Queue

CIRCULAR QUEUE

Perbedaan Circular Queue dengan Queue ialah terletak pada cara push dan popnya, dimana

1. Push

Push pada Circular Queue akan terus dilakukan dengan menggunakan rumus yang berlaku yakni

(Rear+1)%Max

2. Pop

Sedangkan pop menggunakan rumus

(Front+1)%Max

BIG DATA

Sebuah system teknologi yang diperkenalkan untuk menanggulangi volume dan jenis data yang terus berkembang dan meningkat secara signifikan, mulai dari data yang berupa foto, teks, video, dan lain-lain.

Sementara itu IBM mendefinisikan big data ke dalam tiga istilah yaitu:

1. Volume (ukuran)
2. Variety (jenis)
3. Velocity (kecepatan)

Maka itu big data memiliki definisi sebagai sebuah teknologi yang memungkinkan untuk memproses, menganalisis , menyimpan data yang berukuran sangat besar dan dengan jenis data yang variatif serta cepat dalam proses pertumbuhannya hanya dalam waktu yang relatif lebih singkat.

ARDUINO

Terdiri dari 2 bagian yaitu papan surkuit dan software(IDE) yang berjalan pada komputer, dimana kita dapat mencoba untuk membuat proyek proyek elektronik dengan cara mengupload codingan yang telah kita buat dalam Arduino IDE melalui komputer ke papan sirkuit dengan menggunakan kabel usb.

Untuk kodingannya sendiri tidak terlalu rumit karena merupakan Bahasa c yang disederhanakan kembali. Sehingga Arduino ini banyak digunakan oleh pemula sebagai sarana untuk mengenal dunia robotika.

RASPBERRY PI

Sebuah computer berukuran kecil yang diperkenalkan pertama kali pada bulan februari 2012, dimana komputer ini dapat bekerja layaknya desktop, sehingga berguna untuk mellakukan eksperime eksperimen membuat karya karya kreatif seperti komputer portable, mesin game mini, dan lain lain.

CLOUD

Suatu teknologi dimana internet digunakan sebagai media penyimpanan, dimana data yang ingin kita simpan diupload melalui internet dan yang kemudian data tersebut akan ditempatkan di data center. Teknologi ini sudah banyak digunakan, seperti dropbox, google drive, one drive, dan lain lain.

Berdasarkan jenis layanannya, cloud computing dibagi menjadi:

• Software as a Service (SaaS)
• Platform as a Service (PaaS)
• Infrastructure as a Service (IaaS)

AUGMENTED REALITY

Sebuah teknologi yang dapat membantu kita memproyeksikan benda benda 2 dimensi di dunia nyata menjadi 3 dimensi dalam bentuk maya. Teknologi ini mulai banyak diaplikasikan di kehidupan sekarang dimulai dari game, kartu nama, media pembelajaran dan lain-lain.

Data stuktur ialah sebuah cara penyusunan, penyimpanan dan pengaturan data dalam computer sehingga data dapat digunakan secara efisien.

Struktur data terdiri dari:

1. Static memory allocation (array)
2. Dynamic memory allocation (linier dan non linier)

Contoh struktur data yang biasa digunakan:

Array

Linked list

Queue

Stacks

binary tree

• ARRAY

-bersifat homogen (memilki tipe data yang sama)

-merupakan kumpulan data yang sejenis

-bisa diakses dengan mudah (contoh: nama[1])

-indeksnya dimulai dari nol “0”

-array juga memiliki alamat yang saling bersebelahan

1. Store value di array

-inisialisasi

contoh:  int angka[2]={1,2};

-input value

contoh:

alamat[10];

for (int i=0; i<10; i++)

scanf(“%d”, &alamat[i]);

-assign value

contoh:

int i, arr1[10], arr2[10];

for(i=0; i<10; i++)

arr2[i] = arr1[i];

2. Operasi dalam array

Traversal=>passing nilai

Insertion=>memasukkan nilai ke dalam array

Searching=>mencari dalam alamat array\

Deletion=>menghapus

Merging=>menggabungkan array yang satu dengan yang lainnya

Sorting=>mengurutkan array

3. Pointer(bersaudaraan dengan array)

Dimana kita memerintahkan pointer untuk menunjuk kepada alamat daru suatu array.

Contoh:

Int a;

Int *b;

b=&a;

maka apabila a mengalami perubahan nilai, b juga akan berubah nilainya menikuti a.

*   =single pointer (menunjuk kepada alamat sebuah array)

**  =double pointer yang menunjuk ke pointer

*** =triple pointer yang menunjuk ke double pointer

dan seterusnya.

• LINKED LIST

Merupakan dynamic data struktur, dan setiap elemennya dinamakan node.

Linked list merupakan suatu tipe data yang bersifat acak, berbeda dengan array yang memiliki alamat yang bersebelahan, linked list memiliki alamat yang bersifat berjauhan.

Diilustrasikan melalui gambar diatas, dimana kotak a tidak bias ;angsung mengakses data ke D, namun harus secara bertahap dimana A harus melalui B dan C untuk dapat mengakses ke D.

• QUEUE

Elemen yang pertama kali dimasukkan lah yang merupakan elemenyang pertama kali keluar.

Ketika orang pertama maju, maka front akan berpindah kepada orang ke 2, dan begitulah seterusnya sampai kepada front bertemu dengan rear maka proses tersebut berhenti.

• Circular queue

Memilliki proses yang sama dengan queue biasa namun perbedaannya terletak kepada: circular queue memiliki kelebihan untuk dapat mulai dari awal lagi setelah front bertemu dengan rear, sehgingga proses tidak angsung berhenti ketika front telah bertemu dengan rear.

• Priority queue

Memiliki proses yang sama juga dengan queue biasa, namun yang memiliki priotitas lah yang merupakan elemen yang pertam kali akan masuk.

Diilustrasukan seperti: ketika antrian di rumah sakit sedang sangat panjang, dan salah seorang yang berada di antrian terakhir merupakan ibu2 yang sedang hamil dan perutnya sudah berkontraksi, maka ibu2 tersebut berhak untuk diprioritaskan untuk tidak mengantri lebih lama lagi.

• STACKS

Stacks dapat direspresentasikan sebagai array linier

Terdiri atas lifo dan filo

Dimana

Lifo(Last In First Out)/fifo(First In Last Out)=>yang terakhir masuk lah yang keluar duluan, dapat diilustrasikan sebagai sebuah beton yang ditumpuk, maka tdak mungkinkan untuk mengeluarkan beton paling bawah terlebih daahulu, namun kita harus mengeluarkannya dari yang paling atas.

• BINARY TREES

• BT

Tree yang dimana kita bebas dalam memasukkan angkanya

• BST

Tree dimana angka yang terletak di cabang sebelah kiri haruslah lebih kecil dan yang di sebelah kanan harus lebih besar.

• DATA TYPE

Merupakan tipe tipe data yang terdapat dalam pemrograman seperti

1. Integer:

Byte

Shortint

Integer

Word

Longint

2. Real:

Real

Single

Double

Extended

Comp

3. Char

• ABSTRACT DATA TYPE

Merupakan proses representasi data dan program dalam bentuk sama dengan pengertiannya, dengan menyembunyikan rincian dari implementasi.

Seperti contohnya pada c dan c++ memiliki yang disebut struct dan class.