Grading 354, listening to "Time Out". Nice album. Grading still sux0rz, however. At least people really nailed a few of the problems on this homework, though. One guy had a slick way of proving every function 2^n -> 2 is encodable via a polynomial over Z_2 over the variables x_1 ... x_n: Sort all possible input vectors lexicographically. Start with the polynomial 0. Go through all the possible input vectors. Say you're looking at b_1b_2...b_n. Check whether your polynomial gives the right answer. If it doesn't, just tweak it by adding the term x_1^(b_1)x_2^(b_2)...x_n^(b_n). This can't possibly fuck up any previous answer because you iterated over input vectors in lexicographic order; any previous vector has a zero in some position where the currect vector has a one. QED.
