7 modules

I think 7 modules is my upper limit. It is a pain. I have to be constantly on alert and I have to consistently finish my assignments/tutorials way before the deadline else they WILL pile up. For example, I just finished the first draft(actually more like third draft) of my presentation due on 5th Nov. I have also finished an assignment due on 3rd Nov (coincidentally my birthday). I also finished my coding assignment for Computer Graphics due on 29th Oct.

Now, I have to finish my tutorial which is to take place on Tuesday instead of Wednesday (public holiday). This is because I have a 6 hours (probably 7 or more actually) practical on Monday. So I'll be having lessons from at least 10am to 6pm. I'll probably be too tired to do my tutorial after I reach home so late at night.

Seriously, there's so many public holidays this semester. It's crazy. They should let make-up classes be E-learningfied instead.

The longest increasing subsequence problem

The problem is defined as follows: given a sequence, we want to find a longest subsequence that is sorted in increasing order.

I've spent some time searching for answers using dynamic programming (a question in my tutorial sparked this), yet I had difficulty finding clear explanations of algorithms listed to solve this particular problem.

I saw the light mostly after reading http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence, so my explanation will be based on that.

1. An obvious solution using the Longest Common Subsequence(LCS) algorithm.
i) Create a copy of A, B and sort it.
ii) Compare A and B using the LCS algorithm.
A longest subsequence of "A" that is sorted must also be part of "B", since sorting A to become B doesn't change the order of that longest subsequence. The longest common subsequence of A and B must also be the longest subsequence that is sorted in A. Suppose, for sake of contradiction, that it's not, then we can add on an element larger than the biggest element in that sequence or smaller than the smallest element in that sequence, and it will be a subsequence that is sorted and common to both A and B, and yet be larger than the longest common subsequence we have found. A contradiction.

2. Making use of recurrence.
q(k) = max(q(j) for 1<= j <=k-1) + 1
where q(k) is the length of the longest increasing subsequence in sequence S of length k.

Basically what this means that we have already found increasing subsequences before k, and now, if S[k] is larger than the largest element in the longest increasing subsequence we have found so far, we can add S[k] to that subsequence and thus increase the length.

3. A O(n lg n) algorithm was provided, but I didn't quite understand it until I saw the C++ code, also provided, and stared very hard at a Wikipedia article. Basically, we create a B which contains the current longest increasing subsequence(LIS) and slowly build on that in every iteration. Note that B is sorted, since it contains the current LIS. Now, we consider the next element, A[i] to add to B. Is A[i] bigger than the largest element in B? If yes, we can just extend B with A[i]. If not, it must be smaller than the largest element in B. So we can just replace an element in B with A[i]. (It is beneficial to replace some element bigger in B with something smaller that retains the sorted order, since this opens up more possibilities for the rest of the iteration.) It doesn't matter that we replace it because we just need to find the length of the LIS. So we can just build on a previous subsequence. If this grows to be bigger than the previous subsequence that we were building, then good! In the end, we will find the length of the longest common subsequence.

It is trivial to get the longest common subsequence instead of just the length. We can use a tracking table to store the predecessors of each element that we add on to a subsequence. I'll leave it up to you as an exercise.

P.S. To be updated with clearer explanations and maybe(?) pictures if I have the time.

Other interesting readings:
Patience sorting game related to longest increasing subsequence

Hiding cables in plain sight

After getting fibre broadband, I've decided that wireless no longer meets my needs. In fact, I had wanted to use an Ethernet cable to link the router to my computer for a very long time, but it was impractical because: 1. I can't just lay the cable on the floor because that would cut my living room in half; 2. I'll have to drill a hole in the wall so that the cable can go into my room. This time I finally decided enough is enough. I got some flat Buffalo Cat5e cable from Cospro at Sim Lim Square (flat so that I can just pass it under my door and not drill any holes) But the cable sprawled across the top of the living room and was unsightly. I was inspired by an old post at Lifehacker.

So I got to work. I first made some origami leaves

 thanks to this awesome tutorial at Bloomize. Some link to origami roses from that post caught my eye, so I decided to make some roses too. At first, I wanted to do the Kawasaki Rose, but a quick glance at the instructions told me that it was too complicated (although it looks damn fking nice). So I followed this video instead.


 I half-followed the video, and I really anyhow folded without regard for the instructions, and it turned out quite nice. In fact I think it looks much better than the yellow rose that I folded following the instructions completely. Go figure.



 Next up I wanted to make some perching bird, and at first I made a bird of paradise which was super cool-looking but too small for my purposes (I wanted to hide the masking tape). So I found some nesting crane at Origami Club which is basically just a variation of the normal crane.




 It took quite some time, but I'm quite pleased with the results. (I was supposed to study my computer graphics...)


Origami leaf with or without veins

This is awesome... I'm making this to hide my wires.

Origami leaf with or without veins