This material old. Corrected and revised material is at
http://cseweb.ucsd.edu/~gill/BWLectSite/
and is called Arithmetic, Logic and Numbers
Mathematics for Algorithm and
Systems Analysis
by
Edward A. Bender & S. Gill
Williamson
248 pages
Intended audience: Sophomores. This
is the second quarter of a 2 quarter sequence;
however, there is some overlap since not all students have had the first
course.
Background: Some familiarity with calculus is assumed but is not essential.
Comments and errata
are appreciated. ebender@ucsd.edu
Text for preceding course:
A Short Course in Discrete Mathematics by S. G. Williamson
You may download a copy for personal use from this web page at no charge.
This material is intended for double
sided printing. All files start on a right hand page.
ps pdf Table
of Contents
ps
pdf
Unit CL: Basic Counting and Listing
ps
pdf
Unit Fn: Functions
ps
pdf
Unit DT: Decision Trees and Recursion
ps
pdf
Unit GT: Basic Concepts in Graph Theory
ps
pdf
Index
ps
pdf
Solutions
Known Errata as of 10/18/05 [page numbers] in
More important errors are marked with an asterisk.
[5] CL-5: The last line of Example 2 should
capitalize North and South.
[5]
CL-5: In the last sentence of Example 3, “word” should be “name”.
[27]
CL-27: The running head should be justified right, not centered.
*[27] CL-27: Exercise 3-6: Should say “An example of a name is LASLALS,
but LASLASS and LASLAAS are not names.
[27]
CL-27: Exercise 3-9: The inclusion of S(n,0) may be confusing
and should be dropped and the sum in the second line should be for n>0.
[35]
CL-35: In line 5 from
the bottom, there should be a period between “P(A)” and “From”.
*[48] Fn-4: Line 4 from the top should have “h^{-1}(3)=a”.
[57]
Fn-13: In Exercise 2.3, replace “call” with “called” in
the first line.
*[64] Fn-20: In Exercise 3.4, it should say “five points convert to balls”,
not four.
[68]
Fn-24: At the start of line 8, remove “The”.
*[78] Fn-34: Near the end of the first paragraph, the permutation should be “4,1,3,2,6,5”,
not “4,1,3,4,6,5”.
[81]
Fn-37: In line 14, the “sigma” in the subscript should be the Greek
letter sigma.
[84]
Fn-40: At the start of
4.4, “An 100” should be “A 100”.
[104] DT-16: Line 3 above the pseudo
code, “This is makes” should be “This makes”.
*[104] DT-16: In the pseudocode, “Merge(S1,S2)”, not “Merge(L1,L2)”.
*[109] DT-21: In all displayed equations, change “H(2,S,G,E)” to “H(2,S,E,G)”.
[120] DT-32: Just before the theorem, “Steps
1 to 3” should be “Steps 1 and 2”.
[123] DT-35: Midway between figure and
table change “1 and 21” to “1 and 20”.
*[124] DT-36: Between the two sentences in Step 4_0 insert “If k=1, stop
(no solution).”.
*[132] DT-44: Line 5 from the bottom should give a_0 as “5x2^0-3”
and a_1 as “5x2^1-3”. (The twos are missing.)
[147] GT-3: Just below mid-page, there
is a space between “or” and a comma.
[150] GT-6: In line 9 from the top, “form”
should be “forms”.
[151] GT-7: Line 8 from the bottom
lacks a comma: “easier to study is” should be “easier to
study, is”.
[151] GT-7: Line 4 from the bottom “the
P(G)” should be “then P(G)”.
[155] GT-11: Line 12 from the bottom
should start “P’(Q), removing”, not “P’(Q)
removing”. (Comma is missing.)
[155] GT-11: Line 11 from the bottom
should have “requires”, not “require”.
[156] GT-12: In Exercise 1.4(b), “True
or false?”.
[157] GT-13: In Exercise 1.7(a), “triangles
behaves”, not “triangles is behaves”.
*[159] GT-15: In line 12 from the top, add “at all vertices” after “Thus
simple graphs with loops”.
*[161] GT-17: In the first line after the definition, “phi(x)”
should be “phi’(x)”.
*[161] GT-17: Just before the example, “V x V.” should be “V’
x V’.”.
[161] GT-17: In line 7 from the bottom,
there is a space between “words” and the comma.
*[167] GT-23: In Exercises 2.2(d) and 2.3(b) there is the label “f”
with no edge. Remove the label.
[167] GT-23: In Exercise 2.3(a), the
label “B” appears twice.
Change the one on the right to “P”.
[179] GT-35: In Exercise 3.3(e), change
“vertices 12.” to “vertices is 12.”.
[187] GT-43: Line 10 from the top has a
missing right parenthesis: “(f(n)” should
be (f(n))”.
*[189,190] GT-45,46: “Merge(L1,L2)”
appears in 3 places. It should be “Merge(S1,S2)”.
*[190] GT-46: Line 13 from the top ends “n=1” but should end “n-1”.
*[191] GT-47: The formula for s_2 in line 11 from the top should have the floor
function around n/2, not around n-n/2.
*[192] GT-48: In the 4th equation display, “D(P_L(x)”
should be “P_L(x)”.
*[192] GT-48: In the pseudocode, the formula for
Q_L(x) should have a q_1, not a p_1.
[192] GT-48: In the bottom line, “have
two multiply” should be “have to multiply”.
[193] GT-49: In line 8 from the top,
one “log” is italicized.
[196] GT-52: In 8(a) “vertices
18.” should be “vertices is 18.”.
[202] Solutions-4: The 4th line
of CL-2.8(a) ends “If there 2” but should end “If there are 2”.
[208] Solutions-10: Line 8 from the
bottom ends “questions is” but should be “question
is”.
[211] Solutions-13: Line 2 from the
bottom has “lie the same” but should have “lie in the same”.
[212]
Solutions-14: Near the end of Fn-1.3(b), “look a the”
should be “look at the”.
[214]
Solutions-16: The answer to Fn-2.4(a) should end “=e^{100}=e.”,
not “=e^{100}e.”.
[215] Solutions-17: Twice near the end
of Fn-3.3(d) we have “x_x” but should
have “x_1”.
[215] Solutions-17: In the first line
of Fn-3.3(f) the subscripts on x are messed up.
They should be 1,2,3,4,5, not 1,2,3,2,1.
[215] Solutions-17: In line 8 from the
bottom, “x_1-1 choose 2” should be “x_2-1
choose 2”.
[216] Solutions-18: In Fn-3.7 “different
way” reads easier than “different one of the ways”.
[216] Solutions-18: Line 2 from the
bottom ends “+b^2 Cov(Y,Y)”
but should have “-b^2 Cov(Y,Y)”.
*[217] Solutions-19: The last equation should have “a^2 Var(X) + b^2 Var(Y)”, not “Vary(X)
+ Var(Y)” …
*[218] Solutions-20: … and so the top line should have a^2 gamma + b^2
delta”, not “gamma + delta” …
*[218] Solutions-20: … and the next should have “a^2 nr(1-r) + b^2
ns(1-s)”.
*[218] Solutions-20: The last equation display has “X+1” in 3
places but should have “X_1”.
[219] Solutions-21: In the start of DT-1.2(c)
“does 1” should be “do 1” and “After have done”
should be “After we have done”.
[226] Solutions-28: The last line is
missing a right parenthesis before the period.
*[227] Solutions-29: The second equation in 3.7 should begin “P(F|A)=1-P(F’|A)”, not “P(F|A)=P(F’|A)”.
*[228] Solutions-30: In DT-4.7(d), the first displayed equation should end “x^{1-n}”, not “x^{n-1}” and “D”
should be removed from the next equation.
[229] Solutions-31: The top line should
be “We will use …”.
*[229] Solutions-31: In DT-4.9 the rightmost parenthesized expression in the
first line of the displayed equation has two errors near the right end:
a sign error and a missing
denominator of 3: ((k^2-2k+1-1)+3k)/3
[234] Solutions-36: Near the end of
GT-3.4(a), “having most 2” should be “having at most 2”.
[235] Solutions-37: GT-3.8(c) has a
space between the left parenthesis and the c.
[236] Solutions-38: The second line of
GT-4.3 should be “We show by using the definition”, not “Show
using definition”.
[237] Solutions-39: The second line has
an extra right parenthesis.