Question of the Day: you have two jars, 50 red marbles, 50 blue marbles. you need to place all the marbles into the jars such that when you blindly pick one marble out of one jar, you maximize the chances that it will be red. (when picking, you’ll first randomly pick a jar, and then randomly pick a marble out of that jar) you can arrange the marbles however you like, but each marble must be in a jar.
Question: How to add an array of numbers in parallel?
a) Give an O(log n) time, O(n) work EREW algorithm, which, given a boolean array A of size n, finds the smallest index k such that A[k] = 1. You may assume that such a k exists. Also, your solution should not change array A (i.e. you will need to do any computation in another array).
b) Give an O(1) time, O(n2) work common CRCW algorithm for the same problem.
Algorithms vs. AI
1) An MP3 player is loaded with 60 songs: 30 rock songs, 15 jazz songs, and 15 blues songs. The player is supposed to be on “random play”, so songs are played randomly with equal probability (and they can be repeated). However, the first four songs all turn out to be blues. What is the probability that the first four songs are all blues, assuming that the player is on random play?
2) In the United States, 80% of people wear a seat belt while driving. (a) if two people are chosen at random, what is the probability that both of them wear a seat belt? (b) if two people are chosen at random, what is the probability that at least one of them wears a seat belt? (Hint: you could make use of the addition rule for overlapping events, or you could make use of of the rule for the probability of “not-A”)
3) What is the expected profit of buying a ticket for each of the following lotteries, and if you would have to choose one, based on expected profit, which one would it be? (By “expected profit” we mean the expected value of the profit) Lottery A: Tickets cost $10. You have 1% chance to win $500, and 99% chance to win nothing. Lottery B: Tickets cost $15. You have 2% chance to win $400 and 98% to win nothing.
Deck of Card Exercise