What do Algebra and Calculus mean? I sometimes see phrases like 'the relational algebra' or 'the lambda calculus'. What is the difference between an algebra and a calculus?
 A: The mathematical meaning of long-used words shifts over time.  For example, limit in  Newton's time meant end.  And for a while now, some have tried, with limited success, to turn algebra from a subject to an object.  
Although it is barely relevant, let's turn to the etymology. "Calculus" means pebble.  Smoothed pebbles were used in the Mediterranean world's versions of the abacus, and with counting boards.  Professionals skilled in the use of calculi for addition, subtraction, multiplication, and sometimes even division, were called calculators.
A calculus is a set of algorithms for solving a certain class of problems. Thus we have the Differential Calculus, the Integral Calculus, and a number of others.  For a century or so, the (unmodified) word has become so strongly associated with a small number of specific courses that nowadays only those with an antiquarian bent are likely to name their subject a calculus.
The term "algebra," derives, as we know, from al-Khwarizmi's Hisab al-jabr wa'l muqabala.  This was the first systematic treatment of what we now call linear and quadratic equations. Of course people in various parts of the world did in effect know how to deal with such equations centuries before al-Khwarizmi. But it was he who made it a systematic discipline.  After developing the theory, he gave a number of applications, among them elaborate inheritance problems.
The term "jabr" seems to mean, or have meant, "putting together" (caveat: I know neither medieval nor modern Arabic). The term probably refers to procedures such as the one that transforms $7x-5=58$ to $7x=63$.  However, the term is not explained in al-Khwarizmi's book, at least not in the English translation.  
For more than ten centuries after al-Khwarizmi, algebra meant procedures for solving equations, or more generally the study of equations. The major break with that tradition came with van der Waerden's provocatively titled Modern Algebra (1930).  Since then, there has been a gradual divergence of usage between mathematicians and the schools.  
An amusing illustration of the gap is that my local public library has a pristine copy of Jacobson's Basic Algebra, presumably ordered by a librarian unaware that the title has different meanings in different communities.
"Algebra" in the modern (but no longer called modern) sense carries the connotation of concern with structure.  "Calculus" does not. Some branches of algebra retain a link with the traditional study of algebraic equations. Many do not.
A: I came here hoping for an elaboration on what I found in these publicly accessible slides, but actually I think it's stated more succinctly and satsifyingly (to my mind, and limited knowledge), so I'll restate it in case it's of use:
Algebra - Procedural method/algorithm specifying how to obtain the results.
Calculus - Description of what makes a result such, without knowing how to obtain them.
The slides are in the context of the Relational Calculus (as compared to RA), so for example, given the problem of finding those people with fathers named John:
$$\pi_{\text{name}}\ \sigma_{\text{fathers_name}=\text{'John'}}\ \text{People}$$
is a relational algebra, it tells us how to find such peoples' names.
$$\{\ t\ \vert\ t\in\text{People} \wedge t[\text{fathers_name}]=\text{'John'}\ \}$$
is a relational calculus, it tells us what makes an answer; not how to find them. 
A: For an outsider "algebra" and "calculus" are subfields of mathematics, as "botany" and "taxonomy" are subfields of biology.
But meanings tend to shift as we are getting closer to the core.
An "algebra" is a mathematical object, i.e., a set $A$ provided with certain relations, binary operations, "exterior" operations like $\alpha\cdot$, etc. In this sense an algebra of sets (used in probability theory) is a set ${\cal F}$ of subsets of a ground set $\Omega$ such that for any two $A$, $B\in{\cal F}$ the sets $A\cup B$, $A\cap B$ and $A':=\Omega\setminus A$ are again in ${\cal F}$. In a narrower sense an "algebra" is a ring consisting of elements $a$, $x$, $\ldots$ (with its axioms), provided with an exterior multiplication by real or complex numbers $\alpha$ such that $(\alpha x) y=x(\alpha y)=\alpha ( x y)$.
On the other hand a "calculus" denotes a framework of rules applicable in a certain environment. There is a "functional calculus" that assigns to any suitable analytic function $f$ and any  operator $A:\ X\to X$ on a Banach space $X$ an operator $f(A)$ such that things like Taylor expansions, Cauchy integrals, etc., make sense for $f(A)$. In a narrower sense the word "calculus" designs the set of rules pertaining to the fundamental theorem of "calculus", in particular the way we compute areas, volumes and the like by finding " finite expressions" that are "primitives" of other "finite expressions".
A: As it seems this hasn't been mentioned yet...
Branches
Analysis concerns the study of related elements.
(Limit Points, Derivatives of Curves, etc.)
Algebra concerns the study of structured spaces.
(Rings, Measure Spaces, Topological Spaces, etc.)
Calculus provides algorithms for the above.
Example
Consider Banach spaces.
Regard bounded operators between Banach spaces.
As an analyst one is concerned in finding properties of operators, e.g. trace class.
In that sense bounded operators are seen as individual elements.
As an algebraist one is concerned in finding criteria for isomorphy, e.g. reflexivity.
In that sense bounded operators are seen as a space itself.
The functional calculus can be used in either case.
(E.g. the Weyl algebra permits unitary representations.)
Summary
Finally, let me quote Martin Argerami:
"I'm an Operator Algebraist (which interestingly makes me an analyst!)"
