Education

CST Part 1A

... otherwise known as Part 1A of Computer Science Tripos in University of Cambridge has officially ended.

All in all, a rather enjoyable year. From the introduction to ML by the brilliant Prof. Larry Paulson, to the realms of Discrete Mathematics II (with a wicked a proof of existance of ordinal numbers in the exam); from Algorithms to Software Design, from Digital Electronics to Operating Systems, from Floating-Point Computation to Regular Languages and Finite Automata; and everything in between.

A crash course, but the one that is definitely worth going through.

If you're just about to come to Cambridge (or just starting your part 1A), here are a few simple tips that proved to be helpful for me:

• Don't fall behind - in lectures, ticks, homeworks, supervision assignments - in Cambridge pace it's difficult to catch up.
• Do things in advance - it's usually a very good idea and pays off well.
• Make sure that you keep your work/life balance: do a bit of sports (many choices in University of Cambridge Societies website) and go out once in a while. Paradoxically, having a few hours off in a week will help you to stay on top of things.
• Finally, keep an eye on these subjects: Discrete Mathematics II, Operating Systems II, Floating-Point Computation, HW ticks (sorted by the effort they took from me, in decreasing order). They might be different for you, but these particular ones are worth being aware of.

But most importantly - enjoy what you're doing.
Good luck and have fun.

"The Hard Way is the Right Way"

While the Europe is paralyzed by the volcanic ash and I am restrained from coming back to Cambridge, here is a quick recap of what I have been doing for the past couple of months.

1. Guitar

It looks like it is becoming a tradition - another vacation ends with a guitar video. This time - a short slow blues in Stefan Grossman's style. The usual apologies for the sound, video and playing quality apply.

Slow blues in E (Sefan Grossman's style).

2. Professional

I was accepted as a student member to the Chartered Institute for IT (former British Computer Society). For the next two years (at least) I should be reachable through this e-mail: manfredas.zabarauskas@bcs.org.

3. Studies

Without getting into the gory details, the outcomes of the Lent (read: second) term in Cambridge can be summarized by:

Conway's Game of Life

Mandelbrot set (1280x1024)

1. a wallpaper "spit out" by ML depicting a rather standard Mandelbrot set fractal (on the right),
2. an animation "spit out" by Java depicting eight-hundred generations of the spacefiller pattern in the Conway's Game of Life (further on the right),
3. and an insane amount of material to prepare for the upcoming exams; both broad and not as shallow as I expected.

I am still extremely enjoying it, even though the amount of my spare-time has decreased. (As an afterthought - I still had time to play basketball for Blues, Lions and my college, so maybe it was not that bad).

4. Internship

Over the summer I will be working as a Technology Analyst for Morgan Stanley, in their Innovative Data, Environments, Analytics & Systems (IDEAS) group.

Sunrise over Canary Wharf

During the interviews Morgan Stanley really left a very good impression both at the level of knowledge of the people working there and the communication and culture inside the company. We will see if that applies in day-to-day situations. In any case, I have nothing against spending the summer in Canary Wharf and seeing the investment banking industry from inside.

It will surely give me more things to write about in this blog, so be sure to check back once in a while.

Competition: internship offer packs from Morgan Stanley and Citigroup.

Conway's Game of Life

1. Description

In 1970s John Horton Conway (British mathematician and University of Cambridge graduate) opened a whole new field of mathematical research by publishing a revolutionary paper on the cellular automaton called the Game of Life. Suffice it to say that the game which he has described with four simple rules has the power of a universal Turing machine, i.e. anything that can be computed algorithmically can be computed within Conway's Game of Life (outlines of a proof for given by Berlekamp et al; implemented by Chapman as a universal register machine within the Game of Life in 2002).

Glider in the Game of Life

The Game of Life is a zero-player game, i.e. the player interacts only by creating an initial configuration on a two-dimensional grid of square cells and then observing how it evolves. Every new generation of cells (which can be either live or dead) is a pure function of the previous generation and is described by this set of rules:

1. Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
2. Any live cell with more than three live neighbours dies, as if by overcrowding.
3. Any live cell with two or three live neighbours lives on to the next generation.
4. Any dead cell with exactly three live neighbours becomes a live cell.

For more information, patterns and current news about the research involving Game of Life check out the brilliant LifeWiki at conwaylife.com.

2. Implementation

The following applet visualising the Game of Life has been developed as part of the coursework for Object-Oriented Programming at the University of Cambridge, all code was written and compiled in Sun's Java SE 1.6.

Click on any of the screenshots or the button below to launch the Game of Life (and if nothing shows up, make sure that you have the Java Runtime Environment (JRE) installed).

Spacefiller (Game of Life applet)

Unplugged in G

Another vacation, another video - as usual, apologies for the sound, webcam and playing quality. Three days left 'till the journey back to Cambridge.

Gel electrophoresis of Senecio vulgaris, S. squalidus and S. cambrensis DNA strands.

Vacation status: haven't even touched anything related to Computer Science. On the other hand, brushed up on complex trigonometry/logarithms and series expansions (read: maths), and feel reasonably happy to discuss plant evolution through polyploidy (read: biology, see: picture on the right).

Post-vacation status update: apparently I did have to discuss plant evolution through polyploidy in my exam! What were the odds...

Anyway, here's the video. Oh, yes, and while we're at it - happy New Year to you all.

Eric Clapton - Wonderful Tonight (0:00/3:50),
Guns N' Roses - Wild Horses (3:54/6:16).

It Literally Pays Off to Do Homework in Cambridge

"Well done! - joint shortest traditional (and practical :-) sort for the OS1a prize tick". Cambridge, 2009.

45 minutes, 28 MIPS instructions and £25.
Computer Science FTW.

# Copyright Manfredas Zabarauskas, 2009.
# MIPS routine that reads an array of ten integers
# and prints the sorted array to console.
.text
main:   sub $t7,$sp, 40
l_read: li $v0, 5 syscall sw$v0, 0($t7) add$t7, $t7, 4 bne$t7, $sp, l_read l_out: sub$t8, $sp, 36 sub$t7, 40
l_inn:  add $t8,$t8, 4
lw $t2, -8($t8)
lw $t3, -4($t8)
ble $t2,$t3, no_swp
sw $t2, -4($t8)
sw $t3, -8($t8)
move $t7,$sp
no_swp: bne $t8,$sp, l_inn
beq $t7,$sp, l_out
l_prnt: li $v0, 11 li$a0, 10
syscall
li $v0, 1 lw$a0, 0($t7) syscall add$t7, $t7, 4 bne$t7, $sp, l_prnt li$v0, 10
syscall


Eigenfaces Tutorial

The main purpose behind writing this tutorial was to provide a more detailed set of instructions for someone who is trying to implement an eigenface based face detection or recognition systems. It is assumed that the reader is familiar (at least to some extent) with the eigenface technique as described in the original M. Turk and A. Pentland papers (see "References" for more details).

1. Introduction

The idea behind eigenfaces is similar (to a certain extent) to the one behind the periodic signal representation as a sum of simple oscillating functions in a Fourier decomposition. The technique described in this tutorial, as well as in the original papers, also aims to represent a face as a linear composition of the base images (called the eigenfaces).

The recognition/detection process consists of initialization, during which the eigenface basis is established and face classification, during which a new image is projected onto the "face space" and the resulting image is categorized by the weight patterns as a known-face, an unknown-face or a non-face image.

2. Demonstration

To download the software shown in video for 32-bit x86 platform, click here. It was compiled using Microsoft Visual C++ 2008 and uses GSL for Windows.

3. Establishing the Eigenface Basis

First of all, we have to obtain a training set of $M$ grayscale face images $I_1, I_2, ..., I_M$. They should be:

1. face-wise aligned, with eyes in the same level and faces of the same scale,
2. normalized so that every pixel has a value between 0 and 255 (i.e. one byte per pixel encoding), and
3. of the same $N \times N$ size.

So just capturing everything formally, we want to obtain a set $\{ I_1, I_2, ..., I_M \}$, where \begin{align} I_k = \begin{bmatrix} p_{1,1}^k & p_{1,2}^k & ... & p_{1,N}^k \\ p_{2,1}^k & p_{2,2}^k & ... & p_{2,N}^k \\ \vdots \\ p_{N,1}^k & p_{N,2}^k & ... & p_{N,N}^k \end{bmatrix}_{N \times N} \end{align} and $0 \leq p_{i,j}^k \leq 255.$

Once we have that, we should change the representation of a face image $I_k$ from a $N \times N$ matrix, to a $\Gamma_k$ point in $N^2$-dimensional space. Now here is how we do it: we concatenate all the rows of the matrix $I_k$ into one big vector of dimension $N^2$. Can it get any more simpler than that? Continue reading

White Man's Blues

Due to the fact that I have found time to record these videos, I'm starting to suspect that my vacations have prolonged quite a bit... And I still have more than a week left.

Status update: apparently I have been awarded the Simon Gray prize by the Department of Philosophy at the University of Edinburgh. That, a KAL industrial scholarship, a couple of other prizes... I almost regret having decided to leave.

Anyway, here's the video. Try to figure out which is worse: my playing or my webcam's video quality.

Education

Edinburgh University, Computer Science and Artificial Intelligence, Semester II

Labs @ Edinburgh University

As I have promised earlier, here's the second part of my impressions about the individual courses in the first year of Computer Science and Artificial Intelligence at the University of Edinburgh. Hopefully you will find it useful, e.g. when choosing your outside courses, preparing for the exams or simply getting a taste of the CS undergraduate life in the University of Edinburgh.

Once again, please bear in mind that all what is written below represents only my personal opinion.

Innovation and Enterprise for Scientists and Engineers
Professor: Khaled Benkrid

Lectures: a brilliant introduction to the main components and aspects of modern entrepreneurship, definitely one of the most interesting business courses that I’ve been to so far. Not only will you get the basic theoretic concepts of the modern business (like industry, marketing, operational, financial analyses, risk assessment), but you’ll also put them into practice while writing a business plan for your own idea, which will then account for 50% of your final grade.

What’s more, you’ll get the guest talks of local entrepreneurs (either spin-offs from the university, or related in some other way), an overview of the legal system regarding UK start-ups and businesses (PLCs, sole-traders, etc) and on top of that – it will all be related to the science and engineering (with Dr. Benkrid being a computer scientist himself!).
All in all – a highly inspiring, exciting and recommended course!

Exam: well… it all can’t be that interesting. Continue reading

Education

University of Cambridge, Wolfson College

University of Cambridge, Wolfson College

So, it's finally official. In less than two months time I'll be reading Computer Science at the University of Cambridge, Wolfson College. Hopefully that's the last university in my universities chain - all in all there are not many better places to go to. Not many at all.

I'm already looking forward to it. To the legendary supervision sessions, to the world class experts in the field, to the competitiveness amongst the students. I'm sure I will finally arrive at the place where I'll be the average guy between the best one's... not the other way around.

(I'm not convinced that the latter applies to the basketball team, though. Well, I guess we'll find that out pretty soon).

Confirmation Letter. Cambridge University, Wolfson College, 2009.

Education

Edinburgh University, Computer Science and Artificial Intelligence, Semester I

The exam results came back and the first year is finally over, therefore I have decided to share my impressions about the individual lectures in the first two semesters. Hopefully it will help someone to choose one subject over another, not to make the same mistakes when preparing for the exams that I did, or simply to get the taste of the first year in college. Please bear in mind that all what is written below represents only my personal, highly subjective opinion.

1 Night in Haskell

Functional Programming