[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.


1. A mean statistics problem

  1. You are asked to find the typical temperature for a particular time of year centered around day 0. Suppose you have collected daily high temperatures x-n...xn for 2n+1 days in a row (with x0, the day 0 temperature, in the middle), but you are only allowed to report one "typical" temperature y. You will be punished for deviation from the typical temperature according to the formula p = ∑i (xi-y)². Given an explicit formula for the value of y that minimizes p.

  2. Now suppose you are allowed to include a predicted daily increment z, so that the guess for day i is now y+iz. Give an explicit formula for the values of y and z that between them minimize p = ∑i (xi - (y+iz))².

2. Equivalence relations and functions

Let f:A→B be some function.

  1. Show that the relation ~f, given by the rule x~fy if and only if f(x) = f(y), is an equivalence relation.

  2. Show the converse: if ~ is an equivalence relation on A, there exists a set B and a function f:A→B such that x~y if and only if f(x) = f(y).

3. Partial orders

Let A = ℕk be the set of all sequences of natural numbers of length k. Given two elements x and y of A, let x≤y if and only if xi≤yi for all i.

  1. Prove (by showing reflexivity, antisymmetry, and trasitivity) that ≤ as defined above is a partial order on ℕk.

  2. Give examples of choices of k for which ≤ is/is not a total order.
  3. Prove that (ℕk, ≤) contains no infinite descending chain, i.e. there is no infinite sequence a0, a1, a2, ..., where ai+1 < ai for all i.

  4. Now consider the set ℕ of all infinite sequences of natural numbers, where x ≤ y is defined to mean xi ≤ yi for all i∈ℕ. Prove or disprove: (ℕ, ≤) contains no infinite descending chain.

4. Lattices

  1. Prove or disprove: In any lattice, x∨(y∧z) = (x∨y)∧(x∨z).
  2. Prove or disprove: In any lattice, x≥y ⇒ x∧(y∨z) = (x∧z)∨y.

2014-06-17 11:57