Introducing L-Systems

My apologies, I haven't been writing as much these days; I've been having a bit of a blogger's block as to what to write about. I've got a few other statistics articles in mind, however since I enjoy variety I don't really want to write about the same thing all the time. So I'll reach out to the readers, is there any topic in particular you'd like me to write about?

Now that that is taken care of, we can get down to business. I've been doing a lot of reading these days, and one thing that I've stumbled upon are a nifty little computer science topic called L-systems. These things are quite simple to describe, yet are able to produce all sorts of interesting results (have you noticed a common theme to some of my blog posts these days?).

You need 3 things to describe an L-system. The first is an alphabet. An alphabet is very simple, it is just a set of characters that you will use within your alphabet - nothing more, nothing less. This is similar to a programming language where your alphabet is some subset of the ASCII character set unless you're using something more esoteric like APL (which is actually pretty neat, I've been looking at it a bit recently and I might put up a post about it soon - I guess I don't have blogger's block after all! You're still welcome to give requests though :) ).
The next thing you need for an L-system is an axiom. An axiom is simply a finite, non-empty string from your alphabet. You can also call it a seed if you like. The axiom (or seed) serves as the basis for the growth of the system.
The third thing is the most important - the production rules. What these do is map a character in the alphabet to some string. You apply the production rules on the axiom by converting each character in the axiom to whatever the rules say it maps to.

Let's consider an example L-system:

Alphabet: F, +, -
Axiom: F++F++F
Rules:
F -> F-F++F-F
+ -> +
- -> -

It is not necessary to specify the rules for + and -, since if you don't include them it is assumed that they just map to themselves (the identity function).

Let's run this L-system through one iteration. Begin with the axiom:

F++F++F

Then apply the rules:

F-F++F-F++F-F++F-F++F-F++F-F

I'd go for another iteration or two, but as you can see this thing will grow quickly and the text would probably run outside of this div. I'll just let you use your imagination as to what the next iteration would look like.

You may wonder why I picked this specific alphabet, as it looks rather peculiar. It turns out that this alphabet is directions for a turtle. The F means go forward, the + means turn left, and the - means turn right, all the while drawing a line.

Suppose we make the angle that the turtle turns equal to 60 degrees and iterate 4 times, you'll end up with a picture like this:

If you iterated this L-system an infinite number of times and at each iteration divide the distance that the turtle moves on each F by 3, you would end up with a fractal called the Koch snowflake (I made the mistake of saying that name out loud to my girlfriend, which caused her to giggle uncontrollably - perhaps I pronounced it wrong).

The next thing we can do is give our turtle an upgrade. In the current state, the turtle is limited to only drawing convoluted lines. While this is good, there are a great many interesting things to draw that aren't lines. We can change this by adding a powerful new feature to the turtle with these two symbols: [ and ]. The [ will push the current state of the turtle onto a stack (there is only one stack, so I should call it the stack), and ] will pop that state off of the stack and restore the turtle to that state.

This gives us a lot more power to create interesting images. Consider this L-system:

Alphabet: F, [, ], +, -
Axiom: F
Rules:
F -> FF-[-F+F+F]+[+F-F-F]

If you iterate this system 4 times, use an angle of 22.5 degrees and a step size of 6 pixels for your turtle, you get something like this (grabbed from The Algorithmic Beauty of Plants (The Virtual Laboratory)):

That's a bit cooler! And that image is generated by a completely deterministic process (aka no randomness). Which means that unlike my fractal trees, you will get exactly the same picture if you follow the rules above.

You can take these L-system things much much further, however I can see your eyes beginning to glaze over, so I will save that discussion for another day. As for code, you can see the L-system parser here, and the turtle graphics renderer here.

Computer Science vs. Economics For Me

A question people have asked me many times is why I went from Computer Science to Economics (although I'll note here that I actually did finish the CS degree instead of just transferring). It's a valid question, and I figure I'll answer it here.

Update: For those of you who are double-majoring in Computer Science and Economics, stay with it! If you go into an economics-oriented field, your computer skills will set you far apart from the hordes of computer-illiterate economics majors that graduate each year.
For those of you only studying economics, the best piece of advice for you is this: learn to use computers. And go beyond Excel, learn something sophisticated like SQL or R which are much more powerful.

And now, back to the article:
Here are my reasons:
1) While I like programming and working with computers, I found that working with them 40+ hours per week drained my enthusiasm for playing around in the off-hours. I would get home from work and not want to go anywhere near code. It was depressing. Now, even after doing stats and math all day long, I have no problem writing code at night when I'm done studying. So therefore I have decided that I would like to keep coding as a hobby, and do something else to earn a living.

2) More of the people I care about are interested in Economics, so they actually want to hear what I have to say about it (which isn't all that much right now, strangely enough). Some of my friends do care about computer stuff, in fact some of them even read this blog (hey guys! *waves*) but the vast majority of my friends and family don't really care too much about programming, computer science, Linux, etc. It's not that it isn't relevant to them, most of them find computers useful in some form or another, but when you compare questions like "why did I get a virus?" to questions like "why did I get laid off?" or "why did my investment portfolio bomb?" there is a much higher level of interest in the latter two. It's also a question of respect, I suspect that economists get a slightly higher level of respect than do programmers (although these days maybe not!).

3) I feel I can make a bigger contribution to the economic world than the computer world. It seems to me like a lot of the people doing things at the top in economics are just wanking around with math and saying that it reflects reality. I think it would be interesting to see what happens when you throw in more computer simulations using AI, or start wondering what happens when you mix computational complexity with game theory. For example, existence/uniqueness of equilibria matter and all, but the ability for a decision-maker/market to find said equilibria in a timely manner matters too.

4) The computer industry is governed more by economics than computer science (technology/computer science does play a fair-sized part mind you, just the part played by economics seems to be bigger). Why is Microsoft so big? Why is Java so popular? The answers to these questions are answered by economics as much as by technology.

Second Update (2015-06-18): It's been 6 years since I wrote this article, and probably 5 or so since that last update. That's enough time for some adventure and experience, which I'll share it here. I did a Master's in Economics, and worked in a number of different jobs: algorithmic trading, a successful Internet marketing startup, my own video game startup (briefly), and I'm now working at YouTube in San Francisco. This adventure is not over - I'm not even 30 years old. I know that in a few years if I decide to leave the Bay Area, I can go pretty much anywhere and not have to worry too much about finding work. There are very few disciplines that can boast this, but computer science is one of them. So here are some reasons why I am back in the tech world:

1) The jobs pay better. A good economist knows that utility increases with income, and therefore the rational choice between the two is to go into technology.

2) The jobs are more diverse. With economics you pretty much have two choices: a large financial institution, or a government. Unless you've built up some other skills elsewhere (business savvy, tech skills, social skills, entrepreneurship) then you've got limited options. With tech, you can do anything, anywhere. Software touches nearly every industry on the planet from farming to physics, and they are all looking for people who know how to make the computer do what they want.

3) It's easy to go from tech to economics; the reverse is not true. It wasn't very hard for me to get accepted to my Master's program in economics simply because I have an engineering background. Since graduate economics is all math and computers anyway, you're actually better off than the people who did their undergraduate degree in econ.

So while I found economics interesting, the only reason I would recommend that someone take economics over computer science is if they really liked economics and really didn't like computer science. Otherwise I'd suggest a major in computer science with either a minor or a double-major in economics.

Power of the Big O

The other day I posted an article about Hash#only and Hash#except. My friend posted a comment on it with another way of doing it that was IMO a lot more elegant, using a combination of reject and include? as opposed to my use of tap and array diffs/intersections.

Later on I decided to check out which is faster. My intuition told me that they'd be approximately the same, since the reject/include? version was quite obviously O(mn) with m and n being the sizes of the black/whitelist and the hash, and the &/- version was also O(mn). I wrote up a little benchmark here and tested it out. To my astonishment, the &/- version was a few orders of magnitude faster. I had to drop a zero from both the sizes of the array and the hash, and the results:

  0.090000   0.030000   0.120000 (  0.122033)
 10.920000   0.020000  10.940000 ( 10.960146)

Why is it like this? Well it turns out that &/- are O(max(m,n)), not O(mn). What these functions do is they convert one of the arrays to a Hash, which is O(n)¹. Then it iterates across the other array, checking to see if the current element is in the hash, which takes O(m) since hashtable lookup is O(1). Since the two things are not nested, the whole function is O(max(m,n)). The reject/include? is O(mn) because reject is O(m), and include? is O(n), and since include? is nested in the reject block you get O(mn).

I did a quick optimization and changed my friend's version to this:

class Hash
  def except(*blacklist)
    blacklist = Hash[*blacklist.map { |i| [i,1] }.flatten]
    self.reject { |k, v| blacklist.key? k } 
  end

  def only(*whitelist)
    whitelist = Hash[*whitelist.map { |i| [i,1] }.flatten]
    self.reject { |k, v| !whitelist.key? k } 
  end
end

This is O(max(m,n)), and is of similar performance to my original post.

I found this really interesting because it's one of the few times that computer science has actually played a direct role in my job, and because it let me dig into Ruby's internals a bit. It goes to show that even in web development, knowing the lower level details of things and some comp sci knowledge really pays off. Finally, it shows that elegance is not always worth it.

¹I'm fully aware that hashtables have some boundary cases where they are a lot slower than something like a tree, but for simplicity's sake let's say that they are as advertised.

Models of Computation

A random thought: currently our idea of computability revolves around the idea that a Turing machine can be created to accept or reject the input (you can also use lambda or predicate calculus, but for the purposes of this blog entry I will ignore them). For example, I can create a Turing machine to calculate the square of a number. But I cannot create a Turing machine that takes as an input another Turing machine t and an arbitrary input x and say if t will halt on x or not.

A question: Given a computable problem P, is it possible to have a Turing machine that will output a Turing machine that solves P? In English, can we make a computer program that is a programmer?

A brain can do this. A brain (IMHO) is an advanced device that can compute things. If a brain can do it, can a Turing machine? If not, perhaps there is a more powerful computational automaton than a Turing machine, just as a Turing machine is more powerful than a push-down automaton, which in turn is more powerful than a finite-state automaton?

Thinking about this kind of thing makes me want to go back to school.

RegExs and Finite State Automata

In my regular browses through the Internet, I stumble across comments, flame wars, etc. Through doing this, I've realized two things: lots of computer-y people don't know about regular expressions (a highly useful tool) and a lot of them don't seem to know what computer science is (having taken comp sci in school, it slightly bothers me when people call something comp sci when it isn't actually comp sci). So I'm going to write about an actual comp sci topic in hopes that at some point I may help educate people. Also I'm writing this because I like automata theory and want to talk about it.

Regular expressions (regexps) are a part of computer science, in the sub-discipline of automata theory. You can probably put them into other sub-disciplines, but this is one where they are used a lot.
So what is a regexp? Many of us use them, or have heard of them. Well, let's compare to math. An arithmetic expression is a list of primitives (like numbers or variables) and possibly operators (possibly, since "5" is technically an expression) including + and *. They are given an input (usually a set of values that correspond to any variables used in the expression) and evaluate to a certain value.
A regexp is similar to an arithmetic expression. The difference is that a regexp doesn't really evaluate to a value as an arithmetic expression does, rather the regexp accepts or rejects the input (you could say it evaluates to true or false).
So what does a regexp consist of? There is an alphabet Σ (alphabets are usually referred to by the Greek letter Σ, pronounced "sig-ma") over which the regexp works. This can be as simple as {a, b}, or more complicated, like Unicode. For simplicity, we will use small alphabets like {a, b}.
Then there are operations. There are three operations with regexps:

Concatenation: /ab/ (I will use / / to represent a regexp). The input is accepted if it is an a, followed by a b.
Alternation: /a|b/ The input is accepted if it is an a or a b.
Kleene Star: /a*/ The input is accepted if it is zero or more as.

We also need to introduce ε (Greek letter epsilon) which means "nothing".

Those familiar with Perl may say, "Hey, there are lots more operators than that!" True. There are lots more than that¹. However, these are the fundamental base operators. Like in arithmetic, there are the fundamental operations of * and + from which all other operations can be created² (like subtraction, exponentiation). All other operations can be made from combinations of these three, and none of these three can be made up from combinations of the other two (I'm pretty darn certain - you can say the Kleene Star is a combination of concatenation and alternation, but regexps have to be finite and Kleene Star is the only way to represent infinite inputs using a finite regexp).
Let's take a look at some others:
+ (one or more): /a+/ is the same as /aa*/
? (zero or one): /a?/ is the same as /(ε|a)/
and you can figure out others.

So these are pretty cool, but we still only have them at a theoretical level. How would we put these into practice? First, we need a bit more knowledge.

Now we move onto the finite state automaton or FSA (also known as a finite state machine, I just think "automaton" sounds so much cooler). These are "machines" that work over an input, and either accept or reject it.
What are these made up of? Well, we still have our alphabet Σ. We also have a finite set of states, Q. Then a start state s which is in Q, and a set of final states F which is a subset of Q. Finally, there is a transition function δ (Greek letter delta - us comp sci kids seem to love the Greeks) which is a function that takes two inputs: a state and a character, and outputs a state³.
The FSA works by starting in the first state s, and then going in steps over the input, consuming one as it goes, and doing a state transition for each one. The FSA moves to a different state depending on what δ outputs. Then once the input is all consumed, it is rejected if the state we are in is not in the set of final states F, otherwise it is accepted.
It's really easy to write a program to simulate a FSA. Here is a simple algorithm:

function doFSA(input, s, d, F)
    set q = s

    while input is not empty
        a = pop first element from input
        set q = d(a, q) // this is the state transition

    if q is in F
        accept
    else
        reject

Pretty simple eh?

So, how does this relate to regexps? Well, in automata theory there is a proof (that I don't feel like writing out here) that any regular expression can be converted to a finite automaton, and any finite automaton can be converted to a regular expression. That gives us a pretty easy way to simulate our regular expressions!

I've skipped a lot of details here. One that I want to talk about a little bit is non-deterministic FSAs.
A non-deterministic FSA allows two new things. The first is a ε-transition, where the FSA can move from one state to another without consuming an input. This means it can also move back. So you can look at this in different ways: the FSA is in both states; or the FSA's state is indeterminate, ie. you don't know which state it is in.
The second new thing is that FSA's allow for you to end up in different states for the same input from one state. If you're in q₂, you could consume an a and end up in q₃ or in q₄ since the transition relation (in non-deterministic FSAs it is a relation rather than a function) can allow multiple outputs for a specific set of inputs.
It doesn't take much to realize this makes simulating a FSA much harder. Fortunately for us, there is an algorithm on how to convert from a non-deterministic FSA to a deterministic FSA.

The proof that any regexp can be expressed as a FSA involves showing that you can have an FSA that accepts a one-character regexp, and then showing that you can combine these FSAs into larger FSAs that represent the three basic operations of regexps. This creates a non-deterministic FSA, that then can be converted into a deterministic one.

So how is this useful? How does this relate to programming or Ubuntu? It doesn't really. But I think it's good to know how things work, or where our tools come from.

¹ Perl regexps are not true regexps in that they let you use forward matching and that's not something that regexps can do. Second, if you know Perl regexps, I use an implicit ^ and $ in my regexps.
² See here for some info on why multiplication is not just repeated addition.
³ This is the case for deterministic FSAs, non-deterministic FSAs use a transition relation Δ over Q x (Σ U ε) x Q (that's a Cartesian product).

Computer Science Programs in Canadian vs. American Schools

I was reading blog entries today and stumbled across this article. Basically it talks about universities and Java and how programmers nowadays are sucking. It's been a fairly repeated argument over the last little while it seems.

The difference is this: I've been reading that stuff and wondering, "Hmm, are Canadian schools the same?" Up until I read this article, I've been thinking that it is true, Canadian schools pretty much are the same.

Now I'm not so sure. Yes, I did learn Java in my first year (I had done C++ in high school, so it was a breeze learning Java) instead of C or Pascal or Scheme or what else. It also seemed like the math requirements were a little skimpy.

However this article says that many of the students had never seen assembly language or things like that. We were required to take a class on assembly (more specifically, MIPS assembly with some Intel x86 stuff at the end). We also used some C, which the students were required to figure out a bit on their own having not being taught it in any class, although the extent of C that we did wasn't very much. There was one project where we had to take the assembly output of gcc and make some tweaks.
We were required to take a course on programming languages (I think all universities do, don't they?), where the coursework was heavy in Scheme. There was some stuff in Prolog and SmallTalk, although I don't recall there being any major assignment using them.
Finally, many of the upper level classes required coursework to be done in C or C++, two that come to mind immediately were called "Computer Graphics" (that's a no-brainer what it's about) and "Microcomputer Interfacing", which involved programming a mini-computer embedded on a robot with wheels and sensors and what-not.
There was math requirements, of course. Basic calculus, like derivatives and integrals. The honours program that I was¹ in required two advanced calculus courses, which looked at calculus using higher dimensions and vectors to name a few things. Other required courses included a course on linear algebra, and one on logical proofs and things like that.

Are these not things that are taught at all universities? I looked at some others and the curriculum seemed somewhat similar. Some of them had maybe one or two required classes that I didn't have to take, or I had to take one or two courses that they didn't have to take, but for the most part it was the same.
I've never looked at the American universities though. Is it similar to what I wrote above?

¹That's a big "was", I dropped the honours program later in my degree in favour of taking more economics courses.

The Greatest Invention in Computer Science

I was reading Jeff Atwood's article titled "The Greatest Invention in Computer Science" (coincidentally the same title as this blog entry), where he states that the routine is the greatest invention in computer science.

It makes me wonder one thing: "Does Jeff Atwood really know that much about computer science?"

Routines are an excellent addition to software development, but contrary to the opinion of many, computer science is not just about software development.

Personally I'd say there are several greatest inventions in computer science. Routines are good, but pale in comparison to the concept of a high-level programming language. Hard to imagine software development without those. Networking was another one (although this is a bit of a cooperation between electrical engineering, computer engineering and computer science). Software development has been done without it, but it has definitely made a big difference, computers being able to talk to one another without the use of removable media. And the list goes on, from the various sub-domains of computer science that I have missed here. One of my favourites is the concept of reduction - converting a problem to another problem that we've already solved. (This reminds me of a quick joke: A computer scientist sees a house burning down. Solution? Call fire department. Later, that computer scientist sees a house that is not burning down. Solution? Light the house on fire, thus reducing it to a previous problem.)

Perhaps it's my youth, I haven't been around long enough to use a language that doesn't have routines. Oh wait, that's not true. I did assembly language in university. We had to write recursive algorithms for tree processing in assembly. Not too hard, but you have to remember all this stuff about pushing your registers and return address onto the stack to save their state when you recursively call the function, then remember all this stuff about what offset of the current stack pointer your value is located at, etc. Yes, routines are nice, except when you have to do them in assembly language - this is another reason why we don't use assembly language.

Computer science extends far beyond the realm of writing software, but many people seem to lose sight of that fact. They think, "oh, you took computer science in school, you must be able to fix my computer." I tell them that we didn't learn that kind of thing in school. Nor did we learn about how to use Excel. Or what all those business technical acronyms mean (although if one business major could tell me what SAT stands for, I'd be impressed). We learn about how the stuff we use in software development and other computer-related fields works today, so that we may improve upon those methods to make better stuff 10 years from now.

So, routines are nice, but to claim they are the greatest invention in computer science? Please.

Reduce

It seems like there are a lot of programmers out there who don't know or understand what reduce (in Ruby, inject; in Scheme, fold) is. In a computer world where parallelism is becoming increasingly important, I feel that this is a basic concept that should be understood.

Reduce is a higher order function for converting a collection of data into a single value.
It takes 3 parameters: a function f, a list L, and an initial value s. f takes two parameters and returns one.
Reduce passes s and the first element of L to f, then takes the return value from f and the second element of L and passes that to f, and so on. When it hits the end of the list, the return result of reduce is the return result of f. In pseudocode:

function reduce(f, L, s)
    if L is empty return s
    set v to s
    for each element i in L
        set v to f(v, i)
    return v

or in functional-ish style:

reduce(f, L, s) = if f == []
                  then s
                  else reduce(f, tail L, f(s, head L)))

So what's the big deal with this? I can do this type of thing just fine with a for/foreach loop and a variable. For a single processor or thread, it is probably slower if you use reduce. Also for certain functions, reduce doesn't work very well either. This is pretty useless.

Let's look at this mathematically for a second. If f is associative, then the following is true:

f(a, f(b, c)) = f(f(a, b), c)

Examples of functions that are associative are: addition, max/min functions, merge sort, etc. On top of this, if f is commutative ( f(a, b) = f(b, a) ), then we don't even need to keep track of the order.
Assuming that f is associative, and s is the identity value of f (for all possible values a that can be passed to f, f(a, s) = f(s, a) = a), then the following holds:

reduce(f, L, s) = f(reduce(f, L1, s), reduce(f, L2, s))

where L₁ and L₂ are the two halves of L (if f is commutative, it doesn't matter the order in which L₁ and L₂ come). The great thing about this is that this perfectly scales on two processors. One processor does the first reduce, the other processor does the second reduce. Voila, we have just halved the time it takes for us to process this list!

We can take this further. Suppose we have n machines and a big dataset. We can split our dataset into n equal parts and tell each machine to reduce a part, and then one machine puts all the reduce results into a list and reduces that list. The time it took to process our dataset has been divided by n!

We can take this even further. Suppose we now have a dataset bigger than Sidney Crosby's ego (if that's possible). Designate one machine as a master (make sure it is a super machine that is reliable). This machine then takes a piece of our dataset, splits it up into chunks and assigns it to a bunch (or maybe several thousand) of slave machines. Those slave machines then reduce each little piece that they were given, as before. However this time, the master occasionally polls each machine to see if that machine has finished. If it has, then it grabs a new piece of the data set and assigns it to that machine. However if the machine doesn't respond, the master can assume that machine has failed and give the piece that the slave was working on to a different slave. So now we don't have to worry about our slaves failing.

So what has reduce given us? A massively scalable, failure-tolerant processing system. Who uses things like this? Google immediately comes to mind (their algorithm is called MapReduce, after all).

Reduce isn't the only function that scales like this, just seems to be the one that is the most difficult to understand. Reduce is a method of converting a list into a single value. Two others that come to mind are map and filter. Map takes a list and a function and applies the function to each element, returning the list with the modified elements. Filter simply takes a boolean function and a list and finds all the elements in the list for which the function is true.

These types of concepts applied are great ways to make easily scalable code and are things that programmers should be familiar with.

Let's Get Parallel

I think it's time we start moving toward a more parallel style of programming. I'm not referring to academia (which has been working on the parallel problem for decades) or the educated individuals who study things like Lisp or Erlang. I'm speaking to the other 80% of programmers who are embedded in a Java/PHP world where parallelism is unheard of. OK, Java has threads, and a rather good threading model to boot, especially with that nice little synchronized keyword.

However, the threading model itself is flawed. When working with shared mutable values, there are huge issues when it comes to parallelism. First, we have race conditions. So we create things like mutexes to prevent race conditions. Then, we have deadlocks. So we have things to fix deadlocks, leading to livelocks. It seems like no matter how many times we fix something, new problems crop up.

Functional languages, having no mutable values - unless of course you're programming in a functional language with an imperative accent and use set! - do not have this problem. They are inherently parallelizable. However, functional languages confuse a lot of people, so they aren't the best for business. How much easier is it to find someone who can program in Java or PHP than in Lisp or Haskell? Yikes.

The most promising of what I've seen is the actor model. This is sorta like object-oriented programming, except when one actor makes a method call (called sending a message in actor-speak) the caller doesn't block. The method is sent out and then the actor continues what it was doing. This is similar to programming as part of a team using an instant messenger, where each programmer is working independently and when they need to talk to another programmer, they send them a message.

One cool thing about the actor model is that it is pretty easy to scale. You could put all the actors on one machine, or across several machines. If the language or platform or whatever that you're using supports it, you could have network transparency from the programmer perspective. I actually worked on a project on this called RTSync that used an actor-synchronizer model where there were synchronizers included that managed timing among the actors, thus allowing for real-time programming with timing constraints and what-not.

Why should we be reconsidering our parallel programming? Because computers are going parallel. Now there are dual-cores, I'll bet in a few years we'll have quad-cores in people's houses, maybe oct-cores (is that a word?). So I can imagine that in 10 years if you don't have some good parallel programming experience, you're not going to be a very marketable programmer. So get on it.

The Value of a Computer Science Degree

After graduating and working for a while, I began to wonder what the value of my computer science degree was. I don't really use much of what I learned, in fact the majority of things that I use at work are things that I learned on my own time. There is the rare occurrence when I have to reason about the efficiency of a piece of code, but a lot of that is common sense and the rest you can ignore because computers are fast enough to handle it anyway.

I had my first experience with judging new graduate resumes the other day and began to wonder, what is the value of the degree? The majority of the students I found didn't really do anything on their own time, they only had experience with things from random classes they took.

So I'm thinking, maybe we should overhaul the computer science programs at universities. There is a lot of fluff in there about lambda calculus, flip-flops and NP-completeness that we don't really need, scrap all that. How often are students going to be designing parsers? Get rid of that. We should start giving courses on professional software development, with chapters on things like version control and how to use professional IDEs - you know, the useful stuff.

Algorithms courses are good, but they go into too much detail. We don't really need to know about characteristic equations or the exact theta-complexity of the algorithm, because if it runs slow, we can just buy a faster one. This is a free market after all. Just teach the kids how to use a quicksort() function and be done with it.

We should give big projects at the beginning of the course, and then change the requirements at random points in the semester. This will teach the students how to adapt to changes. It will show them what the work world is really like. Don't tell them exactly how to do everything, just tell them what you want and they have to do it.

With all these courses stripped out, we can now make room for the real stuff. There should be advanced Java courses teaching about J2EE, JSP and Struts, things like that. Also another one that teaches advanced C# programming with .NET. The C++ classes should teach useful things like how to make a window. I have never seen anything on resource scripts while in university, this should be remedied.

The only room for Linux in the degree is to teach students how to manage a server. Teach them things like configuring LDAP and Apache, security, and the like. Programming under Linux is inefficient and is not portable to Windows, which is the primary platform that software should be developed for.

After this reform, the universities will be producing students who have hands-on experience with real-world software. This will increase the efficiency of the software market tremendously, as we will no longer have to worry about training new employees. It will also benefit the students, as they will have the skills to tackle today's changing world and can compete in the highly competitive job market.

It is important to note that the majority of this blog entry is in a sarcastic tone. Please do not take it seriously.