Spam

My blog has been getting a lot of spam on one particular post that I wrote earlier this year. Here’s some sample spam on my blog. It looks like someone forgot to fill in the words from their spam template and instead posted the entire template by accident, but this makes writing spam look like a fun pastime for a bored teenager.

This template is particularly interested in what blogging service I use and also notes that my blog posts are awesome. Woohoo, external validation via spam!

Uh, although it was pretty fun seeing this, I’ve enabled Akismet’s anti-spam WordPress plugin, but let me know if you have any other anti-spam suggestions (aside from using this template to filter out spam generated from this template).

{
{I have|I’ve} been {surfing|browsing} online more than {three|3|2|4} hours today, yet I never found any interesting article like yours. {It’s|It is} pretty worth enough for me. {In my opinion|Personally|In my view}, if all {webmasters|site owners|website owners|web owners} and bloggers made good content as you did, the {internet|net|web} will be {much more|a lot more} useful than ever before.|
I {couldn’t|could not} {resist|refrain from} commenting. {Very well|Perfectly|Well|Exceptionally well} written!| {I will|I’ll} {right away|immediately} {take hold of|grab|clutch|grasp|seize|snatch} your {rss|rss feed} as I {can not|can’t} {in finding|find|to find} your {email|e-mail} subscription {link|hyperlink} or {newsletter|e-newsletter} service.

More spam…

How to Berkeley, v2

The first 10 seconds is how I feel.

Berkeley should hire a couple software engineers to fix their online interfaces (e.g. for class registration). People have obviously noticed the problem and now there are layers and layers of web pages / services maintained by different organizations / departments that each contain different amounts of information. It’s all very confusing, disorganized, and arduous, and I miss MIT WebSIS. Here is a guide with some simplified steps for paying fees at Berkeley and class registration for EECS graduate classes:

Shortcut for paying bills/fees:

  1. Login to e-bill/e-check. Scroll to the bottom and click “I agree.”
  2. Click “Pay now” and follow instructions from there.

Methodology for class registration:

  1. Browse for possible classes of interest: Look through the relevant listings [CS, EE, CS-next, EE-next]. This just gives you the names of the courses offered this/next semester. To get the description of the classes, you’ll need to follow the links to the general catalog, but even then, they are probably out of date because the process for faculty to update it is arduous. Good luck finding any descriptions for the special seminars (e.g. CS 294). You might have to be on some mailing list at the right time to get these, so try searching your inbox…
  2. Create a schedule of your classes: Go to ScheduleBuilder and start adding your classes of interest. In the first field, type the department (“EE” or “CS”) and in the next field type the number of the course. When you’re done, click “Generate Schedules.” Select “Save as Main Schedule.” Next, view your Saved Schedules. Optionally export the calendar by selecting “Download iCal.” (From there, you can import this into gCalendar, iCal, etc.) Take note of the CCN numbers displayed to the right side of the interface. You’ll need these for the actual registration step.
  3. An alternative to the previous step is to build the schedule in your head and get the CCN numbers straight from [EE Fall, CS Fall] [EE Spring, CS Spring]. Apparently, some of the classes here have a direct link to register a class, but it seems inconsistent.
  4. Finally, login to TeleBEARS to actually register your classes. Be sure to do this outside of its schedule maintenance hours of 6-7am M-F, 6-noon Su, and some Saturdays. I don’t know what this means, but if your appointment has expired, forget about accessing TeleBEARS at normal hours. Here are the available “Open Hours”: 7-8am, 7pm-12am M-F, and 12pm-12am Sa-Su. WTF. Also FYI, you can’t register for more than 1 seminar (i.e. CS 294) because the registrar thinks they are all the same class. Okay, anyway. First, click on the top tab for the semester that you’re registering for. To the left, click “Add class,” and enter in the CCN from the previous step. Repeat for all your classes.

Links:
Bear Facts [link]: student homepage (i.e. websis)
TeleBEARS [link]: pre-registration, current class list, registration change, there is a tab for each semester
General class catalog [EECS, EE, CS]: usually out of date and doesn’t contain information about special seminars
Class listings [EE Fall, CS Fall] [EE Spring, CS Spring]: contains CCN and enrollment status for graduate classes
Class schedule [CS, EE, CS-next, EE-next]: includes class time, lists special classes (CS 298 = Seminars, CS 294 = Courses, not sure where the descriptions are though)

Class schedule [link, ScheduleBuilder]: printable class schedules, clunky searchable interface for classes

EECS Grad Info [link]
EECS Grad Handbook [link]
Transfer Credit Petition [link]
Add/Drop Form [link]

Please feel free to comment with suggestions on what else to include in this reference.

Optimizing for happiness

Let f(x) be a convex mood function, with happiness at its minimum. With all the swings of moods, f(x) is not necessarily differentiable, and although it may be steep at parts, we assume it is continuous.

Then, we wish to solve the minimization problem

    \[ \min_x f(x) \]

We propose to use a subgradient method. The intuition is that you may pick a direction for your mood to change. Any subgradient at your current point x will point upwards of the curve (less happy), so we take a step towards the opposite direction. There are a variety of ways to select a time step, e.g. exact line search, backtracking. Without loss of generality and for simplicity, we use a constant step size.

Bottom line: If you just smile a little more, you’ll end up happier.

Subgradient method for convergence on happiness

given a starting point x \in \text{dom } f
given an error parameter \epsilon \ll 1
\text{stop} = \text{false}
while ! \text{ stop} do

  • \Delta x \leftarrow -\partial f(x) % Select a subgradient
  • t \leftarrow \epsilon % Line search
  • if x + t\Delta < x and \abs{t \Delta x} \leq \epsilon then \text{stop} = \text{true}
  • x \leftarrow \min(x, x + t\Delta x) % Update

end while

(Thanks, Pranjal, for the inspiration.)

Curiosity

2 months into the PhD now, and we are very much still exploring this grand academic environment at Berkeley. Here are a few of the questions that many of us are asking ourselves and one another. And even though we fully realize that our answers will develop, warp, and combust over the course of the next half decade, we at least have some established prior from which we can begin our journey. The discussions have been extremely insightful and provocative, and I look forward to many more.

About the past

  • How did you get here? Why are you here, at Berkeley? Perhaps differently, why do you think they admitted you?
  • How do you value money? What is your cost for agreeing to not pursue a PhD? 20 million vs 500 billion?

About the future

  • What do you care about? What is your big problem/idea/area?
  • What would you consider to be the biggest problem for society?
  • Do you consider your role in society? What do you consider it to be? Do you feel an obligation to serve society in the way that you are best suited? How does happiness factor in?
  • Do you think your time is best spent via a career in academia? Via research? In industry? As a parent?
  • Do you want to become a professor?

And about the present, quite literally

  • How many projects are you working on now? Which of them with professors?
  • How many group meetings of different professors are you attending?
  • What’s your plan for this semester? For the first year?

How to Berkeley

Berkeley’s online interfaces (e.g. for class registration) are very confusing as compared to what I’m used to at MIT. In case I’m not the only crazy person, here is a reference:

Bear Facts [link]: student homepage (i.e. websis)
TeleBEARS [link]: pre-registration, current class list, registration change
Class listings [EECS, EE, CS]
Grad Class listings [EE, CS]
Class schedule [CS, EE, CS-next, EE-next]: includes class time, lists special classes (CS 298 = Seminars, CS 294 = Courses, not sure where the descriptions are though)

Class schedule [link, ScheduleBuilder]: printable class schedules, clunky searchable interface for classes

EECS Grad Info [link]
EECS Grad Handbook [link]
Transfer Credit Petition [link]

Please feel free to comment with suggestions on what else to include in this reference.

2013: In which we won the MIT Mystery Hunt

Half a week later and despite the lack of sleep, the memories of the MIT Mystery Hunt are starkly fresh. I am incredibly happy and honored to be a part of the small group of hunters to solve the meta puzzle that ended the 2013 Mystery Hunt.

But the team that was, whose name due I suppose to the lack of character limit in the registration form and too much creativity was the entire text of Atlas Shrugged, was called by the Sages and asked, “Would your team agree to stop if the team that was currently in the lead was given the coin?” Other lead teams were given the same option. This was a huge break of competition format, and a question as impossible to answer as some of these puzzles. [Shrugged] was close to the Indiana Jones metapuzzle answer involving decoding a huge calendar wheel of dates, but had been given a wrong response to a yes/no hint question asking if half of their data was right. When they get a second call from HQ correcting the mistake, they turned down the offer to stop Hunting and pressed on. Five minutes later, John Galt and friends did get the fifth of six round answers and headed off for the last task, the runaround.

via 2013: The Year the Mystery Hunt Broke | Wired Magazine | Wired.com.

Sunday night and beyond, Twitter saturated with good-natured frustration about hunt. My favorites:

Damn it, someone win the mystery hunt. (@dbfclark)

Find the damn coin. #MysteryHunt (@gemini6ice)

dear god how much longer? #mysteryhunt (@roydraging)

Holy shit they just mad[e] it so you can skip an entire round in order to end this thing. This is trouble #MysteryHunt (@jmgold)

This #mysteryhunt is so long that it’s spanning two presidential terms. (@Jeffurry312)

Appropriate that the team with the longest name won the #mysteryhunt with the longest duration. (@mersiamnot)

Winning was awesome and, even better: by the end, many of the other teams thanked us for winning (and thereby ending the hunt).

[Image credit: lroyden]

75 hours and 19 minutes, the longest in Mystery Hunt history. I learned so much, got to know a bunch of cool people, and am so happy to be a part of it all.

Singapore: National Day

Singapore’s 47th National Day marks Singapore’s independence from Malaysia and consists of a “Parade” with lots of marching, music and singing, salutes, performances, and fireworks. Unfortunately, you need an invite or ticket to attend, so we watched the stream from our apartment by downtown Singapore (oh yeah– hello from Singapore!). Interestingly, many of the local people do not recognize National Day as a holiday — rather, it is mostly wealthier people, civil servants, and foreigners who partake. The locals told us that it’s essentially a government function. What we saw affirms this too; aside from the flags and banners everywhere, life and traffic seemed to continue as usual. Our morning started with a huge procession of red-wearing Singaporeans next to our apartment walking off to somewhere, and we got very excited for the big day, but the places we went did not seem to be affected by the holiday at all. We learned that educators and officials are invited to the parade, and I wonder who else. I originally associated National Day with US’s Fourth of July, but after some research, I deemed it to be more like a festive version of the State of the Union address. Except it seems that this year, they aired the National Day message a day early (transcript here). So there goes that theory.

[Photo credit: 1 2 3]

Either way, it was very interesting to see Singapore show off its various groups of armed forces and performers of the various southeast Asian cultures, to listen to the singing in Singapore’s 4 national languages, and to see the sea of some 27,000 people in the world’s largest floating stadium. So many colors, so many styles! I guess the mix of cultures is their culture. Despite the utter lack of Caucasians, there is a touch of British influence to much of what we see in Singapore, and it is even apparent in the show, when performers wearing traditional southeast Asian drag dance to rap. And since Singapore’s such a tiny place, we could hear the fighter jets and fireworks from our apartment as we caught them on the TV.

Anyway, happy National Day!

Bitap algorithm

The bitap algorithm is an approximate or exact string matching algorithm that is one of the underlying algorithms of the Unix utility agrep (approximate grep). What differentiates it from other string matching algorithms is its use of bitwise operations, that make it run super fast.

The algorithm for exact string matching works by encoding the pattern to be matched in a bit matrix whose dimensions are the length of a long [31] by the length of the alphabet. So, let’s work with a small alphabet of size 3. A pattern such as “abcc” would be encoded as

1111111111111111111111111111110 # pattern/a
1111111111111111111111111111101 # pattern/b
1111111111111111111111111110011 # pattern/c

see more »

In the “a” row, there’s a 0 for every instance of “a” in the pattern, as indexed into the corresponding bit array. The same applies to “b” and “c.” The letter “c” occurs in the 3rd and 4th place of the pattern, so the 3rd and 4th lower order bits are set to 0. Everything else is a 1.

Let’s match this pattern to the text “aaabcca,” which requires a separate bit array for keeping track of how far we’ve gotten, if we need to start over, etc. More precisely, this bit array keeps track of all matches of the current iteration. We initialize this bit array to ~1 (not 1, long format)

1111111111111111111111111111110 # state

Now, we iterate through the characters of our text “aaabcca.” Here’s where the bitwise operations come in. We 1) select the first letter of the text and bitwise-or the corresponding pattern bit matrix with our state and 2) left shift the state over 1:

Text aaabcca
1111111111111111111111111111110 # pattern/a
1111111111111111111111111111110 # old state
1111111111111111111111111111100 # new state

Awesome, a 0 indicates a match and a 1 indicates a mis-match at the corresponding position. So, so far, we’ve got a match of “a” and are ready to see if the next letter matches too. Next:

Text aaabcca
1111111111111111111111111111110 # pattern/a
1111111111111111111111111111100 # old state
1111111111111111111111111111100 # new state

We’ve still just got a match at “a”…

Text aaabcca
1111111111111111111111111111110 # pattern/a
1111111111111111111111111111100 # old state
1111111111111111111111111111100 # new state

OK, I’m getting bored…

Text aaabcca
1111111111111111111111111111101 # pattern/b
1111111111111111111111111111100 # old state
1111111111111111111111111111010 # new state

Text aaabcca
1111111111111111111111111110011 # pattern/c
1111111111111111111111111111010 # old state
1111111111111111111111111110110 # new state

Text aaabcca
1111111111111111111111111110011 # pattern/c
1111111111111111111111111110110 # old state
1111111111111111111111111101110 # new state

Suppose the pattern is of length m. Each iteration checks the new state for whether the m+1th lowest bit is a 0. If it is, that means the pattern was matched to completion, like in this case! Awesome, we win.

Due to the limitation of this algorithm to strings of 31 characters or less, the runtime is O(1). The number of bitwise operations required is 2n, where n is the length of the text.

beyond low hanging fruit