GRAPH

the elements of graph are vertices, edges and degree.

Vertices are the dots that connected by the line, the line that connect vertices is called edge -> many line = edges.

Every vertices have degree, to count degree simply sum all of the edges of a vertices. Example : the degree for A is 2.

There are 2 types of graph, undirected graph and directed graph.

Undirected graph has no direction in the edges, but directed graph have direction in the edges

Minimum Spanning Tree

one of the way to find MST is using kruskal algorithm

1. Create an array with name is T.
2. Sort all the edges using heap (priority queue)
3. Take the most minimum value of the edge
4. If there is loop, continue to the next edge
5. Else add the edge to T
6. Repeat step 3 to 5 until all vertexes are visited

or prim’s algorithm

1. Create an array with name is T.
2. Choose starting vertex.
3. Whenever each vertex is pointed, the edge which connected to it will be signed as active.
4. Compare all the active edges value, find the smallest number.
5. Add the node with smallest active edge to T.
6. Do step 3 to 5 while the node in T is fewer the total node exist.

The other one is to use Dijkstra’s algorithm

the algorithm for Dijkstra is trying every node by developing a route from initial node. then eleminating the biggest cost.

Heap :

Heap adalah jenis tree yang unik. Heap terdiri dari 3 jenis yaitu :

1.Heap max = heap yang rootnya pasti yang terbesar, sehingga node orang tuanya lebih besar dari node anaknya.

2.Heap min = heap yang rootnya pasti yang terkecil, sehingga node orang tuanya lebih kecil dari node anaknya.

3.Heap min-max = heap yang rootnya terkecil, lalu node yang berada di level ganjil selalu maximal dan mode yang berada di level genap selalu minimal

untuk insert pada min-max heap, harus di sesuaikan dengan levelnya, bila mana di level genap ada element max maka harus di tukar dengan element min karena di level genap harusnya hanya ada element min.

TRIES

Tries adalah jenis tree yang digunakan untuk menyimpan array asosiatif yang biasanya berupa string. trie diambil dari kata RETRIEVAL karena tries dapat menemukan kata hanya dengan beberapa huruf depannya saja.

contoh pada tree tries di atas maka jika anda mengetik B-O maka akan muncul 3 pilihan yaitu BOM /BOS / BOR

Hashing

hashing adalah metode untuk menimpan data berdasarkan indexnya sehingga lebih mudah di akses dan di cari, biasanya pada database.

bentuk dari hashing adalah hash tabel

dapat dilihat bahwa atan yang huruf depannya a di simpan di index pertama, lalu index 1 kosong karena itu seharusnya untuk data yang berhuruf depan b.

Red Black Tree

Red black tree adalah jenis tree yang mempunyai warna merah di hitam di node-nodenya.

Termasuk tree yang balance pada saat insertionnya. contohnya sebagai berikut

• Memasukan node seperti binary tree insertion.
• Node yang baru selalu berwarna merah

:

syarat untuk memasukan node baru adalah :

• kalau parentnya black, berarti tidak ada violation.
• jika orang tuanya merah maka terjadi violation, anak merah tidak boleh memiliki orang tua yang merah.

cara untuk memperbaiki tree :

• Node baru disebut q, orang tuanya p, dan saudara dari orang tuanya s (paman dari q). Jika orang tua tidak mempunyai saudara, maka s adalah hitam (node external berwarna hitam).
• Jika s adalah merah, maka ubah p dan s ke warna hitam dan orang tua dari p menjadi merah.
• Jika s adalah hitam, lakukan rotasi single atau double, ubah pivot rotasi terakhir menjadi hitam dan anaknya merah.

2-3 Tree

bukan binary tree, sehingga cabangnya tidak harus 2. suatu node bisa punya 2 anak dan 1 data atau 3 anak dan 2 data.

Lalu insertion yang dilakukan seperti ini :

beberapa syarat insertion antara lain :

• Memasukan data baru data key.
• Lakukan pencarian dimana key akan diletakan, seharusnya ada di leaf.
• Jika leaf adalah  2-node maka taruh saja key baru disana (jadi sekarang 3-node).
• Jika leaf sudah 3-node push data di tengah. Diantara A, B and key (A dan B dalah kedua data yang ada di 3-node) ke orang tuanya dan pisah kedua data sisa tadi menajadi dua 2-node. Betulkan orang tuanya secara recursive .

beberapa Syarat deletion :

• Mengahapus key dari 2-3 tree.
• Seperti pada BST, kita harus menemukanleaf key yang dapat menggatikan key yang mau kita hapus.Jadi penghapusan akan selalu berada di leaf.
• Jika leafnya adalah 3-node, maka hapus keynya sehingga menjadi 2-node.
• Jika leafnya 2-node:
• Jika orang tuanya 3-node, ambil 1 nilai dari sana.Jika saudaranya 3-node, dorong 1 nilai dari saudara ke orang tua sehingga menjadi 3-node lagi. Jika saudaranya 2-node, buat orang tua menjadi 2-node dan gabungkan node yang sekarang dengan saudaranya..
• Jika orang tuanya 2-node. Jika saudaranya 3-node ambil 1 nilai dari orang tuanya dan push 1 nilai dari suadaranya ke orang tuanya. kalau tidak gabungkan orangtuanya dengan saudaranya.
• Betulkan orangtuanya secara rekursif.

Pertemuan 6 : guest lecturer selvakumar manickam

TREE

Tree adalah konsep data dimana data-data dihubungkan oleh suatu garis yang tidak membuat sirkuit. Garis di sebut Edges sedangkan data-data disebut vertices.

Tree juga memiliki beberapa jenis yaitu :

-Binary Tree

-Binary Search Tree

-Balance Tree (AVL)

AVL TREE

AVL berasal dari nama penemunya Georgy Adelson-Velsky and Evgenii Landis .

AVL tree adalah salah statu jenis tree yang berasal dari BST, tetapi memiliki karakteristik khusus yaitu tree yang dihasilkan harus balance (seimbang).

Balance faktor adalah salah satu element untuk menentukan apakah AVL tree itu sudah balance apa belum. Jika nilainya lebih dari 1 maka AVL tree tersebut tidak balance

Jika Tree tidak balance maka akan ada tindakan berupa rotasi 1x atau rotasi 2x.

contoh rotasi 1x

AVL sendiri digunakan untuk mempercepat pencarian dan penghapusan data karena cabang kanan dan kiri tidak berbeda jauh height nya.

Binary Search Tree

Binary Search tree adalah setiap node node memiliki 1 kunci unik sehingga tidak ada kunci yang sama di node yang lain.

kunci yang ada di kiri node lebih kecil dari pada akar node di atasnya, sedangkan yang dikanan lebih besar dari pada node akarnya. seterusnya node node tersebut akan membentuk BST yang lain.

BST : Searching

Konsep dari pencarian element (X) di BST adalah mencari dari akar node. jika element (X) lebih kecil dari node, maka akan otomatis menuju ke kiri, sedangkan jika lebih besar dari node akan terus menuju ke kekanan.

BST : Inserting

Penambahan node pada BST adalah element (X) di komparasi dengan node, jika lebih besar akan menuju ke kanan sedangkan jika lebih kecil akan menuju ke kiri. Hal ini akan dilakukan sampai mendapat node yang kosong.(akan selalu menjadi daun baru).

BST : Deleting

Penghapusan node memiliki beberapa sifat :

• Jika node yang akan dihapus itu daun(leaf) maka akan langsung dihilangkan.
• jika node yang akan dihapus itu memiliki 1 cabang(anak) maka leaf harus di sambugkan ke parent nodenya.
• Jika node yang di hapus memiliki 2 cabang(anak) maka node yang di kanan harus menggantikan node yang ada di atasnya sampai ke tempat dimana node itu dihapus.

Threaded Binary Tree Concept

Suatu Binary Tree yang punya perbedaan dalam menyimpan pointer NULL.

NULL pointer ini bisa di gunakan untuk menunjuk elemen lain, seperti keturunan dari node sebelumnya.

 

 

 

Tree

Tree adalah sebuah rangkaian dari beberapa node. bentuk tree adalah bercabang ke bawah dan akar berada di node paling atas. Tree mempunyai level(kedalaman) dan juga degree. Ada juga node yang disebut sebagai leaf, node tersebut tidak memiliki cabang kebawah.

Binary tree adalah jenis tree yang ditiap node hanya boleh memiliki cabang maksimal 2.

ada beberapa jenis Binary tree, yaitu :

1. Perfect Binary tree
2. Complete Binary Tree
3. Skewed Binary Tree

Bagian-bagian dalam Binary Tree :

maximum node yang bisa ada adalah 2^h+1 – 1.
h adalah ketinggian dari binary tree.

Tinggi minimum dari binary tree dengan n node adalah ²log(n).

Tinggi maximum dari binary tree dengan n node adalah n – 1.

Expression tree

• untuk prefix membaca dari atas ke bawah.

jadi prefixnya adalah : *+ab/-cde

• untuk postfix membaca dari bawah ke atas.

jadi postfixnya adalah : ab+cd-e/*

• untuk infix membaca dari kiri ke kanan.

jadi infixnya adalah : (a+b)*((c-d)/e)

 

 

 

 

Stack

stack merupakan suatu gambaran dimana data disimpan sebagai tumpukan(yang pertama masuk, ada di paling bawah sehingga menjadi yang terakhir keluar). Dalam bahasa inggriss dikenal sebagai FILO (First In Last Out)

Adapun stack dapat digunakan pada array maupun linked list, operasi yang ada pada stack adalah :

• push(x) : menambah x (data) ke dalam tumpukan.
• pop() : menghapus data dari tumpukan paling atas.
• top() : memberi tahu/return value dari data yang ada dipaling atas tumpukan.

Notasi aritmatik ada 3, yaitu :

• Infix : operator ditulis  bersama operand.
• Prefix : operator ditulis sebelum operand.
• Postfix : operator ditulis setelah operand.

Prefix dan Postfix adalah notasi yang umum digunakan untuk komputasi oleh komputer karena infix menggunakan kurung “( )”untuk memprioritaskan perhitungan yang membuat komputer kesulitan.

Depth First Search

Depth First Search(DFS) adalah algoritma untuk mencari data dari tree atau graph. DFS akan mulai dari suatu titik yang kita assign ataupun dari akar suatu tree lalu mencari sampai ke cabang tree terakhir.DFS menggunakan konsep stack.

Queue

Queue adalah antrian, data disimpan dalam bentuk barisan antrian sehingga yang pertama kali masuk adalah yang pertama kali keluar. Istilah yang sering dipakai dalam bahasa pemprogramman adalah FIFO (First In First Out).

Pada Queue juga ada 3 operasi, yaitu :

• push(x) = menambah data (x) ke paling belakang antrian.
• pop() = menghilangkan data paling depan dalam antrian.
• front() = memberi tahu / return value data yang ada di antiran paling depan.

Circular queue adalah jenis antiran yang akan terus berputar, jika antrian sudah mencapai akhir maka akan kembali ke awal.

Breadth First Search

Breadth First Search (BFS) adalah algoritma untuk mencari suatu data dari tree dan graph. BFS mencari dari akar lalu menelusuri tiap data yang ada di tingkatan yang sama.  BFS menggunakan konsep queue.

Big Data

Big data adalah julukan untuk teknologi di bagian pengolahan data. Big data dapat memproses data yang besar (biasanya terabyte) secara cepat dan biasa digunakan untuk mengolah data yang pertambahaannya juga cepat. Selain itu Big data biasanya hanya digunakan untuk mengolah  data terstruktur. Orang yang berprofesi di bagian big data bisa disebut data scientist.

Arduino

Arduino adalah suatu alat pengendali mikro single-board yang bersifat open-source(terbuka untuk umum) yang dihasilkan dari teknologi wiring platform, arduino di rancang untuk memudahkan penggunaan elektronik dalam berbagai bidang. Software yang digunakan memiliki bahasa pemprograman sendiri, tetapi syntaxnya mirip dengan bahasa C. biasanya Arduino menggunakan keluarga mikrokontroler ATMega yang dirilis oleh Atmel.

Raspberry Pi

Raspberry pi adalah sebuah hardware yang ukurannya mirip seperti kartu kredit. hardware ini bertipe single board circuit dan bisa digunakan untuk berbagai hal seperti bermain game ataupun menonton video. OS raspberry pi sifatnya adalah opensource sehingga bisa dimodifikasi sesuai keperluan oleh penggunanya.

Cloud storage

cloud storage adalah teknologi penyimpanan yang bersifat digital, data kita di simpan dalam lokasi “virtual”, yaitu suatu server yang bisa menampung banyak data (dituliskan sebagai cloud). untuk menggunakan cloud yang pasti user memerlukan account dan koneksi internet, beserta gadget yang memungkinkan.

LaTeX

LaTeX adalah singkatan dari Lamport TeX, yaitu sebuah software yang bertipe word processor dan juga bisa digunakan untuk membuat formula matematika. LaTeX memungkinkan penggunanya untuk mencetak sesuai dengan tipografi yang mereka inginkan dan umumnya digunakan oleh orang-orang profesional.

Data :

• Array

– Sifatnya static.

– Data yang ditampung homogen.

–  Index dimulai dari 0.

– Dapat di akses melalui indexnya.

– Disimpan dalam suatu barisan memori(berderet)

 

• Linked List

-sifatnya dynamic.

-Data yang ditampung bisa heterogen.

-posisinya di memori tidak pasti.

-Aksesnya harus dari head.

• how to store array value :

-initialization : int arr[3] = {1,2,3};

-input : -> pakai scanf

-Assign : -> pakai ‘=’

 

 

Linked List

• Pointer :

-menunjuk ke alamat.

contoh pointer :

int x ; int *px ;

px = &x; \\px simpen alamat x

• Jenis Queue

-Normal queue : Antrian biasa, FIFO(First In First Out).

-Circular Queue : Antrian bisa kembali ke awal bila sudah habis.

-Priority Queue : Antrian di atur berdasarkan prioritas.

Linked List impelementation

• Single linked list : insert

head = element pertama yang menunjuk ke node yang lain

penambahan linked list bisa di tambahkan setelah head, di bagian tengah atau paling terkahir.

• Single linked list : delete

menghapus suatu node, lalu menghubungkan kembali rangkaian yang putus

• circular single linked list : node terakhir menunjuk ke node pertama, tidak ada node yang menyimpan NULL di listnya.

• Doubly linked list : insert , bisa memasukan dimana saja antara head – tail
• Doubly Linked list : delete

-Node yang di hapus harus yang berada di Linked List.

 

-Node yang di hapus bukan head atau tail.

 

 

AO adalah masa yang kurang lebih di sebut kuliah percobaan, Mahasiswa baru di berikan materi selayaknya apa yang akan di pelajari di jurusan yang akan di tempuh pada tanggal 21 september mendatang.  Pada masa AO ini sudah boleh menggunakan pakaian bebas, ya tapi tetap sopan seperti pakai sepatu(yang tertutup), pake celana panjang, kalo buat baju ya jangan yang kutung(seperti kaos kutang gtu).

AO ini tujuannya supaya nanti mahasiswa tidak “stress” pada saat kuliah, ya supaya bener-bener ada gambaran juga ntar kuliah ngapain aja. hari pertama saya tentunya tidak mau telat. ya untungnya sampai hari terakhir AO saya tidak pernah telat :D.

Awal-awal AO lumayan takut sih ketemu dosen yang galak apa killer gtu, kebetulan saya mendapat kelas yang cukup enak, dosennya baik dan ngajarnya enak, Ada juga beberapa teman saya dari kelas GO BAS03 sehingga bisa belajar bareng. Saya kan jurusan IT, di kasih materi programming ya lumayan susah karena saya belum pernah belajar bahasa C. awalnya masih lumayan mudah, buat tulisan-tulisan gtu.. eh sampailah dimana harus membuat bentuk-bentuk seperti kotak, kotak kosong, segitiga… nah itu yang lumayan sulit karena saya kurang paham dengan fungsi for yang sangat di tekankan pada program membuat bentuk-bentuk.

Oiya, pada saat AO tidak semua jadwal saya berisi pelajaran, jadi ada beberapa materi yang menjelaskan fasilitas dan lembaga-lembaga yang ada di binus. Agar mahasiswa tidak binggung saat ada masalah dalam proses perkuliahan. ya beda-beda si tempatnya ada yang di lantai 1,lantai 2,lantai 3, bahkan ada yang kantornya di basement loh.

Saat mulai berkuliah kendala saya adalah lift, ya lift binus memang ada 6, tetapi sangat ramai jadinya kalo dateng siangan dikit saja sudah susah sekali untuk dapat naik lift. berhubung saya ada beberapa jadwal kelas di lantai 13 jadinya kalo saat dapet jadwal itu saya harus datang lebih pagi supaya mendapat lift.Terus udah beberapa hari belajar tentang C di kampus dan bareng temen, Lumayan ngerti lah ya… eh tau-taunya ada ulangan AO……

kisi-kisi yang di berikan oleh dosen adalah kerjain semua latihan yang ada di ppt, ya tapi saya dan teman-teman terlalu fokus dengan soal yang katanya soal tahun lalu, jadinya ya kita banyak bahas tentang soal itu, ternyata tidak ada yang keluarrrr.. :O

Untungnya saya masih lumayan bisa mengerjakan ujian AO tersebut, setelah ujian AO ada kelas mengenai SADC, ada dosen yang keren banget panggilannya Pak sky. dia bisa niruin suara burung yang biasanya lewat kalo lg adegan diem gtu deh di kartun-kartun.