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

Dover (2005) ISBN 0-486-44250-0
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.

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   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 Dover edition
More important errors are marked with an asterisk.

 CL-5: The last line of Example 2 should capitalize North and South.
 CL-5: In the last sentence of Example 3, “word” should be “name”.
 CL-27: The running head should be justified right, not centered.
* CL-27: Exercise 3-6: Should say “An example of a name is LASLALS, but LASLASS and LASLAAS are not names.
 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.
 CL-35: In line 5  from the bottom, there should be a period between “P(A)” and “From”.
* Fn-4: Line 4 from the top should have “h^{-1}(3)=a”.
 Fn-13: In Exercise 2.3, replace “call” with “called” in the first line.
* Fn-20: In Exercise 3.4, it should say “five points convert to balls”, not four.
 Fn-24: At the start of line 8, remove “The”.
* 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”.
 Fn-37: In line 14, the “sigma” in the subscript should be the Greek letter sigma.
 Fn-40: At the start of  4.4, “An 100” should be “A 100”.
 DT-16: Line 3 above the pseudo code, “This is makes” should be “This makes”.
* DT-16: In the pseudocode, “Merge(S1,S2)”, not “Merge(L1,L2)”.
* DT-21: In all displayed equations, change “H(2,S,G,E)” to “H(2,S,E,G)”.
 DT-32: Just before the theorem, “Steps 1 to 3” should be “Steps 1 and 2”.
 DT-35: Midway between figure and table change “1 and 21” to “1 and 20”.
* DT-36: Between the two sentences in Step 4_0 insert “If k=1, stop (no solution).”.
* 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.)
 GT-3: Just below mid-page, there is a space between “or” and a comma.
 GT-6: In line 9 from the top, “form” should be “forms”.
 GT-7: Line 8 from the bottom lacks a comma: “easier to study is” should be “easier to study, is”.
 GT-7: Line 4 from the bottom “the P(G)” should be “then P(G)”.
 GT-11: Line 12 from the bottom should start “P’(Q), removing”, not “P’(Q) removing”. (Comma is missing.)
 GT-11: Line 11 from the bottom should have “requires”, not “require”.
 GT-12: In Exercise 1.4(b), “True or false?”.
 GT-13: In Exercise 1.7(a), “triangles behaves”, not “triangles is behaves”.
* GT-15: In line 12 from the top, add “at all vertices” after “Thus simple graphs with loops”.
* GT-17: In the first line after the definition, “phi(x)” should be “phi’(x)”.
* GT-17: Just before the example, “V x V.” should be “V’ x V’.”.
 GT-17: In line 7 from the bottom, there is a space between “words” and the comma.
* GT-23: In Exercises 2.2(d) and 2.3(b) there is the label “f” with no edge.  Remove the label.
 GT-23: In Exercise 2.3(a), the label “B” appears twice.  Change the one on the right to “P”.
 GT-35: In Exercise 3.3(e), change “vertices 12.” to “vertices is 12.”.
 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)”.
* GT-46: Line 13 from the top ends “n=1” but should end “n-1”.
* 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.
* GT-48: In the 4th equation display, “D(P_L(x)” should be “P_L(x)”.
* GT-48: In the pseudocode, the formula for Q_L(x) should have a q_1, not a p_1.
 GT-48: In the bottom line, “have two multiply” should be “have to multiply”.
 GT-49: In line 8 from the top, one “log” is italicized.
 GT-52: In 8(a) “vertices 18.” should be “vertices is 18.”.
 Solutions-4: The 4th line of CL-2.8(a) ends “If there 2” but should end “If there are 2”.
 Solutions-10: Line 8 from the bottom ends “questions is” but should be “question is”.
 Solutions-13: Line 2 from the bottom has “lie the same” but should have “lie in the same”.
 Solutions-14: Near the end of Fn-1.3(b), “look a the” should be “look at the”.
 Solutions-16: The answer to Fn-2.4(a) should end “=e^{100}=e.”, not “=e^{100}e.”.
 Solutions-17: Twice near the end of Fn-3.3(d) we have “x_x” but should have “x_1”.
 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.
 Solutions-17: In line 8 from the bottom, “x_1-1 choose 2” should be “x_2-1 choose 2”.
 Solutions-18: In Fn-3.7 “different way” reads easier than “different one of the ways”.
 Solutions-18: Line 2 from the bottom ends “+b^2 Cov(Y,Y)” but should have “-b^2 Cov(Y,Y)”.
* Solutions-19: The last equation should have “a^2 Var(X) + b^2 Var(Y)”, not “Vary(X) + Var(Y)” …
* Solutions-20: … and so the top line should have a^2 gamma + b^2 delta”, not “gamma + delta” …
* Solutions-20: … and the next should have “a^2 nr(1-r) + b^2 ns(1-s)”.
* Solutions-20: The last equation display has “X+1” in 3 places but should have “X_1”.
 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”.
 Solutions-28: The last line is missing a right parenthesis before the period.
* Solutions-29: The second equation in 3.7 should begin “P(F|A)=1-P(F’|A)”, not “P(F|A)=P(F’|A)”.
* 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.
 Solutions-31: The top line should be “We will use …”.
* 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
 Solutions-36: Near the end of GT-3.4(a), “having most 2” should be “having at most 2”.
 Solutions-37: GT-3.8(c) has a space between the left parenthesis and the c.
 Solutions-38: The second line of GT-4.3 should be “We show by using the definition”, not “Show using definition”.
 Solutions-39: The second line has an extra right parenthesis.