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.  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 Dover edition
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.