**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 4^{th} 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 4^{th} 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.