Suppose I wanted to use a perceptron to decide whether I wanted the lights on or not. The input to the perceptron is the hour of the day, based on a twenty-four-hour timescale, in five-digit binary notation. (We will omit any concern with minutes or seconds.) For instance, if it is 9:XX AM, the input is 01001 (i4=0, i3=1, i2=0, i1=0, i0=1), and if it is 4:XX AM, the input is 10000. The output is either 0 (lights off) or 1 (lights on).

I want the lights off from 7:XX AM to 3:XX PM, (accompanying my normal sleeping schedule,) and on otherwise.

Design a five-input perceptron for me, by providing the weghtings w4, w3, w2, w1, w0 for the inputs i4, i3, i2, i1, i0 along with a threshold value t. Remember, our inputs are either 0 or 1.

Recall the Minimax game-playing algorithm that we read about in Harel Chapter 12 and discussed in class. Design a board evaluation function (a utility function) for either (a) chess (b) go, or (c) othello that can be used in a minimax algorithm. You need not write a scheme function, rather, simply describe the algorithm that comprises your utility function. Remember, a utility function takes in a board configuration and returns a numerical value. Discuss the advantages and weaknesses of your utility function. If you honestly don't know how to play any of the games listed, let me know, BEFORE the due date.

An estimation, in the spirit of Hofstadter Chapter 11. Read about the corporate promo of the mir impact, in particular the comment about the insurance.

1. Approximately, what might the cost of the free tacos actually be, if the event occurred today, and the target were hit? Make reasonable approximations, and mention what they are. There are approx. 287 million americans.

2. What is the likelihood (at the time the campaign was started), that target is hit? Assume that mir might hit anywhere in a 10,000km by 200km swath, with equal probability; also assume that the core of mir is a sphere 8m in diameter (a crude equivalence based on the core being a 13m by 4m(?) rectangle). You may assume the target is a circle with a diameter of 12m. (Hint: Just concentrate on the central point of the core -- how far away from the center of the target would it have to be, to touch a circular target at all?)

3. What is the expected ("average") cost of this offer, to the insurance company? (Just multiply the two previous numbers.) (Good insurance companies usually charge about 45% more than the expected costs, to cover the overhead of running a business, plus covering reasonable protection for cash-flow exigencies.)

4. We've estimated the immediate costs of the offer (the insurance company's point of view). This seems to say that Taco Bell is out the money they paid the insurer, and whether or not the target is hit they are insulated from any costs/gains. But Taco Bell ain't dumb, they don't support insurance companies for no reason. What does Taco Bell expect to get out of the whole thing, if the target is hit? If not? (These answers aren't numeric, and there are a lot of things a MANA student might think of; just list one or two that come to mind.)

(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 all that full-blown machinery.)

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.

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.)
   3. Exactly three rolls? (probability of a inconclusive roll, times probability of a(nother) inconclusive roll, times the probability of a conclusive one).
   4. Exactly four rolls?
   5. Four or fewer rolls? (That's just the sum of the above probabilities, since the above outcomes are non-overlapping.)

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.)

4. Optional: Extra credit for algebra fans: compute the expectation (i.e., the infinite sum). Show your work.

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?