Thoughts on the Science of Computing

I just finished another quarter of graduate school and am not so patiently awaiting grades.  The courses I took include algorithms, operating systems, and reasoning with partial beliefs.   All of them were interesting in their own way.  Algorithms  is  like solving a chess  puzzle.  You wait for the aha moment when the solution pops in your head.  This can be frustrating on a test because you never know how long it will take before this occurs.  If you have seen the problem before it is usually incredibly easy. 

One of the problems on the final was to prove the following problem is NP-Complete.  Is it possible to seat N knights around a table such that no two knights that have a quarrel are side by side.  The solution is to use a hamiltonian circuit and to reduce the finding of a hamiltonian circuit to that of seating the nights around the table.  When feeding the hamiltonian circuit to the knights problem you consider the vertices of the graph as the knights and each pair vertices that are not connected by an edge have a quarrel.  This will show that a hamiltonian circuit reduces to the knights problem.  You still have to show that a solution to the knights problem can be verified in polynomial time which is trivial in this case.

I think everyone knows what an operating system, but it helps to get your hands dirty with the kernel code.  It really seems fairly simple when you get to know the different pieces and Linux is a great platform with the source available to poke around.  In the class we wrote a Virtual File System and a Block device driver in addition to a simple shell.  All very instructive. 

The last class I took was, as I detailed before, about reasoning with partial beliefs and specifically using Bayesian Networks as a formalism to represent causality and to answer queries about a system giving beliefs and evidence.   This has many applications from data mining using a naive bayes model which simplifies notions of independene to genetic modeling of genes.  This area is one of my interestes as I look to specialize in Artificial Intelligence.  There still seems to be lots to be done in these areas as the field is relatively new. 

Now on to next quarter. 

I have been away from the blog since school started.  Life always gets more hectic.  This quarter I am taking three course, compiler construction, pattern recognition and machine learning, and an AI class in animats.  

The compiler course is the most demanding of the three because the projects are very time consuming, but very instructive.  The textbook is Modern Compiler Implementation in Java. 

The project we are doing is building a compiler that translates a subset of the java langauge into MIPS assembly code.  This is done in several phases or passes, from syntax and typechecking to building several forms of Intermediate Representations to performing register allocation and finally instruction selection.  The subset includes inheritance and enough of the java features to make these projects challenging.  I would recommend anyone to take a compiler course because a compiler is a large scale project and one of the more studied software problems.  As such many areas of computer science come together in a compiler.  In particular, register allocators use graph coloring algorithms and fix point calculations are used for things like liveness analysis.

The pattern recognition course is the most interesting.  In todays world we have access to massive amounts of data on the internet and in database systems.  Pattern recognition and machine learning are critical to mining this data for useful information.  The course I am taking focuses on Vision in particular but most of the techniques are more broadly applicable.  Some of the main topics that I hope to expand on more in my next article are Bayesian Decision Theory, different representations, and dimension reduction techniques from PCA, MDS, and Local Linear Embedding, to various discriminative techniques such as ADABoost and Fisher Linear Discriminant.  I have to say that these topics resonate with me coming from a Physics background, originally.  I appreaciate some of the mathematic concepts with these techniques, such as trying to find the intrinsic dimensionality of the data or concepts of manifolds.  In addition we spend a lot of time dealing with entropy and other statistical concepts similar to what finds in Statistical Mechanics. 

In my next article, I will delve into some of the specifics of the techniques listed above.  I hope to detail the compiler construction in more detail and also to give more details on some of the Pattern recognition methodologies.