Java Reference
In-Depth Information
See “Technically Speaking” from the February 1995 issue of IEEE Spectrum
[Sel95] for a discussion on the standard for indicating units of computer storage
used in this topic.
Introduction to Algorithms by Udi Manber [Man89] makes extensive use of
mathematical induction as a technique for developing algorithms.
For more information on recursion, see Thinking Recursively by Eric S. Roberts
[Rob86]. To learn recursion properly, it is worth your while to learn the program-
ming languages LISP or Scheme, even if you never intend to write a program in
either language. In particular, Friedman and Felleisen's “Little” topics (including
The Little LISPer[FF89] and The Little Schemer[FFBS95]) are designed to teach
you how to think recursively as well as teach you the language. These topics are
entertaining reading as well.
A good book on writing mathematical proofs is Daniel Solow's How to Read
and Do Proofs [Sol09]. To improve your general mathematical problem-solving
abilities, see The Art and Craft of Problem Solving by Paul Zeitz [Zei07]. Zeitz
also discusses the three proof techniques presented in Section 2.6, and the roles of
investigation and argument in problem solving.
For more about estimation techniques, see two Programming Pearls by John
Louis Bentley entitled The Back of the Envelope and The Envelope is Back [Ben84,
Ben00, Ben86, Ben88]. Genius: The Life and Science of Richard Feynman by
James Gleick [Gle92] gives insight into how important back of the envelope calcu-
lation was to the developers of the atomic bomb, and to modern theoretical physics
in general.
2.9
Exercises
2.1 For each relation below, explain why the relation does or does not satisfy
each of the properties reflexive, symmetric, antisymmetric, and transitive.
(a) “isBrotherOf” on the set of people.
(b) “isFatherOf” on the set of people.
(c) The relation R = fhx;yijx
2
+ y
2
= 1g for real numbers x and y.
(d) The relation R = fhx;yijx
2
= y
2
g for real numbers x and y.
(e) The relation R = fhx;yijx mod y = 0g for x;y 2f1; 2; 3; 4g.
(f) The empty relation ; (i.e., the relation with no ordered pairs for which
it is true) on the set of integers.
(g) The empty relation ; (i.e., the relation with no ordered pairs for which
it is true) on the empty set.
2.2 For each of the following relations, either prove that it is an equivalence
relation or prove that it is not an equivalence relation.
(a) For integers a and b, a b if and only if a + b is even.
(b) For integers a and b, a b if and only if a + b is odd.
