Job Summary: Specific Responsibilities: Skills and Qualifications:

Required - BS in Computer Science. This is not uncommon to find on the job requirements out there. It should come as no surprise, and yet people seek these jobs after high school or just the barest of college background if that. If by some chance they get past human resources, often they quickly get discounted by the interviewiers - and with good reason. Frequently this reason is completely missed by the 18 year old kid that claims 8 years of experience on the resume.

What does a Bachelor of Science in Computer Science give you? What assumptions can be made about someone with this piece of paper that states that they have completed the coursework to the satisfaction of the university of blah blah? What does someone who doesn't have this lack?

Skill at translating ideas to code is one thing, and there is a great deal of ideas out there that can be done by the simple scribe. The small tasks, the things for the 15 year old javascript hack. However, the framework of ideas is without structure and quickly crumbles when attempting to work on a larger project that requires a deeper understanding of the nature of computing.

Compiler Design
In my opinion, this is the most useful of all the areas of Computer Science. Everything that is done by a programmer uses either an interpreter or a compiler. The understanding of what happens to the code after it is entered is invaluable when trying to optimize the program. Take for example the following two segments of code:
main()                  |  main()
{                       |  {
  unsigned int i = 8;   |    unsigned int i = 8;
  unsigned int j;       |    unsigned int j;
  j = i / 2;            |    j = i >> 1;
  return j;             |    return j;
}                       |  }
The one on the right has 3 machine code instructions (Pentium produced by gcc -S) for the assignment to 'j', while the one on the left takes 9.

Lexing, parsing, symbol tables. These ideas keep entering the code that is written. Reading config files, parsing html files and modifying them as they pass by, extracting useful data from log files. All of these common tasks require some level of knowledge of how lexers and parsers work. As the files get more complicated, a deeper and deeper understanding is necessary.

Artificial Intelligence
Everyone loves playing games, especially those against computers. True, the bots in Quake 3 and Unreal Tournament aren't quite the best, but they're sure better than the monsters in Doom!. Some of the improvement is faster computers, other is improvements in the actual underlying AI. Few people don't enjoy games, and few programmers don't dream of the games that they would write - and it requires a firm grasp on AI to actually come up with a computer that can win without cheating.

AI extends beyond 'simple' games of tic-tac-toe to heuristics. Heuristics are used in many places from medical databases and expert systems to determining what the cause of a panic message. These systems use much of the same computer science framework as a game of chess.

Language Theory
There are hundreds of programming languages out there, each with a different focus. There are times when you want to use a simple stack based language such as forth or postscript, or even more complex ones such as APL (if you ever have to do matrix work, you'll love APL). Other times, the task fits a functional language more closely, such as elisp and binding different functions to things. With yet other tasks (such as window managers and graphics), an object oriented is the most reasonable. Each of these has its place, and each language has its place too. It is rare for a person to sit down and decide to write a program more complex than Hello World in 6 different languages, and yet that precisely was an assignment in one of the college classes I took. Yes, with any Turing complete language you can write a compiler - but there are languages I wouldn't want to do it in.

For more information on the different types (broad classifications) of computer languages, see Comparison of programming language types.

Numerical Methods
A degree in Computer Science implies some level of numerical competence. Matrices are used in graphics extensively. The area under a curve is common enough to do in programming. Granted, the programmer rarely has to write the code themselves, but yet it necessary to have an understanding of the methods that produce the answer so they are not abused or misused. The Newton-Raphson method is wonderfully useful for finding the x intercept of a function, but you never want to use 0 as an initial approximation for the function: f(x) = x2-1. Why not? That is left as an excise to the reader.

Operating System Design
A vast majority of the engineering positions out there today are working either on an operating system, or very closely to it. Its even listed as a prime requirement for the job I quoted at the top. What is so special about operating systems for everyone else?

With the understanding of the operating system comes the concept of atomic operations. Every graduate of a CS program knows better than to give philosophers two forks to eat spaghetti with (or two chopsticks for Chinese food). Even though it sounds silly, the practical applications of going out to eat with philosophers is very common.

Even such simple things as how threads work and the difference between a spin wait and a blocking wait come into play with everyday code. Atomic operations and mutex locks are becoming more and more important. Each and every (well, ok, not every) one of Bart's Rules are important in compilers. While they are often rather odd look at operating system issues, there is a core of truth in each of them.

Database Design
Anyone can throw together a bunch of data and call it a database. It may not be pretty, it may not be fast, but it will work. However, anyone who has to use it at a later day will most likely hire a hit-man to find you. Database design covers simple things such as the difference between an object and an attribute, the normalization of tables to the more complex questions of how to store particular data. Why is it better to search on a number rather than a string? If indexes are good things, why is it bad to index everything?

Data structures
The first programs that people write are simple, as they should be. All they need are a few variables. More complex problems however, need more complex structures than can be provided with variables alone. Rapidly we learn about arrays and linked lists. In larger tasks, even these structures become awkward and hash tables and trees become necessary tools. With even more complexity, the trees become balanced (2-3 trees, red black trees, B and B* trees) and arrays become sparse. The foundations may be there with linked lists and arrays, but to get to the more complex structures it is necessary to understand things deeper than can be simply experienced or stumbled across.

Theory of Computer Science
From the basics of Deterministic Finite Automata to Regular Expressions and Non Deterministic Finite Automata (and the proof of equivalency) to more complex notions of Context Free Grammar, everything that has been discussed above rests upon these ideas. Computers are built on math and just as math has proofs, so does computer science.

The Turing machine is the tool used to work with in theory. Its simple nature hides its enormous complexity. It is not easy to prove things about a sparc processor, it is just too complex, and thus the Turing machine is used. It is the tape of the Turing machine that is 'n' in the big O. Anything that can be done on any computer can be done with a Turing machine with one infinitely long tape. It doesn't matter if the Turing machine is non-deterministic, or has multiple tapes - they are all equivalent.

The efficency of sorts, lookups and inserts all rest upon these foundations. To understand why a bubble sort is so awful for some data, and yet the best for almost sorted data to the sorting networks for parallel processors. It is the theory of computer science that it all boils down to.

A person who has a degree in computer science can be expected to tackle arbitrary problems and work out new ways of approaching tasks. In the construction world, you do not trust a crane operator to designing the structure of a large building but rather moving the pieces into place. The task of designing is left to the architect who has years of schooling under his belt with an understanding of the various materials that are being worked with. Likewise, in computing it is those who have the experience and understanding that are sought after to build the applications that are in use.


My interview questions:

  • AI: Explain how you would write a game of Tic-Tac-Toe without programming the entire search tree.
  • Theory: Describe a Turing machine and how to program it.
  • Languages: What is the difference between a functional, procedural, and object oriented language?
  • Operating Systems: Explain possible problems with lock files, especially over a network file system.
  • Databases: What is the ACID principle in database design?
  • Data structures: Explain how you would create a sparse array.
  • Compilers: What is the difference between lexicographic scoping and dynamic scoping in perl? How is it done? When should one be used over the other?

The job description at the top is real. If you are intrested, please /msg me. (July update - at one time was real. Curses upon the dot com bubble bursting)

Log in or registerto write something here or to contact authors.