Some Intellectual Material

The list below shows some of the writeup's you might like to read about. Since they have been categorized, you might find some repeated entries. Since I would like to know how many and who are interested in this stuff, you have to send an email to me to get the stuff.

Almost all the questions answered in the Mathematics section was posed by somebody else. In some cases I solved them (writeup = my solution) and in others I found out the solution (writeup = my typing of solution). To explain the problem I use LaTeX notation. Many solutions came about after discussion with my advisor and other students.

If you have any such material or interesting questions, send me an email at  gmkrishn@cs.uchicago.edu .

  • Pure and Applied Logic
  • Computer Science - Systems
  • Temporal Logic in Hardware Verification: Formal verification is one of the methods used to verify circuits. This writeup  (my project for the Computer Architecture course), discusses how to express correctness specification for circuits in Temporal Logic. Assumes basic knowledge of Boolean Logic. If you have no idea about how logic can be used for circuit verification go ahead and read this - 14 Pages. Request
  • A not so gentle introduction to Databases: Some lecture notes, I prepared for a course which I did not teach. Covers Relational Databases, SQL. Probably a bit fast paced. Not complete. Request
  • Mathematics
  • Ultraproducts of finite fields: Given a countable collection of finite fields F_i, and a measure \mu on the indexing set we can define their ultraproduct F. The fundamental theorem relating F to the F_i's is that "any field theoretic statement" \phi holds for F iff \mu({i : \phi fails for F_i}) = 0. This writeup discusses if we can contruct the complex numbers, real numbers etc. by this kind of contruction. Requires some background on field extensions - 16 pages. Request
  • Set Theory: Problem 1 - Given a countable set $X$. Contruct (with the help of Axiom of Choice) an uncountable collection of subsets of $X$, such that the pairwise intersection of the collection is finite.  Problem 2 - Fix a countable universe $X$. Given a countable collection of countable sets closed under finite intersections and super sets, construct (without Axiom of Choice) a set $R$ such that neither $R$ nor its complement is in this collection. Request
  • Probability: The problem goes like this. Let [n] be a set with $n$ elements. Fix any collection G of subsets of [n]. Let W be a weight function, where weights are integers between 1 and m. Then the probability (over all W) that G's minimum weight set is unique is atleast 1 - \frac{n}{2m}. This result has a name associated with it.  Request
  • Polynomials: This problem was given in an undergraduate course in Analysis. The problem is to classify all polynomials which map rationals to rationals and irrationals to irrationals. Atleast one solution is quite elementary. Sleep on this problem for atleast a week before reading the solution. To understand the non-elementary solution, you should be comfortable with ... oops I almost gave away the solution. Request
  • Computer Science - Theory
  • Minimum Distance Problem: Given a finite set X with n elements, and a number m < n. Find a set Y with m elements such h(X,Y) is minimised. h(X,Y) = max d(x,Y) over x \in X, and d(x,Y) = min d(x,y) over y \in Y. Here d refers to the distance between x and y. This writeup solves the problem if the space is the real line, and some insights are provided for higher dimensional euclidean spaces. Knowledge of basic mathematics is enough to read this.  Request
  • Parallel Tower of Hanoi Problem: This writeup suggests a parallel version of the tower of hanoi problem, and gives an almost optimal solution (optimal within a factor of 1.5). As usual we have three sticks and $n$ disks of various sizes. All the disks are on one stick, and we have to transfer it to any of the other stick, observing size restrictions. In each legal move, more than one disk can be moved. However, two or more disks cannot leave a stick and two or more disks cannot land on a stick during the move. How long does it take to move the disks? Sleep on this problem for some time. Who knows you may come up with the optimal solution.  Request
  • Have fun with these problems!