Sunday, 28 June 2015

Humanity Forgetting Terrible Diseases (& History of Tuberculosis)

Sanatorium for Tuberculosis patients

This blog post was inspired by the recent PBS documentary "The Forgotten Plague" (which concentrates on the history of TB, primarily in the United States).

It seems that recently, numerous diseases that we thought were "virtually wiped out", such as the whooping cough, and even polio, have revived in certain areas of the United States. This is primarily due to parents disallowing their children vaccination, and subsequently, protection from these life-threatening diseases.

One opinion of the cause of this is because humans, even within a generation or two, completely forget the horrible history of these terrible sicknesses.

I'd like to focus on one in particular, that was wide-spread and very common up until only the mid-early 1900s: tuberculosis, or "consumption" back when this disease was still common. The reason why it was called "consumption" was because a classic symptom was weight loss.

Although TB was thought to be hereditary, people also thought that fresh air and going outside in the wilderness could help reduce the symptoms. In fact, although there were many other reasons why people went out into the American West, one major cause was the fact that developers advertised how "being in the wilderness" and "going out West" can cure TB.

In 1882, the bacteria that caused TB was discovered, and was named "tuberculosis bacillus" due to its tuber-like shape. So, when people realized that it was not hereditary, and in fact contagious by being in vicinity with a TB-infected person, many special isolated places sprung up to house infected people, and most of these places were in the wilderness.

These places were called "sanatoriums", the first of which was founded by Edward Trudeau, who was also the American to first verify the fact that TB was in fact caused by a bacteria, by taking an excruciatingly long period of time to make the microscope, to adjust the room temperature to be exactly 36-37 degrees celsius for hours (which was extremely difficult back in the early 1900s).

Trudeau's "sanatorium" had grown in popularity in its name, and as a result, many more sprung up, including in Europe as well. All of these sanatoriums tried to mimic how Trudeau ran his sanatorium: patients needed to be in bed all day, eat enough food to be well, and surprisingly, and sitting outside on the porch for hours (even if it was freezing cold outside).

What Trudeau discovered is basically common sense today: that rest and relaxation helps your immune system fight against foreign bacteria.

Eventually, in 1943, the antibiotic streptomycin was discovered by Albert Schatz in order to effectively combat tuberculosis. Schatz painstakingly spent hours and hours getting samples of dirt from outside, and isolate all of the bacteria until he found one that was effective against TB.

And it's 2015 right now, only 72 years later, and most of us have forgotten about this plague - this forgotten plague. In an interview within the documentary with an elderly man who was still alive to tell us his stories about TB, he actually talked about his experiences within the sanatorium, and how his mom, his dad, and most of his relatives died from it. It was one day in 1943 when he was finally told that there was a cure, and lived to tell the tale due to this miracle antibiotic.

Unfortunately for us millenials, there are now many strains of tuberculosis that are resistant to streptomycin, and currently a combination of different antibiotics are used to treat tuberculosis. Perhaps in the near future, there will be even further resistant tuberculosis strains, and I am a bit scared by that, and of any other harmful bacteria that can develop resistance.

Saturday, 20 June 2015

Knapsack Problem For Dummies

This blog post will be a "knapsack problem explanation to dummies".

I hope this might help others who are also not CS majors, but want to know more about this famous problem (like I did).

The Knapsack Problem
You have an n amount of items. Each has a certain weight, w_i, and a certain cost, c_i. We want to fill up our backpack, that only holds a maximum weight W with these items. While doing so, we must maximize the total cost of the items in the backpack (our optimization goal!). Of course, we cannot exceed the weight W, so we can only fit a limited number of items, which means the maximum number of items in our backpack must be be less or equal to the n amount of items available to us.

There are two "types" of this knapsack problem. The first is the divisible knapsack problem, and the second is the indivisible knapsack problem. The difference between the two is that just one is the knapsack problem I just described, with the additional note that each of the n amount of items can be divided into a fraction of that i'th item, whereas the other one assumes that all n items are indivisible. So, you could think of the divisible knapsack problem as a problem where all the items are fully constructed lego toys, and that in order to truly maximize the lego blocks you can stash in your knapsack, you can of course try to divide each lego toy by ripping it apart to only take the most valuable lego parts.

Divisible Knapsack Problem
This version of the problem assumes that arbitrary fractions of items can be included in the knapsack (like the lego example I used). This problem can be solved using the following algorithm:
  1. Sort all of the items from the one that has the biggest c_i/w_i ratio (the cost per weight ratio) to the least cost per weight ratio. Typically the complexity of this sorting algorithm depends on which sorting algorithm you employ, e.g. merge sort would give you a complexity of O(nlogn).
  2. Loop through the list of items you just sorted in step 1, and as long as the knapsack is not yet full, add that i'th item into the knapsack.
  3. Once you got to the i'th item that CANNOT fit into the knapsack anymore, figure out how much the knapsack needs until it is truly full. For example, your knapsack's total allowable weight might be 5 kg, and from step 2, you have already filled it up to 4 kg. The next i'th item that could not be stored into the knapsack weighs 2 kg. Therefore, you break apart/cut apart that i'th item into halves in this case, and store one of those halves into your knapsack. Your knapsack should now be optimized for the best total cost per weight ratio.
This algorithm can be called a "greedy algorithm". A greedy algorithm is just a term for an algorithm that goes through a set of items, and after comparing some of the items e.g. items A and items B, it never goes back to compare it again. This should be ok in this scenario, unless somehow magically item A becomes a lot more valuable, which could occur in real situations. For example, let's say you were in some online MMO game where each player only has a limited inventory (based on "weight"). In this game, the value of all items change all the time depending on the in-game economy (e.g. lots of players might thought "AWESOME SWORD" was super OP at the time, and the in-market price for that was 1000 in-game currency, but then all of a sudden the MMO updated and now obtaining the "AWESOME SWORD" is a lot easier. What happens? The cost of the "AWESOME SWORD" goes down of course.)

Indivisible Knapsack Problem
Remember that this version of the knapsack problem is essentially the same, except that items must be included into the knapsack in all of its entirety. If the item as a whole does not fit into the knapsack, we cannot "cut it up into pieces" and fit those "pieces" into the knapsack.

This version of the knapsack problem actually makes the problem a bit more difficult.

We could go with a "greedy" approach. In fact, we could potentially use our previous greedy approach, which was to sort the items based on cost per weight, and fill the backpack with the items that had highest cost per weight. However, if you actually tested this with lots of test cases, you will discover that sometimes this approach will not always give you the most optimal solution.

There are other "greedy" approaches as well, including;
  • sorting by cost (not cost per weight!) and filling the knapsack until it is full
  • sorting by weight (from least weight to greatest), and filling the knapsack until it is full
These two may sometimes actually give the optimal result, but as with the cost per weight approach, they do not always give the optimal solution.

So, how do we solve the indivisible knapsack problem optimally every time? There is no greedy approach which is optimal, as none will 100% give an optimal solution.

However, we can use some concepts to help us achieve in finding the algorithm to solve this indivisible knapsack problem. These concepts include backtracking and dynamic programming.

Backtracking is basically just brute forcing (though I am leaving maybe a bit of stuff out for simplification.)

Dynamic programming can be explained better with an example first, and then a more general definition after. Let's take the example of the knapsack problem. The problem definition is pretty general. You have an arbitrary n amount of items, each with an arbitrary cost and an arbitrary weight. We can create a lot of more specific subproblems by purely inserting actual numbers into each of these variables. For example, we can try to solve the knapsack problem with a 5 kg knapsack, with 2 available items: a 5 kg $1 item, and a 2 kg $2 item. By solving many of these more specific problems, and remembering the actual numerical answer for each of these by saving them/caching them, whenever we need to solve the knapsack problem again for those particular specific situations (like the specific one described above), we can just "look up" the answer instead of computing the whole answer again.

Oh and also better still, not only is this caching of answers is efficient in itself, but with each cache of each answer, any future computations can become easier as well. Basically, future computations can rely on the previous cached answers to be even faster to be solved. What I just described is something called memoization.

For example, we all know the recursive solution for a fibonacci function. It's just to return F(n-1) + F(n-2). We can actually improve this using memoization. Each time the user/someone calls this fibonacci function, we cache the actual answer, including its sub-answers for F(n-1) and F(n-2). For example, say we use memoization. The user calls F(135). Then, whenever the function is called again, for maybe even a bigger number e.g. F(264), because we called F(135) the first time, the answer for F(135) is cached, and so are its subsequent sub-fibonacci problems e.g. F(134), F(133), F(132), ... , to F(3). Therefore, when calling F(264), the computer will just figure out what F(135) is in a blink of an eye, and compute all the way up to F(264).

Ok, I just explained a lot, and we will try to incorporate all of these new concepts into the actual solution for the indivisible knapsack problem.

We know that there should be an optimal solution, and that this solution includes some number of items. An easy general subproblem for the indivisible knapsack problem would be whether or not each item is actually part of the "optimal collection of items to be put into the backpack". We then solve all of these sub problems, and from there we can get the "best solution".

If n is in solution: the solution will have the cost of the n'th item in the solution.
Knapsack(n,W) = C_n + Knapsack(n-1, W-w_n)
Where that second term, Knapsack(n-1, W-w_n) is precomputed due to memoization.

If n is not in solution: the solution will not consider the n'th item's cost or weight at all.
Knapsack(n,W) = Knapsack(n-1, W)
Where Knapsack(n-1, W) is precomputed due to memoization.

The full and official solution for the indivisible knapsack problem is:
  1. Create a two-dimensional array with its rows being 0 to n, and its columns being numbers from 0 to W (max weight of the knapsack). Obviously the first column and the first row have values of all 0 because a backpack that holds 0 weight will have a maximum cost solution of 0, and a backpack that can contain a maximum of 0 items will have a maximum cost solution of 0.
  2. For each (i.j)th element in the array, where i is a number between 1 and n and j is a number in between 1 and W
    1. Initialize the (i,j)th solution as just SolMatrix[i-1][j] (which is the previously calculated solution without the i'th item considered, and only items 1 to i-1th items considered.)
    2. Change the (i,j)th solution to SolMatrix[i-1][v-w_i]+ cost_of_ith_item IF:
      1. (weight_of_ith_item ≤ j) AND
      2. (SolMatrix[i-1][j-weight_of_ith_item]+ cost_of_ith_item > SolMatrix[i-1][j]) 
I worry that the algorithm for the above indivisible knapsack problem is a bit hard to understand, from how I typed it up.

If you need any further explanations on the indivisible knapsack problem, please click the following links for more details, as they have helped me tremendously on understanding the concepts explained in this post:

How to Deal with Rejection

I got rejected from a national engineering scholarship recently that was very prestigious. I spent many days trying to finish the arduous application process, only to receive that email that explains "the selection process was very tough", and a few words after, receiving the unfortunate news, "we are sorry to inform you...".

I have to admit that I have a lot of general anxiety about anything and everything I encounter in life, but I try very well to hide my fears and worries. I have low self confidence especially, and constantly try to deal with the thought that "I'm not good enough" in every situation. Because of this, my first thought after receiving the email of rejection was that "I'm not good enough.

I suck.

I'll just give up."

I feel very weak for thinking this way at many times in my life, and for admitting this right now. I have thought this exact same way in numerous other situations earlier in my life. However, I know of plenty of people who get stuck in this kind of mental rut as well whenever they try to aim for success.

I know this seems obvious to probably 99% of you reading this, but what I'm about to say was really an eye-opener for a pessimist like me, and will hopefully be a positive motivation for anyone reading this: that my mindset I exhibited was a terrible way to deal with rejection - that I should change it, as it will never make me improve, and will just hurt me and my confidence more.

After seeking advice from multiple friends, from books, and from articles online, I began to realize that instead of being stuck in a prolonged period of depression after I receive a rejection of some sort, I should instead change my mindset to be more productive and I should be more focused on improvement.

"I got rejected from XXX. My approach was probably wrong and I need to improve more!"

This is the most wise method for whenever a rejection is received, in my opinion. There is nothing wrong with yourself, even if you got rejected. You simply just approached it a bit wrong that didn't work for that specific situation. Instead of moping around, try to see any improvements that you could have easily did in order to improve your chances for success, for any future opportunities (trust me, there will always be future opportunities!)

Don't be afraid of rejection either. If you never get rejected, then that means you aren't trying to get out of your comfort zone, and are not at trying to reach your limits. Try to reach them!

Sunday, 7 June 2015

Tell Your World

To remember the intangible feelings that I hold dear in my heart
I broke free from this life, this somber life that some of you know
I hummed these secret songs for years, but now I want to share one with you…
So spread this news far wide… and let it fly high with soaring birds in the blue clear sky!

It’s all those words to share and bare with others
It’s all those notes to sing and send to others
Each and every link forms a new connection
It echoes far away into the distance...

It’s all those words to share and bare with others
It’s all those notes to sing and send to others
Then all your links combine into a circle
With everyone together “tell your world” it’s everywhere!

The dark encapsulates your room, you're blinded by terrible heartache
But the light that shines right through, those gaps between your fingers, brilliantly
I've caught this little tune, and tapped its beat on top of the window sill
And it'll reverberate... and resonate throughout the air and into the sky!

It’s all those words to fare and bare with others
It’s all those notes to sing and shout to others
Each and every link forms a new connection
It echoes far away into the distance...

It’s all those words to fare and bare with others
It’s all those notes to sing and shout to others
Then all your links combine into a circle
With everyone together “tell this world” it’s everywhere!

Never doubted the days, this song that I played
will heal everyone's sorrows,
Life is such a wondrous journey that some people may lose their footpath on...
Now every moment shakes, with each tapping beat, so our world begins to change,
Tell your world today... about the sounds within our hearts!

It’s all those words to share and bare with others
It’s all those notes to sing and send to others
Each and every person forms a connection
We echo far away into the distance...

It’s all those words to share and bare with others
It’s all those notes to sing and shout to others
Then everyone holds hands in a big circle
With everyone together “tell your world” it’s everywhere!

The tune of these lyrics are to the beat of the Japanese vocaloid song, "Tell Your World" by Hatsune Miku. It is not a direct translation, as I wanted to be more creative. You can find the music video for this song here.

The chorus' lyrics specifically is inspired by Zessei Bijin's English cover. You can find it here. Everything else are 100% my own words.