Moved to melvinzhang.net

WordPress was a decent blogging solution but it has become a bit too bloated for my tastes. It also does not support custom domains without a yearly fee. The cost of domain mapping is ridiculous ($9.97/year) compared to the price of owning a domain ($6.99/year for a .net domain from www.internetbs.net).

Posterous turned on its WordPress import feature today and with that my migration is complete.

This site will no longer be updated. New posts will appear on http://melvinzhang.net.

First post on Posterous!

I’m using this service to as a one stop site for publishing on the
web. The idea of posting via email appeals to me because it can be
easily automated using command line tools. More about that later.

My favorite algorithm

This post originally appeared here on 11/01/09. This is the last in a series of reposts from the NUS SoC blog.

---

Many of the mechanical procedures we learned in primary and secondary school for calculating the result of certain mathematical operations are really just numerical algorithms. Usually we start with the Addition algorithm for finding the sum of two numbers, this is typically followed by the Multiplication algorithm, which uses the Addition algorithm and digit shifting. Often we are just taught the steps, but not the reason why following them will give us the correct answer (correctness) or how the steps were developed in the first place (design).

The problem posted by Chris Henry on the frequency of the mode reminded me of a similar problem, that of finding the majority in a collection of n items. The majority is the item whose frequency is more than n/2. This problem has a very clever but simple solution that only needs only one pass over the data. It was listed by one of its inventors, J Stother Moore, as one of his best ideas. It is also my favorite algorithm.

What is your favorite algorithm?

Using a personal wiki for notes and todos

Originally appeared here on 10/01/09.

Taking notes is an important part of learning something new. I find it extremely useful to jot down the important points while the material is still fresh in your head. I’ve experimented with a number of different note taking mediums in the past and I hope to share with you some of my insights.

Paper notes are easy to write (unless you have a bad handwriting, like me) and draw diagrams. However, organizing the notes afterwards can be a pain. This method works fairly well for module notes as you will usually read them in a sequential fashion and the notes can be written next to the slides. If I’m doing a module summary, which is longer, I will type out the notes.

Sometimes, you might need to do some quick research to solve a small problem, such as figuring out how to configure your smart phone to access the wifi network. After finding the answer on the web, I find it useful to type out a short howto to remind myself how is it done, in case I need to do it again in the future.

The trouble with the above methods is that notes are largely independent of one another and it is difficult to find all the information about a particular topic which may be stored in different files/pieces of paper. A more useful note taking system should allow one to create hyperlinks between different notes and to easily search for specific pieces of information.

A screenshot of TiddlyWiki from WikiMatrix.org

My solution, as you might have guessed from the title, is to use a wiki engine. Unfortunately, most wiki software require a web server and database backend, which is too complicated for me. Realizing the need for a lightweight, portable wiki for personal use, Jeremy Ruston built TiddlyWiki, which is a single HTML file powered by JavaScript. The one I’m using for notes is a derivative known as MPTW, it has a cousin MonkeyGTD which I use for managing projects and todos. You simply store the file on your local machine and open it in a browser. When you save your changes, the JavaScript writes the changes back to the file.

Data driven programming assignments

Originally appeared here on 09/01/09.

I attended a talk by Randall Bryant on Data Intensive Scalable Computing. His focus was on computer systems for processing large amounts of data.

I realized the importance of data driven computations earlier though my experience setting programming assignments. I think it is important to have problems that are realistic; where you want to write the programs in order to see the results. Unfortunately, most of the time we are technique driven. We try to form a task around a specific method. However, most problems usually have a rather trivial solution, therefore we need to impose some unreasonable constraints or increase the size of the problem to some unbelievably large size in order to force the use of specific techniques.

I think the correct approach is to start from the data. There are large amount of interesting data that is available over the web, from movies to tags. In the UNIX workshop I conducted for freshmen orientation 2008, I made use of the SMS corpus from the WING research group to motivate the use of UNIX pipes.

Dealing with large amounts of publicly available real world data gives rise to realistic computational problems where the effect of efficient algorithms become apparent. Computations that takes hours to run using a naive method can be completed in seconds using the correct approach.

From Research to Teaching and Outreach

Originally appeared here on 07/01/09.

In my previous post I talked about research in CS, one of the goals of research is to advance our understanding in a specific area. IMHO, there are at least three different “frontiers” of understanding:

• expertise of other researchers/practitioner in the area (the usual sense of research)
• level of understanding attained by undergraduates in the area (teaching)
• public or layman understanding/appreciation of the area (outreach)

Both teaching and outreach are important to the development of a field because it expands the talent pool and imparts modes of thinking that are peculiar to the area. In recent years, there is push to promote Computational Thinking as a fundamental skill, on equal terms with reading, writing, and arithmetic.

I’ve helped out at the NUS SoC open house booth for the last two years, and a recurring problem is that most folks have no clue as to what we do in Computing. I think the Europeans got it right when they used the term “Informatics” instead of “Computer Science”. As Dijkstra wrote in EWD682, “we don’t call painting ‘brush art’, nor surgery ‘knife science’ ”. Incidentally, Dijkstra is probably one of the earliest bloggers, he started to send his writings to colleagues by regular mail, before the advent of the Internet. Now, you can view his writings at the EWD Archive

I prefer the term “Information Engineering”, which puts the emphasis on the object of our study, information, and away from the tool we use, the computer. Most people tend to have a better sense of what is engineering, it is about building useful things. In computing, we design algorithms and build software to manage/process information.

Do you have some simple way to describe what we do in Computing to the layman? Do share your ideas/suggestions in the comments.

Relevance of research skills

I was asked to give a career talk to graduating secondary school students for my alma mater, Swiss Cottage Secondary School. I offered to talk about careers in IT but was told that it was already taken. I suggested maybe I can talk about a career in research and development instead.

In preparation for this talk, I’d thought I will revise a blog post I wrote for the NUS SoC blog regarding the relevance of research skill.

In a nutshell, computer science research is a systematic study of a specific problem to derive new methods and design of computer systems to solve real world problems.

Most of us have to perform various research related activities at one point or another, whether it is working on an project or doing a literature survey for an essay we have to write. In general, a research project consists of the following components:

1. identify and formulate the problem to be solved (IMHO, the most important step)
2. review of existing work on related problems (to avoid reinventing the wheel)
3. proposal of a new solution (not as hard as it sounds, often a refinement of an existing solutions or a combination of various other solutions)
4. show that your proposed solution indeed solves the problem

Almost all serious projects involved the above steps. That is why research skills such as problem formulation, review of related work and design of experiments to support your claims are important. In particular, formulating the right problem is often the key step towards a solution. To quote the words of Jiddu Krishnamurti, an Indian philosopher, “If we can really understand the problem, the answer will come out of it, because the answer is not separate from the problem”.

Bowling, Badminton and Buffet at Swiss Past Vs Present Games Day

The second annual Swiss Cottage Past vs Present Games Day was held on the 5th September. Initially, I did not feel like attending the event as I could not get anyone from my class to come. The day before the games day, I received an SMS from William (one of alumni committee members from class of 75) asking all committee members to come down and support the games. I realized I shouldn’t avoid the event just because no one else from my class is going, I should just go down and get to know the other alumni and current students.

Bowling@CDANS	Lane where I was playing

The bowling competition was held at CDANS, opposite Swiss Cottage. I was “coerced” into joining the game and was assigned to play alongside two new alumni. I figured they must be from Swiss Bowlers as they had their own carrying bags and bowling balls. We played a total of three games and my scores were: 104, 77, 83.

Badminton@Swiss Hall	Floorball@Quadrangle

I had lunch with a group of alumni at CDANS before walking back to Swiss Cottage for the afternoon games. Due to lack of players, Annie and I joined in the badminton game which was held in the school hall. Since both of us are not familiar with the game, needless to say we were completely trashed by the Swiss girls from the badminton club.

A number of other games where held around Swiss, including basketball, floorball and soccer. In the end, the alumni won three out of the five games that were played that day.

In retrospect, I am glad that I decided to go down for the games day as I really enjoyed myself playing the games. I also got to meet up with Mrs Ellie Koh and Mr Saiffudin, two teachers from when I was at Swiss but have since retired.

Blogging from the command line

This post is composed in the text editor Vim, using the L^AT_EX format and converted to HTML using H^EV^EA. The HTML source is posted on this blog using the blogpost command line tool.

Using such a pipeline, there are several ways to produce mathematical equations. Either using images produced by H^EV^EA, default H^EV^EA rendering or using the L^AT_EX plugin installed in WordPress. The following compares the result produced by each of these three methods.

H^EV^EA image

H^EV^EA translation

∑_i=1ⁿ i = n(n+1)/2

WordPress image

Asymptote: A language for vector graphics

Asymptote is a language for describing vector graphics, with a syntax that is similar to C++ but more mathematically oriented. For example, pairs and triples are directly represented in the language as (x,y) and (x,y,z) respectively.

Recently, I wanted to create a simple illustration for a programming task on stacks. Using Asymptote, I created the following image:

A structured image is similar to a structured program because it can be decomposed into simpler elements that are repeated with slight differences, analogous to the way functions are called with different parameters. In my illustration, the basic component is a labeled box, i.e. a square with a label. Several boxes are arranged vertically to form a stack. Three stacks are arranged side-by-side to illustrate the given input and expected output.

Asymptote code of the above illustration is shown below:

unitsize(1cm);

picture labelbox(string s, pair corner, int width=1, int height=1) {
    picture pict;
    path box = corner--(corner.x+width,corner.y)--
                   (corner.x+width,corner.y+height)--
                   (corner.x,corner.y+height)--cycle;
    draw(pict, box);
    label(pict, s, corner, NE);
    return pict;
}

picture stack(string s, int[] v = {}) {
    picture pict;
    label(pict, s, (0.5,0), S);
    draw(pict, (0,0)--(1,0));
    for (int i = 0; i < v.length; ++i) {
        add(pict, labelbox((string)v[i], (0,i)));
    }
    return pict;
}

picture orig;
add(orig, stack("$s_1$", new int[]{3,4,1,2,5}));
add(orig, shift((2,0)) * stack("$s_2$"));
add(orig, shift((4,0)) * stack("$s_3$"));

picture final;
add(final, stack("$s_1$", new int[]{5,4,3,2,1}));
add(final, shift((2,0)) * stack("$s_2$"));
add(final, shift((4,0)) * stack("$s_3$"));

add(orig);
draw("sort", (5.5,3)--(7,3), N, Arrow);
add(shift((7.5,0)) * final);