GRAPH

• Vertex / Vertices / Nodes
• Edges = Garis penghubung antar nodes

2 Jenis graph :

–> Undirected Graph : graph yang edges-nya tidak memiliki panah.

–> Directed Graph : graph yang edges-nya memiliki panah.

Adjacency List Matrix

Adjacency List Matrix adalah salah satu cara untuk mendeskripsikan hubungan dalam graph.

Minimum Spanning Tree (MST)

Minimum Spanning Tree adalah sebuah tree yang merepresentasikan graph dan tidak memiliki loop.

Algoritma Prim

Langkah-langkah Algoritma Prim :

• Buat array dengan nama T.
• Pilih Vertex awal.
• Setiap vertex yg ditunjuk, edge yang terhubung dengannya akan dibuat aktif.
• Bandingkan nilai/value setiap edge yang aktif, cari yang valuenya paling kecil.
• Masukkan node yang memiliki edge aktif ke dalam T.
• Lakukan step 3 sampai 5 selama node T lebih sedikit dari jumlah node yg ada.

Algoritma Kruskal

Langkah-langkah Algoritma Kruskal :

• Buat array dengan nama T.
• Sort/urutkan semua edges menggunakan heap (priority queue).
• Ambil value minimum dari edge.
• Kalau ada yang menghasilkan loop, lanjut ke edge selanjutnya.
• Kalau tidak loop, masukkan edge ke T.
• Lakukan step 3 sampai 5 sampai semua vertex sudah di check.

Shortest Path

Heap

Heap adalah complete binary tree untuk mencari nilai terkecil atau terbesar dari suatu tree.

Ada 3 jenis Heap :

• Min-Heap
• Max-Heap
• Min-Max Heap

Min-Heap

• Setiap node memiliki nilai yang lebih kecil dari nilai anaknya.
• Elemen paling kecil terletak pada Root.
• Elemen paling besar terletak pada salah satu leaf.
• Dapat di implementasikan menggunakan linked list, tetapi lebih mudah menggunakan array.

Contoh Min-Heap

Operasi pada Min-Heap

• Insertion
  • Masukkan elemen baru pada ujung akhir heap.
  • Bandingkan nilai elemen yang dimasukkan dengan parent. Bila nilai node yang baru saja dimasukkan lebih kecil dari parent, Tukar node dengan parent. Lanjutkan proses ini ke atas sampai nilai parent lebih kecil dari nilai node atau node sudah mencapai root.
  • Contoh Insertion Min-Heap

• Deletion
  • Gantilah root dengan elemen terakhir pada heap.
  • Kurangi jumlah elemen pada heap.
  • Bandingkan nilai root dengan nilai left child dan right child. Bila ada nilai anaknya yang lebih kecil dari nilai root, Tukar root dengan anaknya (anak yang nilainya paling kecil). Lanjutkan proses ini ke bawah sampai nilai node lebih kecil dari nilai kedua anaknya atau node sudah mencapai leaf.
  • Contoh Deletion Min-Heap

Max-Heap

• Setiap node memiliki nilai yang lebih besar dari nilai anaknya.
• Elemen paling besar terletak pada Root
• Elemen paling kecil terletak pada salah satu leaf

Min-Max Heap

• Kondisi heap berganti antara minimum dan maximum antar level
• Setiap elemen pada level genap lebih kecil dari anak-anaknya.
• Setiap elemen pada level ganjil lebih besar dari anak-anaknya.
• Elemen paling kecil terletak pada Root.
• Elemen paling besar terletak pada salah satu anak Root.
• Contoh Min-Max Heap

Operasi pada Min-Max Heap

• Insertion
  • jika new node ada di Min level
    • jika parent dari new node lebih kecil, tukar posisi dan lakukan upheapmax dari parent.
    • jika kondisi diatas tidak benar, lakukan UpHeapMin.
    • UpHeapMin :
      • Bandingkan nilai node dengan grand-parent. Bila nilai node lebih kecil, Tukar nilai node dengan grand-parent dan Lanjutkan Upheapmin dari grand-parent.
  • jika new node ada di Max level
    • jika parent dari new node lebih besar, tukar posisi dan lakukan upheapmin dari parent.
    • jika kondisi diatas tidak benar, lakukan UpHeapMax.
    • UpHeapMax :
      • Bandingkan nilai node dengan grand-parent. Bila nilai node lebih besar, Tukar nilai node dengan grand-parent dan Lanjutkan Upheapmax dari grand-parent.
• Deletion
  • Deletion Elemen Terkecil
    • Gantilah root dengan elemen terakhir pada heap.
    • Kurangi jumlah elemen pada heap
    • DownHeapMin dari Root
    • DownHeapMin :
      • M adalah elemen terkecil dari antara anak-anak dan cucu-cucu dari node.
      • Bila M adalah cucu dari node :
        • Jika nilai M lebih kecil dari node, maka :
          • Tukar nilai M dengan node
          • Bila sesudah ditukar nilai m lebih besar dari parent-nya, Tukar nilai M dengan parent.
          • Lanjutkan DownHeapMin dari M
      • Bila M adalah anak dari node :
        • Jika nilai M lebih kecil dari node, Tukar nilai M dengan node.
  • Deletion Elemen Terbesar
    • Gantilah left child atau right child dari root (tergantung mana yang lebih besar) dengan elemen terakhir pada heap.
    • Kurangi jumlah elemen pada heap
    • DownHeapMax dari node tersebut.
    • DownHeapMax :
      • Prosesnya sama dengan Downheapmin, tetapi relational operator-nya dibalik.

Tries

Tries Adalah salah satu konsep struktur data yang digunakan untuk menyimpan string dalam array.

Contoh Tries :

Hashing

Hashing adalah mengubah sebuah string of characters menjadi suatu key yang merepresentasikan string aslinya.

Hashing digunakan untuk index dan mengambil item pada database.

Hash table adalah sebuah tabel dimana kita menyimpan original string. Index dari tabel adalah hashed key, sedangkan value yang disimpan adalah original string.

RED BLACK TREE

Red Black Tree adalah salah satu contoh dari self-balancing binary search tree.

Suatu Binary Search Tree di anggap Red Black Tree jika :

1. Setiap node mempunyai warna, hitam atau merah.
2. Warna default Root adalah hitam
3. Semua external nodes warnanya hitam
4. Node berwarna merah anaknya harus berwarna hitam
   (Tidak boleh ada node merah beranak merah)

Insertion

1. Operasi Insert pada Red Black Tree sama seperti Binary Search Tree.
2. New Node selalu berwarna merah.
3. Jika parent dari node itu bewarna merah, maka terjadi violation.

Contoh :

1.

–> Parent berwarna hitam, tidak terjadi violation.

2. 

–> jika Parent dan Paman dari X berwarna merah, ubah Parent dan Paman menjadi hitam, lalu kakek nya menjadi merah.

3. –> Bila Parent dari X berwarna merah dan Paman dari X berwarna hitam, Maka lakukan Rotasi. Ubah pivot rotasi menjadi hitam dan anak-anaknya menjadi merah.

Singel Rotation

Double Rotation

Deletion

1. Deletion pada Red Black Tree sama seperti deletion pada Binary Search Tree
2. Bila node yang mau dihapus berwarna merah, gantilah dengan anaknya yang pasti berwarna hitam.
3. Bila node yang mau dihapus berwarna hitam & anaknya merah, gantilah dengan anaknya lalu ubah warna anaknya menjadi hitam.
4. Bila node yang mau dihapus dan anaknya berwarna hitam :

Contoh :

1.   –> Bila Sibling berwarna merah, tukar warna Sibling dan Parent, lalu lakukan rotasi pada Parent.
2. –> Bila Sibling berwarna hitam dan keduanya anaknya juga hitam, maka ubah warna Sibling menjadi merah.
3. 

–> Bila Sibling berwarna merah dan ada anaknya yang berwarna merah, maka lakukan rotasi.

2-3 TREE CONCEPT

2-3 tree concept adalah sebuah struktur data dimana setiap node mempunyai 2 anak dan 1 data atau 3 anak dan 2 data.

Syarat-syarat dari 2-3 Tree Concept :

1. Setiap node yang bukan leaf adalah 2-node (1 data dan 2 anak) atau 3-node (2 data dan 3 anak).
2. Semua data disimpan secara berurutan.
3. Semua leaf ada pada level yang sama.

• letakkan data yang ingin di insert ke posisi yang benar (urut).
•  jika leafnya 2 node, maka langsung di insert menjadi 3 node.

• 3. jika leafnya 3 node, maka yang tengah harus naik menjadi parent yang childnya 2 / 3 data.

Deletion

• Carilah data pada leaf untuk menggantikan data yang ingin di hapus.
• Jika leaf itu 3 node, maka hapus saja data itu sehinggal menjadi 2 node.

Delete (23), node berada di leaf dan leafnya 3 node, jadi langsung hapus.

• Jika leaf tersebut adalah 2-node & parent adalah 3-node, ambil satu nilai dari parent.
  – Bila sibling adalah 3-node, push satu nilai sibling ke parent sehingga parent tetap 3-node
  – Bila sibling adalah 2-node, ubah parent menjadi 2-node lalu gabungkan leaf dengan sibling

Delete (50), 40 akan menggantikan 50.

40 naik menggantikan 50, tetapi 30 akan turun bersebelahan dengan 25.

Hasil akhirnya.

www.binus.ac.id

www.skyconnectiva.com

Pada pertemuan ke-6, kelas Data Structure kami menjadi 2 shift, karena kedatangan guest lecturer dari malaysia, yaitu Mr. Selvakumar Manickam.

Ada 2 jenis balanced binary tree yang lebih dikenal, yaitu:

–>AVL Tree

–>Red Black Tree

AVL TREE

AVL merupakan kependekan dari nama penemu AVL Tree, yaitu G.M Adelson-Veleskii dan E.M Landis pada tahun 1962.

Konsep dari AVL Tree ada 4, yaitu:

1. Height dari sub-tree yang kosong adalah 0.
2. Height dari leaf adalah 1.
3. Height dari internal node (node yang ada di bagian dalam tree) adalah height maksimum dari anaknya ditambah 1.
4. Balance factor (selisih dari height sub tree kiri dan height sub tree kanan) tiap node maksimum adalah 1.

Gambar di atas bukan termasuk AVL Tree karena selisih nya 2, sedangkan AVL Tree Maksimal selisih 1

Terdapat 2 operasi pada AVL Tree, Yaitu :

–> Insertion

–> Deletion

Cara Insertion : Menambahkan node, lalu menghitung height dan balance factor tiap node untuk menemukan AVL Violation. jika trees yang sudah di insertion belum balance, harus me-rebalance tree lagi.

Ada 4 kasus yang biasanya terjadi pada saat insertion AVL Tree, yaitu :

–> Kasus 1 : node terdalam terletak pada subtree kiri dari anak kiri T (left-left)

–> Kasus 2 : node terdalam terletak pada subtree kanan dari anak kanan T (right-right)

–> Kasus 3 : node terdalam terletak pada subtree kanan dari anak kiri T (right-left)

–> Kasus 4 : node terdalam terletak pada subtree kiri dari anak kanan T (left-right)

*Kasus 1 dan Kasus 2 adalah singel rotation

*Kasus 3 dan Kasus 4 adalah double rotation

Contoh Kasus 1 :

Contoh Kasus 2 :

Contoh Kasus 3 dan 4 :

Cara Deletion : Node yang telah hapus digantikan oleh node terbesar pada subtree kiri atau node terkecil pada subtree kanan. Jika yang dihapus adalah leaf, maka langsung hapus saja.

Step 1

Step 2

Step 3

Step 4

Pada Shift ke 2, kami di ajarkan oleh Mr. Selvakumar Manickam dari Malaysia, beliau mengajarkan Kami diajarkan banyak tentang AVL Tree, m-ary trees, binary tree dan binary search tree, kompleksitas pada tiap tree kepada kami.

www.binus.ac.id

www.skyconnectiva.com

BINARY SEARCH TREE [ BST ]

BST digunakan untuk mempermudah user dalam mencari data.

BST mempunyari 3 Basic Operation :

Introduction to Tree, Binary Tree And Expression Tree

Tree adalah sebuah data struktur yang terdiri dari kumpulan node.

–> Node teratas disebut root.

–> Node dibawahnya disebut child.

–> Node yang tidak memiliki child disebut leaf.

–> Degree : Total sub-tree dari node yang ada.

–> Height : Maksimum degree dari sebuah tree.

Binary Tree : sebuah data struktur yang maksimum memiliki 2 buah node. Kedua node tersebut bisa dianggap sebagai left dan right child.

Tipe-Tipe Binary Tree :

1. Perfect Binary Tree : Binary Tree yang tiap node mempunyai 2 child dan berada pada level yang sama.

2. Complete Binary Tree : Binary tree yang tiap level terisi oleh node kecuali yang paling kiri dan semua node di buat sekiri mungkin. Perfect Binary Tree adalah sebuah Complete Binary Tree.

3. Skewed Binary Tree : Binary tree yang tiap level hanya mempunyai 1 child.

Properti dari Binary Tree:

• Jumlah maksimal node pada binary tree dari level k adalah 2^K
• Jumlah maksimal node pada binary tree dari height h adalah 2^h+1-1
• Height maksimum suatu binary tree dari node n adalah ²log(n)
• Height minimum suatu binary tree dari node n adalah n-1

Representasi dari Binary Tree menggunakan Array

• Index dari array merepresentasikan atau menunjukan nomor node.
• Index ke-0 merupakan root.
• Index dari Left Child adalah 2p + 1, dimana p = index dari parent.
• Index dari Right Child adalah 2p + 2, dimana p = index dari parent.
• Index dari Parent adalah (p-1)/2.

Representasi dari Binary Tree menggunakan Linked List

Expression Tree :

–> Expression Tree dapat dibuat dari prefix atau postfix dengan proses rekursif.

Konsep dari expression tree:

• Prefix : Print L R
  Contoh : *+abc
• Postfix : L R Print
  Contoh : ab+c*
• Infix : L Print R
  Contoh : (a+b)*c

LINKED LIST IMPLEMENTATION II

Stack –> stack dapat di artikan sebagai sebuah tumpukan. Pada stack diterapkan sistem FILO [ First In Last Out ] jadi sesuatu yang masuk pertama kali akan menjadi yang keluar terakhir.

Queue –> queue dapat di artika sebagai sebuah antrian. Pada queue diterapkan sistem FIFO [ First in First Out ] jadi sesuatu yang masuk pertama kali akan menjadi yang keluar pertama juga, lalu dikenal juga Priority Queue, dimana sesuatu yang masuk pertama belum tentu keluar yang pertama, karena tergantung prioritas.

Lalu ada Infix, Prefix, dan Profix

• Infix : Operator di tulis di tengah operand.
• Prefix : Operator di tulis sebelum operand.
• Postfix : Operator di tulis sesudah operand.
• Contoh :

• Prefix	Infix	Postfix
  * 4 10	4 * 10	4 10 *
  + 5 * 3 4	5 + 3 * 4	5 3 4 * +
  + 4 / * 6 – 5 2 3	4 + 6 * (5 – 2) / 3	4 6 5 2 – * 3 /  +

Depth First Search [ DFS ] : Sebuah algoritma untuk melakukan pencarian dalam tree atau graph. Pencariannya dilakukan dari dalam terlebih dahulu baru ke samping.

Breadth First Search [ BFS ] : Sebuah algoritma untuk melakukan pencarian dalam tree atau graph. Pencariannya dilakukan dari samping terlebih dahulu baru

Pada pertemuan ke-2 ini kami diajar oleh guest lecturer yang di undang oleh BINUS University. Guest Lecturer itu adalah Bapak Bong Defendy. Beliau adalah lulusan Binusian dan beliau juga seorang Technopreneur. Pada pertemuan ke-2 ini Bapak Defendy ini mengajarkan banyak kepada kami, seperti : Big Data, Arduino, Raspberry Pi, LaTex, Cloud, Augmented Reality dan SASS.

berikut pelajaran yang saya dapatkan dari beliau :

1. Big Data : kumpulan dari data-data yang besar ukurannya. Oleh karena itu untuk mengolahnya kita tidak dapat menggunakan cara data tradisional. Dengan adanya Big Data, pengambilan informasi dapat dilakukan dengan mudah serta dapat digunakan untuk menemukan solusi-solusi untuk masalah-masalah yang rumit. Big Data juga menjadi media penyimpanan data  yang tak terbatas. Big Data biasanya digunakan oleh lembaga-lembaga pemerintah / lembaga-lembaga besar.
2. Arduino : Arduino adalah sebuah platform open-source yang terbentuk oleh hardware ( mikro controller ), Bahasa Program dan Integrated Development Environment ( IDE ). Arduino berfungi untuk mentederhanakan proses rangkaian dan pemrograman mikrokontriler.
3. Raspberry Pi : komputer kecil (seukuran kartu kredit) yang harganya bisa dibilang terjangkau, yang diproduksi dengan maksud edukasi. Raspberry Pi memiliki CPU, RAM, chip grafis, port masukan dan keluaran untuk aneka perangkat. Penggunaan  Raspberry Pi sama seperti komputer pada umumnya, tapi untuk dapat menggunakannya diperlukan sebuah monitor pc / tv sebagai layarnya serta dilengkapi oleh port usb untuk keyboard dan mousenya.
4. LaTex : sebuah penyimpanan dokumen / markup untuk software Tex yang digunakan untuk membuat typesetting suatu dokumen, atau membuat formula matematika. LaTeX memungkinkan penggunanya untuk melakukan typesetting serta mencetak hasil kerjanya dalam bentuk tipografi yang terbaik. Sehingga LaTeX paling banyak digunakan oleh para peneliti matematika, ilmuwan, insinyur, dll.
5. Cloud : Sebuah media penyimpanan, dengan Cloud kita dapat menyimpan sebuah data / file dari yang terbesar sampai yang terkecil. Cloud dapat digunakan dengan cara yang gampang, hanya memerlukan koneksi internet. Jika terjadi kehilangan data/file dapat diatasi dengan cara membuat mirror server / server recorvery.
6. Augmented Reality : sebuah teknologi yang memiliki fungsi yaitu menggabungkan benda 2D / 3D ke dalam sebuah lingkungan nyata, lalu memproyeksikan benda-benda maya tersebut dalam waktu nyata. Contoh : IKEA telah menerapkan Augmented Reality, jadi pada calon pembeli dapat melihat gambaran benda yang diinginkan hanya dengan gadget.
7. SASS : Suatu penyampaian aplikasi perangkat lunak dimana konsumen SASS membayar untuk mengakses dan menggunakan aplikasi yang dioperasikan. untuk menggunakan aplikasinya di perlukan koneksi internet.

ARRAY

• Variabel yang mempunyai data yang sama.
• Indeks di array selalu dimulai dari indeks [0].

Operasi yang dapat dilakukan dalam array :

• Traversal.
• Insertion.
• Searching.
• Deletion.
• Merging.
• Sorting.

Pointer

Pointer adalah variabel yang berisi alamat memori dari suatu variabel lain.

Double Pointer adalah Pointer yang berisi alamat pointer lain.

Struktur Data

Struktur Data adalah cara pengaturan, penyimpanan dan penyusunan data di dalam sebuah media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.

Contoh Struktur Data :

• Linked List.
• Array.
• Queue.
• Stack.
• Binary Trees.
• Hash Table.

Struktur adalah tipe data yang ditetapkan oleh user yang dapat menyimpan informasi yang berhubungan, sedangkan array dapat menyimpan hanya entitas dari tipe data yang sama.

Struktur adalah kumpulan dari variabel di bawah satu nama.

Variabel dalam struktur yang dari jenis data yang berbeda dan masing-masing memiliki nama yang digunakan untuk memilih dari struktur.

Linked List adalah suatu kumpulan data dimana urutannya ditentukan oleh suatu pointer.

Perbedaan dari Linked List dan Array.

Array

• Ukurannya selalu tetap.
• Alokasi memori dilakukan pada saat array didefinisikan.
• Pembebasan memori dilakukan pada saat program berhenti.

Linked List

• Ukurannya berubah-ubah disesuaikan dengan kebutuhan.
• Alokasi memori ditentukan pada saat data dibuat.
• Pembebasan memori dilakukan setiap ada penghapusan data.

 Pada tanggal  12 September 2015 adalah hari yang ditunggu-tunggu oleh semua mahasiswa baru jurusan Teknik Informatika. Pada tanggal 12 September 2015 itu ada welcoming party yang diselanggarakan oleh HIMTI. Nama acaranya adalah HTTP [ Himti Togetherness and Top Performance ]. HTTP sendiri bertemakan “SHINE” [ Strengthening Harmony & Inspiring New Experiences ].

Pada acara HTTP kita dapat bersenang-senang dengan mahasiswa SoCS [ School of Computer Science ]. acara HTTP sendiri di mulai pukul 09.00 WIB, tapi bagi yang pergi ke tempat acara HTTP menggunakan bus yang disediakan oleh HIMTI, semuanya harus kumpul pada pukul 06.00 WIB di lobby kampus alam sutra. acara HTTP ini yang di selenggarakan dari pukul 09.00 sampai 18.00 terdiri dari banyak acara, ada Talk Show, Visualisasi, Band Performance, Guest Stars dan DJ performance.

Untuk mahasiswa baru SoCS, jangan ragu untuk ikut HTTP yang akan di selenggarakan tahun depan, karena gak bakal nyesel kalo itu acara HTTP yang diadain oleh HIMTI.