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.

Parallel Processing

• CREW
• EREW
• CRCW

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.

Parallel Algorithms Answer

Databases

• MySQL
• http://sqlfiddle.com/

Algorithms vs. AI

• Problem Solving
• Framing
• Intentionality
• What if P = NP?
• Dynamic thinking
  • Models (Parallel Processing)

Proofs

• Induction
• Recurrence

Candy Exercise

• Autonomy and Agency
• Think less thermometer and more thermostat

Game Theory

• Dominant Strategy
• Nash Equilibrium
• Socially Optimal
• (Pareto Optimal)

Page Rank

Auctions

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.

http://math.elon.edu/statistics112/probability.html

Deck of Card Exercise

• Bayes Rule
• http://en.wikipedia.org/wiki/Bayes'_theorem

My notes:

• Game Theory: http://cmps17.pbworks.com/w/page/52747360/Game%20theory%20exercises%20with%20solutions
• Road, Page, Bayes: http://cmps17grading.pbworks.com/w/file/fetch/53886576/midterm2-rubric.pdf
• Auction: http://cmps17grading.pbworks.com/w/file/fetch/53649246/CMPS17Homework4Rubric.pdf

https://www.youtube.com/watch?v=sno1TpCLj6A

language model

• say we are reading a bunch of text, and want to determine the language
• every language has a characteristic letter frequency
• not perfect, languages change over time
• this is exploited by cryptography, for example, to break simple substitution
  • english 13%e, 9%t, 8%a
  • spanish 13%a, 14%e, 9%o
  • german 17%e, 10%n, 8%i
• should be able to tell the difference between these?
• how? what would you do to take a whole bunch of text, then decide which language you were in?

Information Mining

LaTeX

Field Trip

• Tuesday Meetings
• Journal 6
• Assignment 6
• Feedback