Nosebleed: Day 2

So this is day two of SMACS 2008. Two words: interesting and nosebleed. The first speaker talked about (mostly) complexities of algorithms over parallel networks in different topologies. It started with Turing machines and other computation models. I learned about the possible connection of Apple's logo (a bitten apple) and Alan Turing, the "father" of computer science. It was rumored that Turing died by dipping an apple in cyanide before bitting it. Snow White wannabe? (I heard he's gay.) LOL

So the topic was like data structures and algorithm analysis meets data communications and networking. This is, of course, another new thing learned (I hope) because I've only dealt with analysis of algorithms in a sequential setting (using only one processor). Parallel algorithm uses multiple processors. I have always thought that more processors are always better for any type of problem. Apparently, cost (eg communication cost) also grows with the number and sometimes it grows higher that the speed up in processing the algorithm.

One thing that I found really interesting is the application of operations research in parallel computing. So this is like Statistics meets Computer Science. And I thought, why not? Parallel processing involves a lot of scheduling and queueing of processes, etc., which are what we basically studied in operations research in Stat (only our examples there are more on industrial applications).

Like the first day, lunch was great. I ate a lot! I needed it to energize my brain. During lunch break we were provided with some entertainment (on the LCD projector) via some nerdy math/comp.sci. jokes that are only understood by math/cs majors. Those were really funny, indeed, but definitely not so easy to share.

The afternoon session topic was on Formal Languages, which was something I looked forward to because I'm teaching Automata Theory and Formal Languages for the first time this sem. This would give me more confidence in teaching the subject.

The talk was a good refresher of what I have encountered during my grad course, especially about the Pumping Lemma for Regular Languages that is used to prove irregularity of languages. I wonder how I'm gonna deliver this topic to my students though. It took me quite a while to actually understand it during my MCS. And oh, there is also a Pumping Lemma for Linear Languages (where w = uvxyz). Samot kalibog!

The most nosebleeding part for me was the Recursively Enumerable Languages, which are languages accepted by Turing Machines. I've never actually liked this part bcoz I don't like the notations. The Turing machine is the model of the modern computer (yet it still looks primitive to me). This is actually the part that made me retake Theory of Computation during my comprehensive exam (I didn't answer the questions on Turing machines.). And after the talk, sad to say, I still do not like it.

The most interesting stuff I learned is the application of Formal Languages to molecular biology. Whoa! Apparently, the alphabets in DNA/RNA (a,t,c,g,u) can be treated just like alphabets in Formal Languages. A DNA structure can be modeled using regular expressions and context-free grammars. Amazing! However, I was not able to get how it's actually applied coz my head was breaking and my sinusitis was killing me.

It was a long learned-a-lot day.