Run For Leprosy (Teach For Indonesia)

RUN FOR LEPROSY

a. kesan saya dalam mengikuti acara Run For Leprosy ini adalah senang sekali karena bisa berolahraga sambil charity untuk para penderita penyakit kusta. pesan saya adalah semoga Teach For Indonesia dapat membuat lebih banyak lagi charity event untuk orang - orang yang benar - benar membutuhkan.

b. kusta merupakan penyakit yang menyerang tubuh, kulit hingga tulang, dan penyakit ini dapat menyerang siapa saja yang mengakibatkan cacat. Pengobatannya pun membutuhkan waktu yang lama dan bisa jadi harus menjalani amputasi berat jika tidak segera diobati. Di Indonesia sendiri kusta sudah banyak yang mengalami. Bahkan Indonesia masuk dalam peringkat ke-3 didunia dan peringkat ke-1 di ASEAN dengan jumlah penderita kusta yang banyak.

maka dari itu kita harus mengenali kusta dan apa saja penyebabnya. Penyebab kusta itu sendiri adalah bakteri Mycobacterium leprae yang menyerang lewat udara, masuk ke pernapasan. Bakteri ini biasanya berkembang dengan baik didaerah yang lembab dan banyak menyerang orang – orang yang tinggal didaerah dengan tingkat kebersihan yang rendah, seperti tempat pembuangan sampah, dll. Kusta ini juga dibedakan menjadi 2 yaitu kusta kering dan kusta basah. Gejala kusta kering yaitu munculnya bercak putih, sedangkan pada kusta basah bercaknya berwarna merah.

Kita harus menjaga kebersihan diri dan lingkungan kita untuk mengurangi penyebaran penyakit kusta ini. Kita juga tidak boleh menjauhi para penderita kusta, karena mereka memerlukan kepedulian dari kita, mereka membutuhkan dukungan dari kita untuk melawan penyakit kusta tersebut.

c. saya berkomitmen untuk tidak menjauhi orang - orang yang terkena penyakit kusta.

d. menurut saya sosialisasi yang baik tentang kusta adalah dengan seminar - seminar tentang apa itu kusta, sehingga masyarakat dapat mencegah dari awal.

Leftist Tree, Tries & Hashing

Heap & Deap

Heap

Heap terbagi menjadi 3, yaitu :
- min-heap
- max-heap
- min-max heap

min-heap
dalam min-heap, elemen / node yang terkecil berada di root atau terletak paling atas. dan semakin kebawah semakin besar. itu berarti node yang terbesar berada dileaf, tetapi bisa dileaf yang mana saja.
contoh min-heap:

max-heap

max-heap merupakan kebalikan dari min-heap dimana yang berada di root adalah node paling besar dan makin kebawah makin kecil.

contoh max-heap:

aplikasi heap

contoh aplikasi heap adalah Priority Queue dimana dalam Priority Queue ini terdapat beberapa operasi seperti:

(dalam min-heap)

- find-min : yaitu untuk menemukan nilai terkecil dalam heap tersebut yang pastinya terdapat di root

- insert : tentu saja kita dapat memasukkan elemen / node baru kedalam  heap

- delete-min : karena ini seperti queue maka yang kita delete adalah root atau nilai terkecil dalam heap

(dalam max-heap)

- find-max : untuk menemukan nilai terbesar dalam heap yang pastinya terdapat di root

- insert : memasukkan node baru kedalam heap

- delete-max : menghapus nilai terbesar dalam heap / root

(RBT) Red Black Tree

Red Black Tree merupakan Binary Search Tree yang terdiri dari 2 warna. Sebuah BST dikatakan RBT apabila memenuhi kondisi berikut :

1. setiap node memiliki warna, baik merah atau hitam
2. root adalah hitam secara default / otomatis
3. semua external node adalah hitam
4. jika sebuah node berwarna merah, maka kedua anaknya berwarna hitam. itu berarti tidak ada child merah yang memiliki parent merah
5. setiap node ke external node keturunan memiliki jumlah node hitam yang sama

Terdapat 2 operasi pada RBT yaitu Insert dan Delete

- Insert
insert pada RBT sama seperti pada konsep BST dan setiap node baru berwarna merah. jika parent berwarna hitam maka tidak ada violation dan tinggal insert saja node tersebut, tetapi jika parent berwarna merah maka violation terjadi (sesuai aturan nomor 4).
untuk memperbaiki violation tersebut maka:
  - misalkan:
Q = node baru
P = parentnya
S = sibling P (parent Q)
jika parent tidak memiliki sibling, S  = hitam (external node)
jika S = merah, ganti P dan S menjadi hitam dan parent P menjadi merah
jika S hitam maka lakukan rotasi seperti rotasi pada AVL, lalu ubah pivot rotasi terakhir menjadi hitam dan anaknya menjadi merah.

contoh 1 (node baru X): recolor

 contoh 2 (node baru X): single rotate

 contoh 3 (node baru Y): double rotate

- Delete

delete pada RBT juga sama seperti BST, hanya pada RBT ada beberapa kondisi mengenai warna, yaitu:

   - misalkan:

M = target delete

C = pengganti

jika M = merah, C = merah langsung ganti

jika M = merah, C = hitam langsung ganti

jika M = hitam, C = merah langsung ganti dan recolor C = hitam

jika M = hitam, C = hitam akan menciptakan token double black di posisi C

C = N

S = sibling

Sl = sibling left

Sr = sibling right

P = parent

kondisi jika ada token double black:

- kondisi 1 jika S = merah, SL & SR = hitam

maka reverse color P dan S dan rotate di P , token black tetap ada di N. cek kondisi lagi

- kondisi 2 jika s = hitam, SL & SR = hitam

maka recolor S = red , token black pindah ke P

jika warna P = merah recolor jadi hitam, jika P = hitam maka terjadi double black lagi

- kondisi 3 jika S = hitam , SL / SR = merah

maka rotate di parent (single/double), parent baru mengikuti warna parent lama dan kedua anaknya jadi hitam , lalu token black hilang

nb : jika token double black berada pada node merah, maka node tsb menjadi hitam dan

token double black hilang.

contoh delete:

www.binus.ac.id

www.skyconnectiva.com

Stack & Implementation

Stack
Stack bisa dibilang sebagai array linear karena stack berupa tumpukan. Istilah dalam Stack yaitu LIFO ( Last In First Out) atau FILO (First In Last Out). Contoh dalam kehidupan sehari - hari seperti tumpukan buku atau piring.
Dalam Stack terdapat 2 variabel, yaitu TOP dan MAX.
Top digunakan untuk menunjukkan elemen paling atas dari Stack. sedangkan Max untuk menunjukkan jumlah data dalam Stack.
Jika Top = NULL maka berarti Stack kosong, jika Top = Max - 1 berarti Stack penuh.
Pada Stack, jika menambah data maka Top akan naik, tetapi jika ada hapus data maka Top akan turun.
Beberapa operasi pada Stack :
- is_empty(); = untuk mengecek stack kosong
- is_full(); = untuk mengecek stack penuh
- top(); atau peek(); = untuk kembali ke index top
- push(x); = untuk menambah x pada Top didalam stack
- pop(); = untuk menghapus data dari Top dalam stack

Representasi Stack dalam array:

Representasi Stack dalam Linked List:

Dalam Linked Stack, setiap node memiliki 2 bagian:

- 1 bagian untuk menyimpan data

- 1 bagiannya lagi untuk menyimpan alamat dari node selanjutnya

Start pointer pada linked list digunakan sebagai Top, dan semua penambahan serta pengurangan data dilakukan di node yang ditunjuk oleh TOP.

Code untuk Stack: 

Untuk menambah data :

      struct stack *push (struct stack *top, int val){

         struct stack *ptr;

         ptr = (struct stack*) malloc (sizeof(struct stack*));

         ptr -> data = val;

         if (top == NULL){

              top = ptr;

              top -> next = NULL;

         } else {

              ptr -> next = top;

              top = ptr;

         }

         return top;

      }

Untuk menghapus data :

      struct stack *pop (struct stack *top){

         struct stack *ptr;

         ptr = top;

         if (top == NULL){

              printf(“\n STACK UNDERFLOW”);

         } else {

              top = top -> next;

              printf(“\nThe deleted value: %d”, ptr -> data);

              free(ptr);

         }

         return top;

      }

Untuk menampilkan data :

      struct stack *display(struct stack *top){

         struct stack *ptr;

         ptr = top;

         if (top == NULL){

              printf(“\n STACK IS EMPTY”);

         } else {

              while(ptr != NULL){

                  printf(“\n%d”, ptr -> data);

                  ptr = ptr -> next;

              } 

         }

         return top;

      }

Notasi Infix, Prefix, dan Infix

      

Prefix : operator ditulis sebelum operand

Infix : operator ditulis diantara operand

Postfix : operator ditulis setelah operand

Kita butuh notasi Prefix dan Postfix karena notasinya tidak membutuhkan kurung () untuk menghitungnya.

Prefix dan Postfix lebih mudah dihitung / dievaluasi oleh komputer.

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

Depth First Search merupakan algoritma untuk mencari didalam tree atau graph. DFS dimulai dari root hingga kebawah. Breadh First Search juga merupakan algoritma untuk mencari, bedanya dengan DFS, BFS mencari dengan menyebar kiri kekanan, sedangkan DFS mencari lurus hingga kedalaman.

Contoh DFS yang benar :

Contoh BFS :

www.binus.ac.id

www.skyconnectiva.com

Tree

Tree
Tree merupakan kumpulan dari 1 atau lebih node.

Dalam Tree,
- node paling atas disebut Root
- garis yang menghubungkan parent (orang tua) ke child (anak) disebut Edge
- node yang tidak memiliki children (anak) disebut Leaf
- node yang memiliki parent yang sama disebut Sibling
- degree dari node adalah total subtree dari node tersebut
- ketinggian / kedalaman suatu tree merupakan degree maksimum dari node dalam tree
- jika ada edge yang menghubungkan P ke Q maka P disebut Ancestor dari Q, sedangkan Q disebut Descendant dari P

Contoh Tree beserta keterangannya:
             
                

Keterangan :
- Degree dari Tree tersebut adalah 3
- Degree dari B adalah 2
- Height (ketinggian) = 3
- Parent (orang tua) dari C = A
- Children (anak) dari A = B, C, D
- Siblings (saudara) dari E = F
- Ancestor (leluhur) dari F = A, B
- Descendant (keturunan) dari B = E, F
- Root = A
- Leaf = E, F, G

Binary Tree
Binary Tree adalah rooted tree data structure dimana setiap node paling banyak memiliki 2 child.
2 child ini biasanya dibedakan menjadi left child dan right child.
Perbedaan Binary Tree dengan Binary Search Tree :

Binary Tree boleh tidak urut, jadi antara left child, parent dan right child nilainya bebas tidak harus urut.
Tetapi pada Binary Search Tree harus urut, left child harus lebih kecil dari parent dan right child harus lebih besar dari parentnya.

Selain Binary, terdapat juga Unary dan Ternary.

Jenis - jenis Binary Tree:

- Perfect Biinary Tree : Binary Tree dimana setiap level punya node yang sama

- Complete Binary Tree : Binary Tree yang disalah satu levelnya boleh ada yang belum terisi, Perfect Binary Tree merupakan Complete Binary Tree

- Skewed Binary Tree : Binary Tree dimana setiap node memiliki paling banyak 1 child

Binary Tree dalam array:

               

Keterangan:

- Index pada array menunjukkan nomor node

- Index 0 adalah node Root

- Index left child adalah 2p + 1 dimana p adalah index parent

- Index right child adalah 2p + 2

- Index parent adalah (p - 1) / 2

Binary Tree dalam Linked List:

        struct node {

            int data;

            struct node *left;

            struct node *right;

            struct node *parent;

         };

         struct node *root = NULL;

Prefix, Postfix, Infix

                       

Prefix  : *+ab/-cde

Postfix  : ab+cd-e/*

Infix  : (a+b)*((c-d)/e)

Cara mengubah Infix, Prefix dan Postfix.

Infix -> LVR

Prefix -> LRV

Postfix -> VLR

ingat KaBaTaKu (Kali Bagi Tambah Kurang)

contoh:

             2 + a + (b / 2) * 3

maka:

prefix : + 2 + a * / b 2 3

postfix : 2 a b 2 / 3 * + *

tugas :      c / a * 2 + 3 / 12 + 21

prefix :     + / + / c * a 2 3 12 21

postfix :    c a 2  * / 3 + 12 / 21 +

Implementasi Prefix dalam Linked List:

     void prefix(struct tnode *curr) {

        printf( “%c “, curr->chr );

        if ( curr->left  != 0 ) prefix(curr->left);

        if ( curr->right != 0 ) prefix(curr->right);
     }

Postfix :

     void postfix(struct tnode *curr) {

        if ( curr->left  != 0 ) postfix(curr->left);

        if ( curr->right != 0 ) postfix(curr->right);
        printf( “%c“, curr->chr );

     }

Infix:

     void infix(struct tnode *curr) {

        if ( curr->left  != 0 ) infix(curr->left);

        printf( “%c“, curr->chr );

        if ( curr->right != 0 ) infix(curr->right);
     }

www.binus.ac.id

www.skyconnectiva.com

Session 3 (Dosen Tamu) - Algoritma dan Struktur Data

Algoritma
Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria.

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



Array
Array merupakan kumpulan elemen data yang sama karena elemen data tersebut harus memiliki tipe data yang sama (homogen). 

Linked List
Linked List merupakan struktur data yang dinais dimana elemennya dapat ditambah atau dihapus kapan saja karena dijalankan saat run-time. Setiap elemen pada Linked List disebut node (titik). Keuntungan dari Linked List adalah lebih menghemat memori karena elemen yang tersedia sesuai kebutuhan yang ingin dipakai saja.



Perbedaan Array dan Linked List

Dosen Tamu
Pada Senin, 10 Maret 2014 kelas besar Struktur Data 42PGT kedatangan dosen tamu bernama Ongky Pribadi, S.Kom. (CMIIW). Beliau bekerja sebagai programmer freelance dan dulunya lulusan Sistem Informasi. Beliau memilih untuk tidak bekerja dikantoran dan lebih memilih freelance. Saat ini beliau telah membuat banyak aplikasi untuk berbagai perusahaan dan beliau biasanya melakukan maintenance jika diperlukan. Misalnya dengan program yang hanya memerlukan 2 modul bisa berharga 12 juta untuk membuatnya, sedangkan untuk maintenance bisa mencapai 300ribu perdatang. Intinya bekerja dibagian teknologi seperti programmer merupakan pekerjaan yang memberikan gaji yang cukup besar.

www.binus.ac.id
www.skyconnectiva.com