May it be correct and efficient

I got a response from another professor of mine. I enjoyed Peter Sanders “Informatik 3” course, which was about machine models and SAT for large parts. Here comes an answer from the rather theoretical algorithm camp of computer scientists.

Generally speaking, CS is concerned with building software and hardware that is

  • correct
  • efficient

Since I am working on algorithmics, the foundations of the latter area, let me make that more concrete there. You want to design, analyze and implement efficient algorithms for the problems that are most important / frequently used. Hence, you can look at building blocks that are used in many applications or more specific problems that show up in particularly important applications. Here is a sample of important building blocks that I happen to have worked on (but I do not claim here that my contributions are important):

  • sorting
  • dictionaries
  • shortest path search
  • full text search
  • collective communication in networks
  • load balancing

That feels a little “back to the roots”, but it shows that we still need to think about the basics. An example i can think of is a cuckoo hashing from 2001.

Published in: on May 16, 2007 at 12:16 pm  Leave a Comment  

The URI to TrackBack this entry is:

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: