Struktur Data Binary Tree untuk representasi N-ary Tree

Beberapa hari lalu gw mengumpulkan tugas kuliah Algoritma dan Pemrograman (yap, untuk S2). Salah satu bagian dari tugasnya adalah untuk memodelkan sebuah pohon n-er (n-ary tree).  Sebuah pohon n-er adalah seperti yang digambarkan di bawah.

N-ary tree

Berbeda dengan pohon biner yang setiap simpul memiliki paling banyak 2 simpul anak, maka sebuah simpul pada pohon di atas dapat memiliki simpul anak yang jumlahnya tidak tentu. Karena jumlah anaknya tidak dapat ditentukan maka representasi larik statis untuk mencatat setiap anak dari sebuah simpul bukan lah merupakan pilihan yang baik, apalagi menggunakan larik 2 dimensi yang berisi matriks ketetanggaan (yang jelas untuk masalah representasi pohon akan memakan banyak sekali ruang). Yang jelas pilihan yang cukup masuk akal adalah menggunakan senarai dinamis.

N-ary tree dengan list

Ilustrasinya dapat dilihat di gambar atas. Setiap simpul akan memiliki sebuah senarai yang akan mencatat simpul-simpul anak. Karena simpul-simpul anak dapat bertambah maka akan sangat nyaman menggunakan senarai.

Tapi karena tugasnya diwajibkan menggunakan C, gw merasa agak kecewa karena di saat publikasi tugas mata gw sudah berbinar-binar akan menggunakan fitur senarai generik pada STL. Dengan senarai generik tersebut gw tinggal membuat sebuah struktur simpul yang memiliki sebuah senarai simpul. Rasanya agak malas kalau harus mengkode senarai berkait lagi seperti yang dilakukan saat masih di tahun kedua kuliah sarjana. Apalagi Bu Inggriani Liem selalu berpesan bahwa seorang programmer harus selalu bisa menulis kode senarai kapanpun dibutuhkan. LOL.

Untungnya teman sekelompok sudah bersedia membuatkan representasi pohon. Tapi yang cukup menarik, representasi ini merupakan representasi senarai yang sudah sangat disederhanakan. Idenya sangat mirip dengan ide pohon biner.

Pohon biner

Pada pohon biner, sebuah simpul mempunyai dua buah simpul anak: anak kiri dan anak kanan. Representasi ini dimodifikasi sehingga dapat merepresentasikan pohon n-ary. Anak kiri akan dianggap sebagai simpul anak sedangkan anak kanan dapat dianggap sebagai simpul saudara. Pohon yang ada pada gambar paling atas akan direpresentasikan sebagai berikut.

Pohon n-ary dengan representasi biner

Jika diuraikan sebagai pohon biner maka akan terlihat seperti berikut.

Representasi pohon biner

Menarik juga 🙂

Crash Failure dan Crash Recovery

Crash Failure dan Crash Recovery adalah 2 buah model di dalam bidang sistem terdistribusi. Di dalam crash failure ketika sebuah proses mengalami crash maka proses tersebut tidak akan dapat beroperasi kembali di dalam sistem. Model ini adalah model pertama yang diperkenalkan ketika belajar mengenai algoritma terdistribusi. Akan tetapi di dalam kenyataannya, proses-proses dapat kembali bekerja setelah mengalami crash.

Di dalam model Crash Recovery, sebuah proses miliki dua buah keadaan yakni up dan down. Up adalah keadaan di mana proses sedang beroperasi dan sebaliknya down adalah keadaan di mana proses sedang tidak beroperasi. Perubahan keadaan dari up menjadi down disebut crash dan perubahan sebaliknya disebut recovery. Sebuah proses dikatakan always up jika di dalam melakukan aktivitasnya proses tidak pernah sekalipun mengalami down hingga selesai. Di sisi lain, ada sebuah keadaan yakni unstable jika proses tersebut mengalami crash dan recovery secara berturut-turut dalam jumlah yang sangat banyak. Ketika itu proses dianggap tidak beroperasi dengan baik.

Berbeda pada model Crash Failure, pada Crash Recovery sebuah correct process adalah proses yang pada suatu waktu akan up secara permanen (dalam hal ini dianggap memiliki waktu yang cukup untuk menyelesaikan aktivitasnya). Sedangkan sebuah faulty process adalah proses yang pada suatu waktu akan always down atau unstable.

Di dalam melakukan aktivitasnya sebuah proses akan dilengkap dengan 2 buah tempat penyimpanan: volatile memory dan stable storage. Ketika sebuah proses mengalami crash maka data yang disimpan pada volatile memory akan terhapus sedangkan data yang disimpan pada stable storage akan tetap utuh. Oleh karena itu stable storage ini digunakan untuk mengembalikan state atau data-data yang diperlukan pada saat proses melakukan recovery.

Zhang-Suen Thinning Algorithm

Mungkin gw udah cerita di beberapa post lalu kalau pada semester ini gw mengambil mata kuliah Sistem Rekognisi. Permasalahan yang dihadapi kali ini adalah bagaimana menipiskan ketebalan sebuah gambar pada karakter yang ingin direkognisi. Penipisan ini dilakukan untuk mengambil fitur-fitur penting dari karakter tersebut. Algoritma ini disebut thinning. Keterangan lebih lanjut bisa dibaca di sini.

Algoritma yang gw gunakan di sini adalah algoritma yang dikemukakan oleh Zhang-Suen dalam paper mereka yang berjudul “A Fast Parallel Algorithm For Thinning Digital Pattern“.

Broadcast Specifications

Tulisan ini diambil dari tugas review artikel berjudul “A Modular Approach To Fault-Tolerant Broadcast and Related Problems“. Artikel ini membahas permasalahan broadcast dan consensus pada sistem yang fault tolerant. Permasalahan-permasalahan tersebut diklasifikasikan berdasarkan spesifikasinya ke dalam beberapa kategori mulai dari kategori terlemah Reliable Broadcast dan kombinasi antara beberapa permasalahan broadcast lainnya.  Kemudian artikel ini akan memberikan algoritma solusi untuk setiap permasalahan. Selanjutnya solusi ini akan dideskripsikan secara moduler mulai dari solusi untuk kategori Reliable Broadcast dan membangun solusi untuk kategori yang lebih kuat dengan menggunakan algoritma-algoritma untuk permasalahan yang lebih lemah.

Di mana menaruh session?

Session adalah sebuah pertukaran informasi semi permanen antara dua buah device. Dengan menggunakan session sebuah device terus dapat mengenali sebuah device identik dalam jangka waktu yang tidak terlalu lama dan dapat menyimpan informasi mengenai komunikasi antara kedua device tersebut. Session ini bersifat stateful (meski mungkin ada yang tidak, tapi gw pribadi gak tau contohnya). Sebuah device dapat mengingat apa sih yang terjadi antara device tersebut dengan sebuah device yang lain selama komunikasi berlangsung.

Contoh session adalah TCP session. Pada awal sebuah komunikasi TCP, kedua device akan membuka sebuah socket untuk berkomunikasi. Sebuah TCP session adalah dari awal sebuah device mengirimkan SYN sampai dengan pesan ACK penutupan koneksi tersebut.

Di dalam desain protokol, kita perlu mengetahui state sebuah device. Dengan adanya session, state tersebut dengan mudahnya diketahui selama kedua device masih berada dalam session. Pada contoh di post-post sebelumnya, awal sebuah session dimulai ketika sebuah socket selesai melakukan blocking dan menerima koneksi sampai socket ditutup. Selama sesi ini kedua device bertukar pesan-pesan. Pesan-pesan ini nantinya akan diparsing oleh kedua device berdasarkan protokol yang sudah ditetapkan oleh si desainer protokol.

Akan tetapi ada beberapa protokol yang sifatnya stateless, seperti protokol HTTP. Pada protokol ini, client hanya mengirim sebuah HTTP request dan server mengembalikan sebuah HTTP response. Hal ini dirasa cukup karena pada awalnya HTTP mungkin digunakan untuk static web. Pada penggunaan selanjutnya ada kebutuhan untuk membuat sebuah web sedikit lebih statis. Kemudian diciptakanlah sebuah mekanisme session di atas protokol HTTP.

Pada mekanisme ini, saat server menerima request dari sebuah client, server tersebut akan memeriksa apakah client tersebut sudah berada dalam sebuah session atau belum. Jika belum maka server membangkitkan sebuah hash dan menyimpannya pada basis data. Setelah itu server akan mengembalikan response yang disertai dengan hash tersebut pada header dari response. Selanjutnya si client diwajibkan untuk menyertakan hash tersebut pada header dari request yang dikirim kepada si server. Dengan demikian server dapat mengetahui apakah si client sudah berada pada sebuah session atau belum.

Java Socket Programming: Simultaneous Connections

Salah satu cara mengatasi kemungkinan timeout yang diakibatkan oleh blocking pada postingan sebelumnya adalah dengan menggunakan multithread.

Java Socket Programming: Multiple Connection

Pada post yang lalu, server yang dijalankan hanya bisa memaintain sebuah koneksi kemudian keluar. Cara untuk mengatasinya adalah dengan menggunakan infinite loop.

Java Socket Programming: Simple Client with GUI

Kalau dipost yang ini dan ini, gw udah nyoba client menggunakan Telnet dan Command Line Application, sekarang gw bakal nyoba bikin client dengan GUI.

Jadi ada 3 buah obyek form: textbox, button, sama textarea. Nah pada textbox, gw pengen mengetikkan apa yang ingin gw kirim ke server. Kemudian gw klik button “Kirim”. Di textarea akan keliatan pesan-pesan dari server.

Java Socket Programming: Simple Client

Kalau di post ini kita nyobanya pake Telnet, maka sekarang kita bikin client sederhana untuk berkomunikasi dengan server tersebut.

Java Socket Programming: Server Tebak-Tebakan

Lanjutan dari yang sebelumnya.

Di sini, gw akan mencoba ngebuat sebuah server tebak-tebakan. Server ini akan membangkitkan sebuah angka, mencoba menerima masukkan dari client sebuah angka, dan memeriksa kecocokan angka dari client dengan angka yang sudah dibangkitkan. Gw akan mencoba memperagakan bagaimana sebuah server dapat memegang koneksi dan melakukan komunikasi terus menerus sampai salah satu memutuskan.