Combination and Permutation

Combinations and permutations are two common operations applied to a collection of elements. There are also formulas to calculate the number of possible combinations or permutations, which sometimes can be leveraged to directly get answers which otherwise may require going through every possible case.

Read More

Binary Tree

One interesting aspect about binary trees is the way to store and represent them. Linked lists provide an intuitive illustration of binary trees, while extra spaces are required for pointers. Arrays seem to enable the most compact representation for binary trees, but the advantage only applies to some cases like complete binary trees.

Read More

Reader-writer Problem

The reader-writer problem is another synchronization problem of accessing a shared resource between two different roles. The only constraint is that when someone is writing, no others are allowed to either read or write. This indicates that at a time there can be only one active writer or multiple active readers.

Read More

Producer-Consumer Problem

The producer-consumer problem is also known as the bounded-buffer problem. It’s about the synchronization between a producer and a consumer who share a bounded buffer. The producer generates and puts items into the buffer, one at a time, and pauses when the buffer is full. The consumer consumes and removes items from the buffer, one at a time, and pauses when the buffer is empty. We can generalize the producer-consumer problem to have multiple producers or consumers.

Read More

Synchronization Primitives

Processors are often utilized effectively by running multiple tasks simultaneously. To guarantee the correct results of concurrent tasks, synchronization is desired across processes that execute those tasks. The fundamental of synchronization relies on the support of hardware, upon which a wide variety of high-level synchronization operations are built on software.

Read More

Social Network Feeds

Social networks play an important role in our daily life. Without physical connections, we are aware of the status of our friends. We are even able to connect with famous persons and learn their life, which was unimaginable before. One key way of connections in social networks is via feeds, where people publish status or information and others who subscribe or follow it would see. With more and more people are connecting virtually, there is a massive growth of feeds and their flow between people. A system to support such function in the global scale is the foundation of modern social networks.

Read More