Tag Archives: Computer Science

Computer Science Stack Exchange Live!

Computer Science Stack Exchange public beta

cs.SE in nondescript beta style

Since my post in December, Computer Science Stack Exchange has gone through private beta and is now accessible for everybody. Head over to cs.stackexchange.com and take a look! We are waiting for your questions so do not hesitate to post anything you have always wanted to know in computer science1, be it theory, applied or even practical!

We also need more expertise: out off almost 190 questions sixteen have yet to receive a good answer. among those are one about equivalence of Büchi automata and linear μ-calculus and another about efficiently learning regular languages.

You might also want to check out our hottest questions, including why Quicksort is often considered the best sorting algorithm, encryption using NP-hard problems and connections between Gödel’s incompleteness theorem and the halting problem.

I am very excited about this site. One one hand, it gives me the opportunity to share my knowledge in computer science with a wide variety of people, and I like teaching. On the other hand, I get to learn a lot. Not only do people ask about things I know next to nothing about so I can learn from the answers, but there are also original concepts. My favorite is Patrick’s proposal of heap automata; I have spent several hours contemplating his question about their power and follow-up questions.

I hope to see you on cs.SE soon!

  1. Mind the FAQ, though.

Computer Science StackExchange Upcoming

A screenshot of the current proposal for a computer science site in the StackExchange network.

I have posted about Stackexchange before. Helpful folks on various sites have solved many a problem I have had since then. I have posted a bunch of answers which—hopefully—helped out others in return. To say the least, I am convinced of the StackExchange model and am continually amazed at its effectiveness.

The wealth of knowledge saved on the StackExchange network1 has become so extensive that if you google for programming or LaTeX related problem almost certainly a question on Stackoverflow or tex.SE comes up. If not, asking there is often faster than searching the webs and/or trying around. Especially on tex.SE you can expect great answers in a matter of hours.

Now an exciting thing has happened: A proposal for a computer science site has reached commitment phase! That means that a number of people have to vote for the site in order to move it to a beta phase after which it will be a full-fledged member of the network2. The new site is to complement Stackoverflow and its derivates on one and cstheory.SE on the other side, filling the massive gap in between. I am very excited about this; if the community on cs.SE can be only half as good as on some other sites we are about to create the best resource for computer science students, researchers and users the web has seen so far.

But we are not there yet! First we have to have enough people commit to using the new site, then we need a successful beta. If you want this to happen, head over to area51, commit and be part of the community from the start!

  1. Licensed under Creative Commons, mind!
  2. Find more information about the process here.

On Planarity of Control Flow Graphs

For our master’s project, we include visualisation of control flow graphs of Java bytecode as a user interface feature. When discussing the feature, a question quickly became apparent: are control flow graphs (CFG) planar? If so, we expect drawing them to be relatively easy. If not, however, we can abandon hope for being able to always draw nice graphs.

Obviously, unconditional jumps can cause arbitrarily nasty CFGs; that is not surprising as GOTOs are generally to be considered harmful. We agreed, however, that we should rather consider basic blocks of actual Java rather than arbitrary bytecode, as it is Java code we want to talk about. Sadly, even if we disregard labelled break just to be save, Java CFGs are not planar in general. The examples we found suggest that this is true for most procedural and object oriented languages, too. Read more »

Regular Encoding of Binary Trees

Encoding of binary trees as a regular language?

A couple of months ago, a question on cstheory.SE asked whether there is a regular encoding of binary trees. My immediate gut feeling was: no way! Binary trees are equivalent to Dyck words and the language of those is not regular1.

I was able to back this feeling with an approach using generating functions. I showed that the number of binary trees with \(n\) nodes does not have a rational generating function; as all regular languages have rational structure functions, I claimed that this shows that binary trees can not be encoded with a regular language. This argument turned out to be somewhat fishy or incomplete since an encoding does not have to map all trees of size \(n\) to encodings of size \(f(n)\); at this point, the counting argument breaks down. Read more »

  1. Easily shown with Pumping Lemma for regular languages.

B. Liskov on the Power of Abstraction

Barbara Liskov giving her Turing lecture

Last week, Barbara Liskov visited Kaiserslautern and gave her talk On the Power of Abstraction. I had known her from the substitution principle named after her1 and taught to every computer scientist and programmer, but she is far more distinguished than that: Barbara Liskov is an ACM Fellow, holds the ACM Turing Award and the IEEE John von Neumann Medal and a couple of other awards, telltale of her influence on the field.

The talk she gave is actually her Turing lecture, obligatory for Turing awardees. The room was so packed that quite some people had to remain standing, and it was worthwhile to have come. You can watch the lecture—in another instance—in full here. For me as a CS novice, the lecture is a small time travel machine to the seventies: Barbara talks about the history of how abstract datatypes and related concepts came to be. As someone who grew up with languages like Java, it is hard to imagine a world where all programming there is is literally done on assembler level. So, lots of the material presented should feel trivial to the modern mind, but Barbara manages to instill the spirit of the time into her listeners. After her talk, you know why she got awards for things you take for granted today.

Since the lecture itself can be watched online, I just want to share my favorite quotes and anecdotes I wrote down during the talk; I hope I am not misquoting.

[Barbara] did not apply at MIT because she did not want to be a nerd.

I have no idea how I got that idea. [...] It was ready to be discovered.

You never need optimal performance, you need good-enough performance. [...] Programmers are far too hung up with performance.

There were no GOTOs because I believed Dijkstra.

It’s really just common sense.

Why did she get this award? Everybody knows this anyway!

Especially the last quote demonstrates, if unintentionally, the impact of Liskov’s and others’ work of that time. If something you conceive is considered common sense 30 years later, you really had a brilliant idea.

  1. She did not name it, of course. Apparently, she received an email in the 90′s by somebody asking her wether he got “her” principle right, surprising her She had not known that the principle had borne her name for years in the community.