cr.yp.to update

 2005-261.html |  136 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2005-501.html |   69 +++++++++++++++++++++++++++++
 2 files changed, 205 insertions(+)
diff -ru .old-crypto/2005-261.html cr.yp.to/2005-261.html
--- .old-crypto/2005-261.html	2005-08-31 17:25:17.000000000 -0400
+++ cr.yp.to/2005-261.html	2005-09-09 22:29:55.000000000 -0400
@@ -255,5 +255,141 @@
 Example: {5,6} x {7,8,9} = {(5,7),(5,8),(5,9),(6,7),(6,8),(6,9)}.
 Example: {1,2} x {2,1} = {(1,1),(1,2),(2,1),(2,2)}.
 (1,2) is not (2,1).
+<h2>9 September 2005</h2>
+Oops, I left out a chapter from my copy of the book!
+Here are all the chapters of
+``A short course in discrete mathematics'':
+<ol>
+<li><a href="2005-261/bender1/contents.pdf">Table of Contents</a>
+<li><a href="2005-261/bender1/BF.pdf">Unit BF: Boolean Functions and Computer Arithmetic</a>
+<li><a href="2005-261/bender1/Lo.pdf">Unit Lo: Logic</a>
+<li><a href="2005-261/bender1/NT.pdf">Unit NT: Number Theory and Cryptography</a>
+<li><a href="2005-261/bender1/SF.pdf">Unit SF: Sets and Functions</a>
+<li><a href="2005-261/bender1/EO.pdf">Unit EO: Equivalence and Order</a>
+<li><a href="2005-261/bender1/IS.pdf">Unit IS: Induction, Sequences and Series</a>
+<li><a href="2005-261/bender1/solution.pdf">Solutions</a>
+<li><a href="2005-261/bender1/index.pdf">Index</a>
+</ol>
+<p>
+Class material from last Friday:
+Two pairs (a,b) and (c,d) are equal if and only if
+their first coordinates are equal and their second coordinates are equal:
+i.e., (a,b)=(c,d) iff a=c and b=d.
+Some names for the pieces a,b of a pair (a,b):
+components of a vector;
+components of a pair;
+components of an ordered pair;
+elements of an array;
+symbols in a string;
+etc.
+Review of Cartesian product.
+A relation from S to T is a subset of S x T.
+Examples.
+Functions from S to T.
+Steps to prove that f is a function from S to T:
+prove that each element of f is a pair;
+prove that, for each pair, the first component is in S;
+prove that, for each pair, the second component is in T;
+prove that, for each element x of S, there's a pair (x,something) in f;
+prove that, for each element x of S, there aren't two pairs
+(x,y) and (x,z) in f except when y=z.
+Examples.
+A function f is surjective (``onto T'') 
+iff, for each element y of T, there's a pair (something,y) in f.
+A function f is injective (``into''; ``one-to-one'') 
+iff, for each element y of T, there aren't two pairs
+(x,y) and (z,y) in f except when x=z.
+A function is bijective
+iff it is both surjective and injective.
+Examples.
+<p>
+Practice exam due Friday 9 September:
+1. Define f: \N -&gt; \N by f(x) = x^2 + x;
+i.e., consider the function from \N={0,1,2,3,...} to \N
+that has elements (x,x^2+x).
+Is f one-to-one? Is f onto?
+2. Give an example of an onto function from {1,2,3,4} to {3,4,5}.
+Give an example of an injective function from {3,4,5} to {1,3,5,7,9}.
+3. Find a bijection from {0,1,2,3,4,...} to {...,-2,-1,0,1,2,...}.
+4. Prove: If {{a},{a,b}} = {{c},{c,d}} then a = c and b = d.
+(Side note: Some people define the pair (a,b) as {{a},{a,b}}.)
+<p>
+Wednesday's class material:
+View of function from S to T as a rule specifying, for each element of S,
+an element of T.
+Warning: two different-sounding rules can be the same function.
+Functions f, g are equal iff they are equal as sets.
+These three functions from {1,2,3} to \N = {0,1,2,...} are equal to each other:
+the function {(1,2),(2,4),(3,6)};
+the rule specifying, for each element x of {1,2,3}, the number 2x;
+the rule specifying, for each element x of {1,2,3},
+the number sqrt(3x^2 + x(x-1+1)).
+View of function from S to T as a table.
+Warning: reordering table doesn't change function.
+View of function from S to T as a graph.
+Can also graph relations.
+The notation f(x) for the unique y such that (x,y) is in f.
+``Argument'' is function input.
+``Value'' is function output.
+f:S-&gt;T means that f is a function from S to T.
+Example:
+``Define f:{1,2,3}-&gt;\N by f(x)=x^2''
+is a standard way to define the function {(1,1),(2,4),(3,9)}.
+Another example:
+``Define f:\N-&gt;\N by f(x)=x/2 if x is even, 3x+1 if x is odd.''
+This example is surjective, not injective, not bijective.
+Composition of functions:
+if f is a function from S to T,
+and g is a function from T to U,
+then gf is the function from S to U
+such that (gf)(x) = g(f(x)) for each x in S.
+Examples.
+<p>
+Today's class material:
+Let f be a function from S to T.
+The domain of f is the set of first components of elements of f;
+i.e., the domain of f is S.
+The image of f is the set of second components of elements of f;
+this is a subset of T.
+The codomain of f is T;
+beware that codomain, like surjectivity, does not depend on f alone.
+The range of f is the codomain of f;
+beware that some people instead define range as image.
+The inverse image set of y under f
+is the set of x's such that (x,y) is in f.
+``Inverse image'' means ``inverse image set.''
+The coimage of f is the set of nonempty inverse image sets under f.
+Example: the function {(1,5),(2,4)} from {1,2} to {4,5};
+domain, image, codomain, range, various inverse images;
+coimage is {{2},{1}}.
+Example: the function {(1,6),(2,5),(3,5),(4,6)} from {1,2,3,4} to {5,6,7,8};
+domain, image, codomain, range, various inverse images;
+coimage is {{1,4},{2,3}}.
+The coimage of f is a partition of S.
+Definition of partition.
+Example: All partitions of {1,2,3,4}.
+All partitions of S are coimages of various functions.
+``Equivalence relations'':
+can convert a partition into a relation from S to S;
+can recognize from ``transitivity'' etc.
+whether a relation from S to S is obtained from a partition.
+<p>
+Practice exam due Friday 16 September:
+1. What is the domain of the function f:\N-&gt;\N
+defined by f(x) = x/2 for x even
+and f(x) = 3x+1 for x odd?
+What is the codomain? What is the coimage?
+2. Simplify the Boolean function
+(p v q) v ((q v (~r)) ^ (p v r))
+as far as possible;
+i.e., write the shortest formula for it.
+3. Write a truth table for (p ^ (p =&gt; q)) =&gt; q.
+Here p=&gt;q is defined as q v (~p).
+4. Simplify the Boolean function
+((p ^ (~q)) =&gt; r) =&gt; (p =&gt; (q v r))
+as far as possible.
+<p>
+<b>The first exam will be Monday 19 September.</b>
+It will cover sets, functions, and Boolean functions.
 </body>
 </html>
diff -ru .old-crypto/2005-501.html cr.yp.to/2005-501.html
--- .old-crypto/2005-501.html	2005-08-31 17:29:56.000000000 -0400
+++ cr.yp.to/2005-501.html	2005-09-09 22:40:41.000000000 -0400
@@ -160,5 +160,74 @@
 Reality.
 Example: Schimmler sort.
 Example: dual-core CPUs.
+<h2>9 September 2005</h2>
+Please read Chapter 30 of the textbook: fast Fourier transforms.
+<p>
+Class material from last Friday:
+How expensive is addition of two n-bit integers
+in the usual binary representation,
+producing an (n+1)-bit integer
+in the usual binary representation?
+Answer depends on addition machine and cost measure.
+First cost measure: number of instructions;
+``time'' in a baby algorithms course.
+Algorithm performing Theta(n) instructions.
+Second cost measure: wall-clock time, i.e., real time.
+Previous algorithm takes time n^(1.5+o(1)).
+Pipelined algorithm takes time n^(1+o(1)).
+Third cost measure: circuit depth.
+Converting carry-chain recurrence to product of many matrices.
+Parallel multiplication of many matrices.
+<p>
+Class material from Wednesday:
+Example of integer addition.
+Matrix view of same example.
+Simplest algorithm taking depth n^(o(1))
+is very bad in other cost measures:
+number of instructions, mesh price-performance ratio, etc.
+Fourth cost measure: circuit gates times circuit depth.
+Serial algorithm has cost n^(2+o(1)).
+Parallel algorithm has cost n^(2+o(1)).
+Example for n=6.
+Better parallel algorithm, merging intermediate results.
+Cost n^(1+o(1)); exponent 1 is optimal.
+Constant factors: look up ``parallel prefix.''
+Increasing cost measure
+by expanding circuit depth to circuit delay,
+accounting for distance in circuit;
+raises cost to n^(3/2+o(1)).
+Further increasing cost measure
+by expanding number of gates to length of wires,
+accounting for price of wiring;
+again cost n^(3/2+o(1)).
+Mesh price-performance ratio is also n^(3/2+o(1)).
+<p>
+Today's class material:
+Why use price-performance ratio, i.e., price-time product?
+Minimizing time without regard to price is unrealistic.
+But why price-performance ratio
+rather than price + time, for example, or price time^2,
+or some other combination?
+Using price-performance ratio as cost has two nice features:
+k independent computations in serial are, together,
+k times as expensive as one computation;
+and k independent computations in parallel are, together,
+k times as expensive as one computation.
+Can also graph (price,time) pairs.
+Advantages and disadvantages of various time measures.
+Advantages and disadvantages of various price measures.
+Back to addition:
+can reduce mesh price-performance ratio to n^(1+o(1))
+by changing the problem,
+using redundant representation of integers.
+Moving on to integer multiplication:
+How expensive is multiplication of two n-bit integers
+in the usual binary representation,
+producing a 2n-bit integer
+in the usual binary representation?
+Simple solution, n^{2+o(1)} instructions:
+multiply each bit of the first integer u
+by the second integer v, and add the results.
+5-bit example.
 </body>
 </html>