I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific method?
Mathematics is a science also, and you would have to search for a long time to find published empirical results in this field (although I guess there must be some). There are other scientific domains where "lemmas and proofs" are valued over experience, such as quantum physics. That said, most sciences mix theory and practice (with various ratios), and Computer Science is no exception.
Computer Science has its roots in Mathematics (see Turing's biography for instance http://en.wikipedia.org/wiki/Alan_Turing), and as such many results (generally dubbed as in the field of "theoretical computer science") consist in proofs that computers in some computational model can solve some problem in a given amount of operations (e.g. conferences such as FOCS, STOC, SODA, SoCG, etc..). Nevertheless, many other results of computer science are concerned with the applicability of those theories to practical life, through the analysis of experimental results (e.g. conferences such as WADS, ALENEX, etc...).
It is often suggested that the ideal is a good balance between theory and practice, as in "Natural Science", where the observation of experiments prompts the generation of new theories, which in turn suggest new experiments to confirm or infirm those: as such many conferences attempts to accept both experimental and theoretic results (e.g. ESA, ICALP, LATIN, CPM, ISAAC, etc...). The subfield of "Algorithms and Data Structures" in computer science might suffer of an imbalance in the sense that "Theoretical" conferences are generally more highly ranked than experimental ones. I believe that this is not true in other subfields of computer science, such as HCI or AI.
Hope it helps?
Implementing algorithms well is a skill which takes a different set of tools than just proving theorems. Many algorithms which were discovered by the theory community have indeed been implemented in practice (although I would like to see the theory community take a bigger role in this process). Physics doesn't ask the same researchers to do theory and experiment, although it is expected that the two groups communicate. Why shouldn't you expect to see the same divide in computer science?
ADDED IN EDIT:
Expanding on my comment in answer to Suresh's about what I meant by "role" above, at Bell Labs and AT&T Labs, researchers in algorithms were encouraged to talk to people in development. I didn't do as much of this as I probably should have, but I did get at least one paper out of it, and I think it would be good for the field if there were more communication between people in theory at universities and practitioners. This doesn't mean that I think everybody who comes up with an algorithm should code it (even if it's practical).
On the other hand, coding algorithms (or having a student code them) that you think might be practical can be useful in getting them adapted by practitioners. Consider one example. Lempel and Ziv wrote two technical papers in 1977 and 1978 on new data compression algorithms. Everybody ignored them. In 1984, Welch wrote a much less technical paper giving a slight twist on LZ78 that improved its performance somewhat, and gave the results of a small study comparing its performance with other data compression methods. It was published in a journal read by a number of programmers, and the algorithm was given by a few lines of pseudocode. The method was quickly adapted in a number of places, eventually resulting in an infamous intellectual property dispute.
Of course, one of the best ways for algorithms researchers to communicate with practice is to produce grad students who go off and work at Google, IBM, or other companies, and we're already doing that. Another way might be to answer practitioner's questions in this forum. Hopefully, we're doing a reasonable job of that as well.
One research area that uses empirical methods and methods of Theoretical Computer Science is the field called "Experimental Algorithmics" or "Algorithm Engineering". Like Chris mentioned, high performance computing relies heavily on this as modern systems have complex cache and latency issues that we have a hard time modeling.
--Update 1/20/2013-- I would also mention a great presentation by Robert Sedgewick.
This depends on the discipline you are in; as Jeremy states, there is a spectrum of theory vs. practice.
Topics like complexity tend to be weighted towards the theory side, as often the goal is to find a boundary for the space or runtime. Implementing an algorithm in C++ and then running it a bunch of times isn't going to prove that a problem is NP-complete.
As a polar opposite, high-performance computing (with conferences like Supercomputing) are all empirical; no one would ever submit a proof to an HPC publication as there is too much variability with regard to memory hierarchy and kernel overhead.
So what seems like the same question (How long does something take to run?) will be approached two completely different ways depending on the goals, techniques, community, etc. See Poul-Henning Kamp's You're Doing It Wrong for an example of the dissonance.
In programming languages research many ideas for new programming language constructs or new type checking mechanisms stem from theory (perhaps informed by experience in practice, perhaps not). Often a paper is written about such mechanisms from a formal/theoretical/conceptual perspective. That's relatively easy to do. Next comes the first hurdle: implementing the new constructs in the context of an existing compiler and experimenting with it, in terms of efficiency or flexibility. This too is relatively easy.
But can we then say that the programming construct constitutes an advance to the science of programming? Can we say that it makes writing programs easier? Can we say that it makes the programming language better?
The answer is no. A proper empirical evaluation involving scores of experienced programmers over large periods of time would be needed to answer those kinds of questions. This research is hardly ever done. The only judge of the value of a programming language (and its constructs) is the popularity of the language. And for programming language purists, this goes against what our hypotheses tell us.
Perhaps I'm missing the motivation for your question but there are many examples of empirical results motivating research, algorithms and other results.
Plouffe gives an account of discovering the BBP spigot algorithm for the digits of $\pi$ where he recounts the use of whatever Integer Relation Algorithm Mathematica was using to discover the formula.
Along the same line, Bailey and Borwein are big proponents of experimental mathematics. See "The Computer as Crucible: An Introduction to Experimental Mathematics", "Computational Excursions in Number Theory" amongst others. One might argue that this is more experimental Mathematics but I would argue that at this level the discussion the distinction is semantic.
Phase transitions of NP-Complete problems are another area where empirical results are heavily used. See Monasson, Zecchina, Kirkpatrick, Selman and Troyansky and Gent and Walsh for starters, though there are many, many more (see here for a brief survey).
Though not quite on the level of Theoretical Computer Science or Mathematics, there is a discussion here about how the unix utility grep's average case runtime beats optimized worst case algorithms because it relies on the fact that it's searching human readable text (grep does as bad or worst on files with random characters in them).
Even Gauss used experimental evidence to give his hypothesis of the Prime Number Theorem.
Data mining (Bellkor's solution to the Netflix Prize to make a better recommendation system) might be argued to be a theory completely based on empirical evidence. Artificial Intelligence (genetic algorithms, neural networks, etc.) relies heavily on experimentation. Cryptography is in a constant push and pull between code makers and code breakers. I've really only named a few and if you relax your definition of empirical, then you could cast an even wider net.
My apologies for being so scattered in answering your question but I hope I've given at least a few examples that are helpful.