Comp 200                 Homework 6 (jelly2000, circuits)                

1. (4pts) Tonight is family-style dinner, and you and two friends want to plan in advance who will go and get the food, over e-mail. You offer to roll a die (with say, 1-2 means you get the food, 3-4 Chris does, 5-6 Kim does), and them e-mail them the result of the die roll, but for some reason they don't trust you. But y'all've just read Harel Chpt. 11's "Playing poker over the phone", so you figure it's possible to jointly choose a food-getter, in such a way that you're all satisfied the choice was indeed random.
   How? Describe your algorithm precisely. Does this protocol still work if two people might try to collude? (It's okay if it doesn't.)

   (You can use a public-key crypto system if you like (taking for granted how to encrypt/decrypt), though there are simpler solutions which don't need that full-blown machinery.)

   |On hw6 prob 1, may we assume that no two people will gang up and try to
   |trick the third, or do we have to prevent this possibility with our
   |algorithm?
   |
   Aha, excellent question!
   You can answer the question either way you like: 
   (a) that your friends would never actively conspire [easier], or
   (b) that people might conspire, so you need to find a protocol
       which people will trust can't be rigged, even by conspiracies.
       (If you need to make reasonable assumptions -- eg that you can
       trust e-mail headers, etc -- that's fine, but you should
       explicitly mention such assumptions.)
   
   I'd had the easier version (a) in mind, when i wrote the problem.
   

   [an error occurred while processing this directive]

2. (5pts) In class we saw some randomized algorithms (e.g. checking primality) which ran quickly, but occasionally (with a small probability) gave a wrong answer. For such an algorithm to be useful, we had to argue that the chance of an error was very small. Such algorithms are called "Monte Carlo" algorithms.

   But we can also have "Las Vegas" algorithms which are always correct, but occasionally slow. For these algorithms to be useful, we want to argue that the chance of being incredibly slow is small. This problem aims you at a Las Vegas algorithm, and then discusses the probability of it being slow:

   You and Kim and Chris are now at dinner, and you realize that in all your excitement about how to solve the previous problem, you forgot to actually carry out the solution. So now you can decide in person who will pick up the dinner. If you had a 6-sided die, this wouldn't be a problem. However, all you have is a 4-sided die. You can't use the approach "a roll of 1 means me, 2 means Chris, and 3 or 4 means Kim", since Kim balks at her being more likely to be chosen than the others.

   1. What is a (simple) procedure so that you can randomly choose? Hint: you can consider some rolls as "inconclusive", and re-roll them.

      [an error occurred while processing this directive]

   2. Note that this algorithm always gives an answer (it always decides on a person, eventually), but could take a long time. We want to argue that it's still a good algorithm -- that the chance it requires more than (say) 4 rolls is quite small. Towards such a claim:

      1. What is the probability that only one roll is required?
      2. Exactly two rolls? (That is, the probability the first roll is inconclusive, times the probability that the second roll is conclusive.) [an error occurred while processing this directive]
      3. Exactly three rolls? (probability of a inconclusive roll, times probability of a(nother) inconclusive roll, times the probability of a conclusive one). [an error occurred while processing this directive]
      4. Exactly four rolls? [an error occurred while processing this directive]
      5. Four or fewer rolls? (That's just the sum of the above probabilities, since the above outcomes are non-overlapping.) [an error occurred while processing this directive]
   3. The average ("expected") number of rolls needed is the infinite sum:

        1*(probability of exactly 1 roll)
      + 2*(probability of exactly 2 rolls)
      + 3*(probability of exactly 3 rolls)
      + 4*(probability of exactly 4 rolls)
      + ....
      

      Compute the sum of just the first four terms. (While each successive term is getting smaller, it's the mathematician's question, to determine whether the first four terms dominate the next million, much less all the rest.) [an error occurred while processing this directive]
   4. Optional: Extra credit (1pt) for algebra fans: compute the expectation (i.e., the infinite sum). Hint available. [an error occurred while processing this directive]

   5. Now suppose you don't have a four-sided die, but just a coin. How can you still randomly choose one of the three of you? (I.e., reduce die-rolling to coin-flipping.) Presuming the previous algorithm really was efficient (meaning, unlikely to take a huge number of die-rolls), is your solution to this efficient?

      [an error occurred while processing this directive]
3. (2pts) Write a Jelly2000 program which multiplies the two numbers stored in memory locations 2001 and 2004 respectively, and stores the result in memory location 2010. Show the contents of these memory locations, then run the program, and again show the contents of these memory locations. [an error occurred while processing this directive]

   Then, run your program in the Jelly2000 Machine Inspector. (You'll want your program in a separate file, for this.)

   Some questions/answers from a previous semester: what does "bad instruction 0" mean?; placing constants into memory.

4. (5 pts) Write a Jelly2000 program which sums the squares of odd numbers between 1 and N, where N is provided in memory location 321. That is, calculate 1²+3²+5²+...+N². (Note that the reference sheet already contains a program to compute 1+2+3+...+N.) As above, run your program with Jelly2000 Machine Inspector to check your work.
   [an error occurred while processing this directive]

   Alternately: you can compute the sum: 1 - 1/3 + 1/5 - 1/7 + 1/9 - ..., for N terms or so, and multiply the result by four. (There are better ways to calculate pi, though.) Okay, Jelly2000 doesn't have fractions, so you instead can mutliply each term in the series by K (with perhaps K being 100,000 or so), and compute K*pi (or at least, an integer near K*pi). You can base one of your projects on calculating pi several ways, in Scheme and/or Jelly2000, along with a 1-2 page write-up of your approach.

5. (3pts) Circuit to compare numbers.
   1. Draw a circuit (using AND, OR, and NOT gates) which has two input wires a and b, and one output wire which is 1 if and only if a = b (that is, the output is one iff ((a is 0 and b is 0), or (a is 1 and b is 1))).

      Remember the :pproach to writing circuits: first go to an english description using only the words "and","or","not", and any other circuits we know of; hopefully you can transliterate that description directly into a circuit. (For this problem, i've already tacked on with the suitable english description.)

      [an error occurred while processing this directive]
   2. Intel has taken the circuit you just created, and mass-produced it as a new gate, EQ. Draw a circuit which takes two four-bit data (a₁,a₂,a₃,a₄ and b₁,b₂,b₃,b₄) as input, and outputs 1 iff each a_i = b_i (for i = 1,...,4). You may use AND, OR, NOT, and EQ gates.
      [an error occurred while processing this directive]
6. (5pts) Consider an "if" circuit, which has three inputs: a "choice" c, and two other inputs i₁, and i₂ (each of these being on/off (+0V/+5V)). There is one output, which computes (if c i1 i2). That is, were you to replace 0/1 with false/true, the desired "if" circuit gives the same answer as the scheme function "if". (Of course, scheme's if isn't restricted to *just* having booleans for i₁ and i₂, as we are in this circuit version.)
   1. Example: what should the output wire be, when the input wires are 0,1,1? When the are 1,0,1? [an error occurred while processing this directive]
   2. Give an English sentence, which describes when the output wire should be on (+5V), using "and", "or", "not", "c", "i₁", and "i₂", but not using the word "if". [an error occurred while processing this directive]
   3. Design the circuit, based on the sentence from the previous part. ² [an error occurred while processing this directive]
   4. (Extra Credit 4pts) Generalize this to a circuit with six inputs: Two "choice" inputs, c₁, c₀ and four inputs i₀, i₁, i₂, i₃.

      The two "choice" inputs are to be regarded as a two-bit numeral, c₁c₀. The single output should be the same as the input named by this two-bit numeral.

      For example, were [c₁,c₀] to be [1,0] (decimal "2"), then the output should be whatever value i₂ is.

      This circuit is called a two-bit multiplexor. You can see now, that it can acheive the effect of loading a value from memory: If our memory were only four bits (i₀ through i₃), then the two control lines c₁c₀ name an address, and this multiplexor circuit outputs the desired bit of memory! (The if circuit above can be viewed as a one-bit multiplexor.)

      If our memory consisted of four 8-bit quantities (instead of four 1-bit quantities), how could we combine a bunch of multiplexors to retrieve the desired eight bits?

      This problem can be parlayed into a final project.

7. (1pt) State what your project will be: either, what task or program you will describe or write, or (if doing a paper) formulate a precise question which your project will answer. (If you are not doing a project, please say so.)

² Note that the parts of this program are the first steps of the design recipe for programs: give example test cases, and write down the english comment for the function. This isn't coincidence; circuits are just another programming language. (back)