cr.yp.to update

 2005-261.html |   18 ++++++++++++++++++
 2005-501.html |   20 ++++++++++++++++++++
 2 files changed, 38 insertions(+)
diff -ru .old-crypto/2005-261.html cr.yp.to/2005-261.html
--- .old-crypto/2005-261.html	2005-08-29 05:09:01.000000000 -0400
+++ cr.yp.to/2005-261.html	2005-08-31 17:25:17.000000000 -0400
@@ -237,5 +237,23 @@
 Adequately detailed answer: ``Disproof: Define A = {1} and B = {2}.
 Then A union B = {1,2},
 so (A union B) union B = {1,2} != {1} = A.''
+<h2>31 August 2005</h2>
+Class material from Monday: Venn diagrams, and special Venn diagrams.
+<p>
+Today's class material:
+Statement involving set names, union, intersection, minus, equal, subset
+is true for all sets if and only if it's true for special Venn diagram.
+Example: Venn proof that S intersect T is a subset of T.
+Example: Venn proof that (X-S) intersect (X-T) = X - (S union T).
+For comparison, non-Venn proof.
+Picture of non-Venn proof.
+Using Venn diagrams to disprove ``T - S is a subset of S,''
+i.e., to disprove ``for every set S: for every set T: T - S is a subset of S.''
+Example where T - S is a subset of S.
+Set product (Cartesian product):
+S x T is the set of strings (a,b) where a is in S and b is in T.
+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).
 </body>
 </html>
diff -ru .old-crypto/2005-501.html cr.yp.to/2005-501.html
--- .old-crypto/2005-501.html	2005-08-29 05:37:25.000000000 -0400
+++ cr.yp.to/2005-501.html	2005-08-31 17:29:56.000000000 -0400
@@ -140,5 +140,25 @@
 such as divide-and-conquer and dynamic programming.
 </ul>
 Research directions after the prerequisite course.
+<h2>31 August 2005</h2>
+Class material from Monday:
+This is not a course about constant factors.
+This is not a course about mathematical methods of algorithm analysis.
+This course will consider more computational problems.
+This course will consider more cost measures.
+Examples of algorithm cost measures.
+Will prove that n steps of odd-even transposition sort are enough for n numbers.
+Enough to prove that small numbers come before large numbers.
+Enough to prove that all arrays of 0's and 7's are sorted.
+Inductive proof, case 1: last number is a 7.
+Inductive proof, case 2: last number is a 0.
+<p>
+Today's class material:
+Schimmler sort on typical balanced array of 0's and 7's.
+Schimmler sort on typical unbalanced array of 0's and 7's.
+The parallel price-performance myth.
+Reality.
+Example: Schimmler sort.
+Example: dual-core CPUs.
 </body>
 </html>