This is my story as a proud Binusian!

Diary of Binusian

Category Archives: Data Structures

Data Structure (Pertemuan 8)

Posted on by Posted in Data Structures Leave a comment

HEAP

Heap merupakan sebuah complete binary tree yang memiliki beberapa sifat tertentu.

Min-Heap

  • Data pada node lebih kecil dari data pada anaknya.
  • Node dengan nilai terkecil terletak pada root.
  • Node dengan nilai terbesar terletak pada leaf.
  • Heap dapat diimplementasikan menggunakan linked-list, namun akan lebih mudah bila menggunakan array.
  • Contoh Min-Heap:

Operasi dalam Min-Heap

  • Find-Min
    Mencari data terkecil pada Min-Heap (Root).
  • Insertion
    1. Insert data baru sebagai node terakhir dari heap.
    2. Lakukan Up-Heap
      Bandingkan nilai data yang di-insert dengan parent-nya. Jika lebih kecil dari parent, maka tukar nilainya.
    3. Upheap dihentikan jika nilai parent-nya lebih kecil dari current node atau jika current node adalah root.
  • Deletion
    1. Tukar nilai dari data terakhir dengan root. Root sebagai current node.
    2. Karena data yang ingin dihapus sekarang berada pada leaf, langsung hapus.
    3. Lakukan Down-Heap
      Bandingkan nilai current node dengan kedua anaknya. Jika salah satu anaknya lebih kecil dari current node, tukar posisi. Jika kedua anaknya lebih kecil nilainya dari current node, tukar posisi dengan anak yang nilainya paling kecil.
    4. Down-Heap dihentikan jika current node bernilai lebih kecil dari kedua anaknya atau jika current node adalah leaf.

Max-Heap

  • Merupakan kebalikan dari Min-Heap.
  • Data pada node lebih besar dari data pada anaknya.
  • Node dengan nilai terbesar terletak pada root.
  • Node dengan nilai terkecil terletak pada leaf.
  • Operasi pada Max-Heap hampir sama dengan operasi pada Min-Heap. Yang membedakan hanya konsepnya saja (data terbesar ada pada root, parent lebih besar dari anak).

Min-Max Heap

  • Kondisi pada heap bergantian antara minimum dan maximum antar level.
  • Element pada level genap bernilai lebih kecil dari anaknya (min-level).
  • Element pada level ganjil bernilai lebih besar dari anaknya (max-level).
  • Root memiliki nilai paling kecil dan kedua anaknya memiliki nilai paling besar.
  • Contoh Min-Max Heap:

Operasi pada Min-Max Heap

  • Insertion
    1. Insert data baru sebagai node terakhir dari heap.
    2. Lakukan Upheap
      Proses Upheap pada Min-Max Heap:

      • Jika node baru ada pada Min-Level:
        1. Jika parent dari node baru lebih kecil dari node baru tersebut maka tukar nilai dan upheapmax dari parent.
        2. Selain di atas, upheapmin dari node baru.
      • Jika node baru ada pada Max-Level:
        1. Jika parent dari node baru lebih besar dari node baru tersebut maka tukar nilai dan upheapmin dari parent.
        2. Selain di atas, upheapmax dari node baru.
      • Upheapmin
        1. Bandingkan nilai dari current node dengan nilai dari grand-parent.
        2. Jika nilai dari current node lebih kecil dari parent-nya, maka tukar nilai.
      • Upheapmax
        1. Bandingkan nilai dari current node dengan nilai dari grand-parent.
        2. Jika nilai dari current node lebih besar dari parent-nya, maka tukar nilai.
  • Deletion
    • Deletion dari data terkecil:
      1. Tukar nilai root dengan nilai dari data terakhir pada heap.
      2. Hapus data terakhir.
      3. Downheapmin dari root.
    • Deletion dari data terbesar:
      1. Tukar nilai anak kiri atau anak kanan dari root dengan nilai dari data terakhir pada heap.
      2. Hapus data terakhir.
      3. Downheapmax dari node.
    • Downheapmin
      • m adalah anak dengan nilai terkecil dari current node dan grand-children.
      • Jika m adalah grand-children dari current node, maka:
        • Jika m lebih kecil dari current node, maka:
          1. Tukar nilainya.
          2. Jika m lebih besar dari parent-nya maka tukar nilainya.
          3. Lanjutkan downheapmin dari m.
      • Jika m adalah children dari current node, maka:
        • Jika m lebih kecil dari current node, maka:
          1. Tukar nilainya.
    • Downheapmax
      Kebalikan dari downheapmin.

_______________________________________________________________________

TRIES

Tries merupakan konsep struktur data yang digunakan untuk menyimpan string.

Contoh konsep Tries:

_______________________________________________________________________

HASHING

Pengertian Hashing:

  • Hashing adalah transformasi sebuah string dari beberapa karakter yang lebih singkat atau suatu kunci yang mewakili string aslinya.
  • Hashing digunakan untuk mengambil item dalam database karena lebih cepat untuk menemukan suatu item menggunakan hashed key daripada mencari value aslinya.

Hash Table

  • Merupakan sebuah tabel (array) dimana kita menyimpan string aslinya.
  • Index dari tabel tersebut berupa hashed key sementara nilainya (value) adalah string asli.
  • Contoh Hash Table:

Fungsi dalam Hash:

  • Mid-square
  • Division
  • Folding

Cara meng-handle collision:

  • Linear Probing
    Mencari slot kosong dan menempatkan string di slot kosong tersebut.
  • Chaining
    Menempatkan string pada slot sebagai chained list (linked list).

Data Structure (Pertemuan 7)

Posted on by Posted in Data Structures Leave a comment

RED BLACK TREE

Red Black Tree merupakan salah satu Balanced Binary Search Tree. Konsepnya hampir sama dengan AVL, namun Red Black Tree menggunakan pewarnaan merah atau hitam pada node dan violation ditentukan dari pewarnaan node tersebut.

Syarat dalam Red Black Tree:

  1. Root selalu berwarna hitam.
  2. Node berwarna merah tidak bisa memiliki parent atau child berwarna merah.
  3. Jumlah node hitam ke node eksternal sama.
  4. Apabila insert node baru, node tersebut diberi warna merah.

Operasi dalam Red Black Tree:

  1. Searching
    Proses searching pada Red Black Tree sama dengan proses searching Binary Search Tree.
  2. Insertion
    • Proses insertion sama dengan BST
    • Node yang di-insert diberi warna merah
    • Pastikan tidak ada violation
    • Bila ada violation gunakan langkah berikut:
      • Color Swap
      • Single Rotation
      • Double Rotation
  3. Deletion
    • Proses deletion pada RBT sama dengan deletion pada BST.
    • Anggap node yang ingin dihapus adalah M dan anaknya adalah C.
    • Jika M berwarna merah, maka gantikan M dengan C dan C harus hitam.
    • Jika M berwarna hitam dan C berwarna merah, ganti M dengan C dan ganti warna C menjadi hitam.
    • Jika M dan C berwarna hitam:
      • Ganti M dengan C.
      • Jika sibling berwarna merah, tukar warna sibling dan parent. Lalu lakukan single rotation pada parent.
      • Jika sibling berwarna hitam dan kedua anaknya juga berwarna hitam, maka ubah warna sibling menjadi merah.
      • Jika sibling berwarna merah dan salah satu anaknya berwarna merah, maka lakukan single rotation atau double rotation.

_______________________________________________________________________

2-3 TREE

2-3 Tree bukan merupakan binary tree. 2-3 Tree merupakan struktur data dimana:

  1. Setiap node yang memiliki 2 anak akan memiliki 1 data pada node.
  2. Setiap node yang memiliki 3 anak akan memiliki 2 data pada node.

Syarat pada 2-3 Tree:

  1. Setiap node internal (non leaf) adalah 2-node (1 data dan 2 anak) atau 3-node (2 data dan 3 anak).
  2. Data disimpan secara urut:
    • Pada 2-node, anak kiri lebih kecil dari anak kanan.
    • Pada 3-node, anak kiri lebih kecil dari anak kanan dan anak yang di tengah memiliki nilai yang masuk dalam range parents-nya (nilainya di antara parents-nya).
  3. Semua leaf berada di level yang sama.

Contoh 2-3 Tree:

Operasi pada 2-3 Tree:

  1. Searching
    Konsep searching pada 2-3 Tree sama dengan konsep searching pada BST. Perbedaan hanya pada maksimal jumlah data per node dan maksimal jumlah anak per node.
  2. Insertion
    • Konsep pada 2-3 Tree hampir sama dengan BST. Anak kiri lebih kecil dari anak kanan. Data kiri lebih kecil dari data kanan pada suatu node. Maka, apabila data yang di-insert lebih kecil dari node, penelusuran bergerak ke anak kiri menuju ke leaf. Sedangkan apabila data yang di-insert lebih besar dari node, penelusuran bergerak ke anak kanan menuju ke leaf.
    • Jika leaf merupakan 2-node, maka lakukan insert menjadi 3-node.
    • Jika leaf merupakan 3-node, push data tengah ke parent dan data dari node tersebut dipisahkan menjadi 2-node. Perbaiki parent secara rekursif.
  3. Deletion
    • Sama seperti BST, cari sebuah data pada leaf yang akan menggantikan data yang mau dihapus. Deletion akan selalu terjadi pada leaf.
    • Jika leaf berupa 3-node, maka delete node sehingga menjadi 2-node.
    • Jika leaf berupa 2-node:
      • Jika parent berupa 3-node, ambil 1 value dari parent. Jika sibling berupa 3-node, push 1 value dari sibling-nya ke parent (untuk membuat parent kembali menjadi 3-node). Jika sibling berupa 2-node, ubah parent menjadi 2-node dan gabungkan dengan sibling.
      • Jika parent berupa 2-node dan sibling-nya berupa 3-node, maka ambil 1 value dari parent dan push 1 value dari sibling ke parent. Jika sibling berupa 2-node, maka gabungkan parent dengan sibling.
      • Perbaiki parent secara rekursif.
    • Contoh deletion:



Data Structure (Pertemuan 6)

Posted on by Posted in Data Structures Leave a comment

BALANCED BINARY SEARCH TREE

Balanced Binary Search Tree memiliki anak yang memiliki height seimbang. Balanced Binary Search Tree yang pertama merupakan AVL. AVL berasal dari nama penemunya, yaitu G.M. Adelson-Veleskii dan E.M. Landis di tahun 1962.

Elemen dalam AVL:

  1. Height = MAX(H left, H right) + 1
  2. Balance Factor = (H left – H right)
    Jika hasilnya:
    (-) maka BST berat ke kanan
    (+) maka BST berat ke kiri
    Balance Factor yang ditoleransi dalam AVL adalah 1 dan -1. Apabila lebih dari 1 atau kurang dari -1, maka BST tidak balanced.

Proses balancing dalam AVL:

  1. Single Rotation
    Apabila jalur violation berupa Left-Left (LL) atau Right-Right (RR), maka perlu dilakukan single rotation agar tree menjadi seimbang.
  2. Double Rotation
    Apabila jalur violation berupa Right-Left (RL) atau Left-Right (LR), maka perlu dilakukan rotation agar jalur violation menjadi Left-Left (LL) atau Right-Right (RR). Lalu dilakukan rotation sekali lagi agar tree menjadi seimbang.

Operasi dalam AVL:

  1. Insertion
    Proses insertion sama seperti pada unbalanced BST, namun setiap kali ditemukan violation harus langsung dilakukan proses rotation hingga menjadi Balanced Binary Search Tree.
    Contoh insert: 51, 26, 11, 6, 8, 4, 31

Deletion
Proses deletion sama seperti pada unbalanced BST, namun setiap kali ditemukan violation harus langsung dilakukan proses rotation hingga menjadi Balanced Binary Search Tree.
Contoh:

_______________________________________________________________________

GUEST LECTURE – Selvakumar Manickam

Mr. Manickam adalah seorang dosen dari Universitas Sains Malaysia. Beliau menjelaskan ulang mengenai elemen-elemen dari tree, yaitu parents, child, leaf dan sebagainya. Beliau juga membahas tentang AVL, Data Structure Complexity dan M-ary tree.

Data Structure Complexity:

M-ary Tree

M-ary Tree merupakan sebuah tree yang anaknya berjumlah lebih kecil atau sama dengan M (<=M). Suatu tree dapat disebut m-ary tree apabila setiap vertex memiliki child tidak lebih dari m.
Contoh:

Binary Search Tree

Posted on by Posted in Data Structures Leave a comment

BINARY SEARCH TREE

Binary Search Tree (BST) adalah tree yang terurut serta dapat diproses untuk pengurutan (sorting) dan pencarian (searching).

Operasi pada Binary Search Tree:

  1. find(x) : untuk mencari suatu node atau data (x) pada Binary Search Tree
  2. insert(x) : untuk menambahkan suatu node atau data (x) pada Binary Search Tree
  3. remove(x) : untuk menghapus suatu node atau data (x) pada Binary Search Tree

_______________________________________________________________________

SEARCHING

Proses pencarian data pada Binary Search Tree:

  1. Membandingkan data yang ingin dicari apakah sama dengan Root, lebih kecil dari Root atau lebih besar dari Root.
  2. Jika data sama dengan Root, maka pencarian selesai dan data ditemukan. Jika data lebih kecil dari Root, maka pencarian akan bergeser ke Child kiri dari Root. Jika data lebih besar dari Root, maka pencarian akan bergeser ke Child kanan dari Root.
  3. Proses pencarian terus dilakukan menggunakan konsep lebih kecil (kiri) dan lebih besar (kanan) hingga data ditemukan. Jika pencarian telah sampai di data terakhir dan ternyata data yang ingin dicari nilainya lebih besar dari data terakhir, maka return NULL. Artinya data belum ada.

 

Contoh pencarian data pada Binary Search Tree di atas apabila ingin dicari angka 5:

  1. Bandingkan apakah angka 5 lebih kecil atau lebih besar  dari angka 9 (Root). Karena angka 5 lebih kecil dari angka 9, proses pencarian akan jalan ke child kiri.
  2. Sekarang proses ada di angka 4. Bandingkan apakah angka 5 lebih kecil atau lebih besar  dari angka 4. Karena angka 5 lebih besar dari angka 4, proses pencarian akan jalan ke child kanan.
  3. Sekarang proses ada di angka 6. Bandingkan apakah angka 5 lebih kecil atau lebih besar  dari angka 6. Karena angka 5 lebih kecil dari angka 6, proses pencarian akan jalan ke child kiri.
  4. Sekarang proses ada di angka 5 dan data ditemukan.

_______________________________________________________________________

INSERTION

Proses penambahan data pada Binary Search Tree:

  1. Bandingkan apakah data yang ingin ditambahkan lebih kecil atau lebih besar dari Root.
  2. Apabila lebih kecil, proses akan berjalan ke child kiri. Apabila lebih besar, proses akan berjalan ke child kanan.
  3. Proses terus dilakukan menggunakan konsep lebih kecil (kiri) dan lebih besar (kanan) hingga data terakhir. Apabila data yang ingin dicari bernilai lebih kecil dari data terakhir, maka data baru akan ditambahkan sebagai child kiri dari data terakhir. Apabila data yang ingin dicari bernilai lebih besar dari data terakhir, maka data baru akan ditambahkan sebagai child kanan dari data terakhir.

 

Contoh proses penambahan data pada Binary Search Tree di atas apabila data yang ingin ditambahkan adalah angka 11:

  1. Bandingkan apakah angka 11 lebih kecil atau lebih besar dari angka 6 (Root).
  2. Angka 11 lebih besar dari angka 6, maka proses berjalan ke child kanan.
  3. Bandingkan apakah angka 11 lebih kecil atau lebih besar dari angka 10.
  4. Angka 11 lebih besar dari angka 10, maka proses berjalan ke child kanan.
  5. Bandingkan apakah angka 11 lebih kecil atau lebih besar dari angka 19.
  6. Angka 11 lebih kecil dari angka 19. Karena angka 19 merupakan data terakhir (left child = NULL, right child = NULL), maka angka 11 ditambahkan sebagai child kiri dari angka 19.

_______________________________________________________________________

DELETION

Ada 3 kasus yang perlu diperhatikan dalam proses deletion:

  1. Jika node/data yang ingin dihapus adalah leaf, maka node/data tersebut dapat langsung dihapus.
  2. Jika node/data yang ingin dihapus memiliki 1 child, maka node/data tersebut akan dihapus kemudian child dari node tersebut akan dihubungkan dengan parent dari node tersebut.
  3. Jika node/data yang ingin dihapus memiliki 2 children, maka cari node paling kanan dari child kiri node tersebut. Kemudian hapus node yang ingin dihapus serta gantikan posisinya dengan node paling kanan dari child kiri node tersebut.

Tree, Binary Tree dan Expression Tree

Posted on by Posted in Data Structures Leave a comment

TREE 

Tree adalah kumpulan dari satu node atau lebih.

Beberapa istilah atau konsep dalam tree:

  • Root : Node yang berada di paling atas
  • Parent : Induk dari sebuah node
  • Child / children : Turunan dari sebuah node
  • Edge : Garis yang menghubungkan parent dengan child
  • Leaf : Node yang tidak memiliki children
  • Sibling : Node yang memiliki parent yang sama
  • Degree : Jumlah sub-tree dari sebuah node
  • Height / depth : Degree maksimum dalam sebuah tree
  • Ancestor : Terdiri dari parent node itu sendiri beserta parent dari parent suatu node
  • Descendant : Terdiri dari parent node itu sendiri beserta parent dari parent suatu node

_______________________________________________________________________

BINARY TREE

Binary tree adalah sebuah tree yang tiap node-nya memiliki paling banyak 2 children. Kedua child ini biasanya dibedakan menjadi left child dan right child. 

Tipe dari binary tree:

  • PERFECT Binary Tree, adalah binary tree yang seluruh level-nya memiliki height (depth) yang sama.
  • COMPLETE Binary Tree, adalah binary tree yang seluruh level-nya terisi penuh (kemungkinan terkecuali level terakhir). Semua node berada pada bagian kiri sejauh mungkin (bergantung pada jumlah parents, dsb.). Perfect Binary Tree termasuk Complete Binary Tree.
  • SKEWED Binary Tree, adalah binary tree yang tiap node-nya memiliki paling banyak satu child.
  • BALANCED Binary Tree, adalah binary tree yang terbentuk dimana tidak ada leaf yang lebih jauh dari root dibandingkan dengan leaf yang lain (tidak ada leaf yang lebih jauh atau lebih dekat dari leaf lain).

Properti dari Binary Tree:

  • Jumlah maksimal node pada binary tree dari level k adalah 2<sup>K</sup>
  • Jumlah maksimal node pada binary tree dari height h adalah 2<sup>h+1</sup>-1
  • Height maksimum suatu binary tree dari node n adalah <sup>2</sup>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

 

Implementasi Linked List

Posted on by Posted in Data Structures Leave a comment

STACK

Stack memiliki prinsip LIFO (Last In First Out) atau FILO (First In Last Out), artinya data yang paling terakhir masuk ke dalam stack akan keluar paling pertama atau sebaliknya.

Stack memiliki 2 variabel, yaitu:

  1. TOP yang digunakan untuk menyimpan address dari elemen paling atas pada sebuah stack.
  2. MAX yang digunakan untuk menyimpan jumlah maksimum dari elemen yang dapat ditampung sebuah stack.

TOP selalu dimulai dari NULL. Dalam array, TOP = -1 karena array dimulai dari index ke-0.

  • Jika TOP = NULL, maka stack-nya kosong.
  • Jika TOP = MAX – 1, maka stack-nya penuh.

Operasi dalam stack:

  • push(x) : Menambahkan sebuah item ke atas stack.
  • pop() : Mengeluarkan sebuah item dari atas stack.
  • top() : Menunjukkan item paling atas dari sebuah stack.

_______________________________________________________________________

QUEUE

Queue memiliki prinsip FIFO (First In First Out), artinya data yang paling pertama masuk akan keluar paling pertama. Namun sebuah queue tidak selamanya menggunakan prinsip FIFO. Sebuah queue dapat memiliki sistem prioritas (Priority Queue), artinya data yang memiliki prioritas lebih tinggi dapat keluar lebih awal.

Queue memiliki 2 variabel, yaitu:

  1. Front, untuk menyimpan address data paling depan pada queue.
  2. Back / Rear, untuk menyimpan address data paling belakang pada queue.

Front dan Rear selalu dimulai dari NULL, dalam array Front dan Rear sama dengan -1.

  • Jika Front = Rear = NULL, maka queue-nya kosong.

Operasi dalam queue:

  • push(x) : Menambahkan sebuah item ke belakang queue. Operasi ini disebut juga enqueue.
  • pop() : Mengeluarkan sebuah item dari depan queue. Operasi ini disebut juga dequeue.
  • front() : Menunjukkan item dari queue yang berada di paling depan. Operasi ini disebut juga peek.

Jenis queue:

  1. Queue (menggunakan prinsip First In First Out)
  2. Circular Queue (Queue akan kembali ke data pertama apabila telah mencapai data terakhir)
  3. Priority Queue (Antrian berdasarkan prioritas data)

_______________________________________________________________________

NOTASI ARITMATIKA

Ada 3 notasi aritmatika:

  • Infix (Operator ditulis di antara Operand -> Operand Operator Operand), biasa digunakan.
  • Prefix (Operator ditulis sebelum Operand -> Operator Operand Operand), disebut juga Reverse Polish Notation.
  • Postfix (Operator ditulis setelah Operand -> Operand Operand Operator), disebut juga Polish Notation.

Prefix dan postfix tidak memerlukan kurung (brackets) untuk memprioritaskan operasi perhitungan serta lebih mudah dievaluasi oleh komputer.

Contoh Notasi Huruf:

Contoh Notasi Angka:

_______________________________________________________________________

DFS & BFS

  • Depth First Search (DFS) merupakan suatu algoritma untuk melakukan penelusuran atau pencarian dalam tree atau graph. Proses pencarian ke dalam dulu baru ke samping. DFS menggunakan stack.

Contoh Depth First Search:

Visit Order: A, C, B, E, D

  • Breadth First Search (BFS) merupakan suatu algoritma untuk melakukan penelusuran atau pencarian dalam tree atau graph. Proses pencarian ke samping dulu baru ke dalam. BFS menggunakan queue.

Contoh Breadth First Search:

Visit Order: A, B, C, D, E

Data Structure (Pertemuan 2)

Posted on by Posted in Data Structures Leave a comment

BIG DATA

Teknologi Big Data adalah teknologi yang memungkinkan proses pengolahan data dengan ciri berukuran sangat besar, sangat variatif, sangat cepat pertumbuhannya dan mungkin tidak terstruktur yang perlu diolah khusus dengan teknologi inovatif sehingga mendapatkan informasi yang mendalam dan dapat membantu pengambilan keputusan yang lebih baik.

Proses ini bertujuan agar setiap bisnis, organisasi ataupun individu yang mampu mengolah data tersebut bisa mendapatkan informasi lebih mendalam (insights) yang akan memicu pengambilan keputusan (decision making) dan tindakan (action) bisnis yang mengandalkan insights tersebut, bukan berdasarkan insting semata.

_______________________________________________________________________

ARDUINO

Arduino adalah sebuah platform open source (sumber terbuka) yang digunakan untuk membuat proyek-proyek elektronika. Arduino terdiri dari dua bagian utama yaitu sebuah papan sirkuit fisik (sering disebut juga dengan mikrokontroler) dan sebuah perangkat lunak atau IDE (Integrated Development Environment) yang berjalan pada komputer. Perangkat lunak ini sering disebut Arduino IDE yang digunakan untuk menulis dan meng-upload kode dari komputer ke papan fisik (hardware) Arduino. Ketika membicarakan Arduino maka ada dua hal yang terlintas dalam pikiran para penggunanya, yaitu hardware dan software. Dua bagian ini seakan satu kesatuan utuh yang tidak bisa di pisahkan.

Arduino dapat mengetahui apa yang harus dilakukan dengan menulis kode dalam bahasa pemrograman Arduino dan menggunakan lingkungan pengembangan Arduino, seperti yang telah dijelaskan dalam situs resmi Arduino. (https://www.arduino.cc/)

_______________________________________________________________________

RASPBERRY PI

Raspberry Pi atau yang biasa disebut Raspi merupakan sebuah perangkat komputer yang berukuran sebesar kartu kredit dan dapat disambungkan ke monitor atau televisi serta menggunakan keyboard dan mouse yang standard. Raspi adalah perangkat kecil yang mampu yang memungkinkan orang dari segala usia untuk mengeksplorasi komputasi, dan belajar bagaimana program dalam bahasa seperti Scratch dan Python.

Raspi mampu melakukan segala hal yang dapat dilakukan oleh sebuah desktop computer, mulai dari internet browsing dan memutar high-definition video, hingga membuat speadsheets, mengolah kata, serta bermain games.

_______________________________________________________________________

LATEX

LaTeX adalah bahasa markup atau sistem penyiapan dokumen untuk peranti lunak TeX. Tex merupakan program komputer yang digunakan untuk membuat typesetting suatu dokumen, atau membuat formula matematika. LaTeX memungkinkan penulis/penggunanya untuk melakukan typesetting dan mencetak hasil kerjanya dalam bentuk tipografi yang terbaik.

Keuntungan menggunakan LaTeX:

  1. Memiliki format dokumen yang terstruktur sehingga membuat dokumen terlihat sangat profesional dan sempurna.
  2. Segala jenis formula matematis dapat dituliskan dengan mudah.
  3. List gambar, List tabel, Daftar Pustaka, footnote bahkan daftar isi dapat secara otomatis dibuat oleh program.
  4. LaTeX melatih dan memaksa pengguna untuk membuat dokumen dengan struktur yang baik dan benar, sehingga tidak terjadi kerancuan dalam penulisan.

Kerugian menggunakan LaTeX:

  1. Sangat sulit untuk menuliskan dokumen yang tidak terstruktur.
  2. Memerlukan kecerdasan manusia.

_______________________________________________________________________

CLOUD

Cloud computing adalah jenis komputasi berbasis internet yang menyediakan shared processing resources dan data ke komputer serta perangkat lain sesuai permintaan. Cloud computing memungkinkan akses ke sebuah kumpulan sumber komputasi yang dapat dikonfigurasi.

Cloud Computing adalah suatu paradigma di mana informasi secara permanen tersimpan di server di internet dan tersimpan secara sementara di komputer pengguna (client) termasuk di dalamnya adalah desktop, komputer tablet, notebook, komputer tembok, handheld, sensor-sensor, monitor dan lain-lain.

_______________________________________________________________________

AUGMENTED REALITY

Augmented Reality adalah teknologi yang menggabungkan benda maya dua dimensi dan ataupun tiga dimensi ke dalam sebuah lingkungan nyata tiga dimensi lalu memproyeksikan benda-benda maya tersebut dalam waktu nyata. Tidak seperti realitas maya yang sepenuhnya menggantikan kenyataan, realitas tertambah sekedar menambahkan atau melengkapi kenyataan.

_______________________________________________________________________

SASS

SASS merupakan perluasan dari CSS3, yang menambahkan banyak fitur-fitur baru seperti variabel, mixin, aturan penyarangan, dan lainnya. SASS diterjemahkan menjadi CSS standar menggunakan perangkat lunak command line, atau plugin dari sebuah framework web.

Introduction to Data Structure

Posted on by Posted in Data Structures Leave a comment

A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways.

Data structure could be divided into:

  1. Static Memory Allocation (Homogenous)
  2. Dynamic Memory Allocation (Heterogenous)

Some common examples of data structures include:

  • Arrays
  • Linked lists
  • Queues
  • Stacks
  • Binary trees
  • Hash tables

 

ARRAY

Arrays in C act to store related data under a single variable name with an index, also known as a subscript. It is easiest to think of an array as simply a list or ordered grouping for variables of the same type. As such, arrays often help a programmer organize collections of data efficiently and intuitively.

Characteristics of array:

  • A collection of similar data elements
  • These data elements have the same data type (homogenous)
  • The elements of the array are stored in consecutive memory locations and are referenced by an index
  • Array index starts from zero

Storing array values:

  • Initialize the elements
  • Input values for the elements
  • Assign values for the elements

There are a number of operations that can be performed on arrays. They are:

  • Traversing (It is used to access each data item exactly once so that it can be processed)
  • Insertion (It is used to add a new data item in the given collection of data items)
  • Searching (It is used to find out the location of the data item if it exists in the given collection of data items)
  • Deletion (It is used to delete an existing data item from the given collection of data items)
  • Merging (It is used to combine the data items of two sorted files into single file in the sorted form)
  • Sorting (It is used to sort the data items based on given instructions)

 

POINTER

Pointer is a data type whose value refers to another value stored elsewhere in computer memory using its address. Like any variable or constant, you must declare a pointer before using it to store any variable address.

The two most important operators used with pointer type are:

  • & the address operator
  • * the dereferencing operator

How to use pointers?

There are a few important operations, which we will do with the help of pointers very frequently. (a) We define a pointer variable, (b) assign the address of a variable to a pointer and (c) finally access the value at the address available in the pointer variable. This is done by using unary operator* that returns the value of the variable located at the address specified by its operand. The following example makes use of these operations:

LINKED LIST

A linked list is a linear collection of data elements, called nodes pointing to the next node by means of pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

Following are important terms to understand the concepts of Linked List:

  1. Link − Each Link of a linked list can store a data called an element.
  2. Next − Each Link of a linked list contain a link to next link called Next.
  3. LinkedList − A LinkedList contains the connection link to the first Link called First.

As per above shown illustration, following are the important points to be considered.

  1. LinkedList contains an link element called first.
  2. Each Link carries a data field(s) and a Link Field called next.
  3. Each Link is linked with its next link using its next link.
  4. Last Link carries a Link as null to mark the end of the list.

Types of Linked List:

  1. Simple Linked List − Item Navigation is forward only.
  2. Doubly Linked List − Items can be navigated forward and backward way.
  3. Circular Linked List − Last item contains link of the first element as next and and first element has link to last element as prev.

Basic operations of Linked List:

  1. Insertion − add an element at the beginning of the list.
  2. Deletion − delete an element at the beginning of the list.
  3. Display − displaying complete list.
  4. Search − search an element using given key.
  5. Delete − delete an element using given key.

Linked List vs Array

Array:

  • Linear collection of data elements
  • Store value in consecutive memory locations
  • Can be random in accessing of data

Linked List:

  • Linear collection of nodes
  • Doesn’t store its nodes in consecutive memory locations
  • Can be accessed only in a sequential manner

 

 

QUEUE

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

Basic features of Queue

  1. Like Stack, Queue is also an ordered list of elements of similar data types.
  2. Queue is a FIFO( First in First Out ) structure.
  3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
  4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

Applications of Queue

Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

  1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
  2. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service representative is free.
  3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive, First come first served.

 

STACK

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. Stack is used to store the data in such a way that element inserted into the stack will be removed at last (LIFO / Last In First Out).

There are basically three operations that can be performed on stacks .

  1. inserting an item into a stack (push).
  2. deleting an item from the stack (pop).
  3. displaying the contents of the stack(pip).

 

BINARY TREE

What is binary tree?

  • A data structure which is defined as a collection of elements called the nodes
  • Every node contains a left pointer, a right pointer, and a data element

More tree terminology:

  • The depth of a node is the number of edges from the root to the node.
  • The height of a node is the number of edges from the node to the deepest leaf.
  • The height of a tree is a height of the root.
  • A full binary tree.is a binary tree in which each node has exactly zero or two children.
  • A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

 

DATA TYPE

Data Type is a collection of objects and a set of operations that act on those objects.

For example, the data type int consists of:

  • objects : 0, +1, -1, +2, -2, etc
  • operations : +, -, *, /, %, etc

Example of predefined data types are int, char, float.

 

ABSTRACT DATA TYPE

Abstract Data Type (ADT) is a data type that is organized in such a way that the specification of the objects and the specification of the operations on the objects is separated from the representation of the objects and the implementation of the operations.

C/C++ has a concept called class and struct which assist the programmer in implementing abstract data type.

Example of ADT:

For example, an abstract stack, which is a last-in-first-out structure, could be defined by three operations: push, that inserts a data item onto the stack; pop, that removes a data item from it; and peek or top, that accesses a data item on top of the stack without removal. An abstract queue, which is a first-in-first-out structure, would also have three operations: enqueue, that inserts a data item into the queue; dequeue, that removes the first data item from it; and front, that accesses and serves the first data item in the queue. There would be no way of differentiating these two data types, unless a mathematical constraint is introduced that for a stack specifies that each pop always returns the most recently pushed item that has not been popped yet. When analyzing the efficiency of algorithms that use stacks, one may also specify that all operations take the same time no matter how many data items have been pushed into the stack, and that the stack uses a constant amount of storage for each element.