Difference between pages "Chapter 1" and "2.55"

Latest revision as of 19:41, 10 September 2020

This problem is a famous game-theoretical scenario called the pirate game (http://en.wikipedia.org/wiki/Pirate_game). Assume the senior pirate gets to vote.

Where there is only 1 indivisible dollar: 2 pirates - The senior pirate gets it. 3+ pirates - The least senior pirate gets it.

In general, every 2 + 2^K (k >= 1) pirate will survive, while the others will die

Another Answer : Assume senior pirate also gets to vote.

Based on pirates inherent tendency -

a. They want to kill other pirates even if it does not affect their outcome -

2 pirates: Senior gets it.

3 pirates: Least-senior pirate gets it because the 2nd-least-senior pirate will vote for kill; so in order to live, he/she must give the gold to the least-senior pirate.

4 pirates: 2nd or 3rd-least-senior pirate will get gold (equally likely) because 1st will vote for kill irrespective of whether he/she gets the gold or not, and the 2nd or 3rd-least-senior pirate will vote for the plan if he/she gets the gold respectively.

5 pirates - This pirate is certainly going to die regardless of his/her proposal since there will be at least 3 pirates that don't get the gold and thus vote to kill him/her. This will eventually lead to the above situation where the 2nd or 3rd-least-senior pirate will receive the gold.

6 pirates: The 5th-least-senior pirate will vote for whatever plan the most senior pirate proposes—if the proposal falls down to him/her, then he/she is guaranteed to die as explained above. In order to get the last vote, the most senior pirate can give the gold to any of the remaining four pirates. The reason for each is below—recall, the desire to have the gold surpasses the desire to kill another pirate (e.g., if Pirate A has a 50% chance of getting the gold without killing anyone vs. a 49% chance of getting the gold and killing everyone else, he/she will choose the former):

• 4th-least-senior pirate: would agree to receive the coin, because as mentioned before, if the 5th-least-senior pirate decides, he/she will die. This will eventually result in this pirate having to give away the coin in order to live as described in the "4 pirates" situation.

• 3rd-least-senior pirate: would agree to receive the coin since there would only be a 50% chance he/she would get it as described in the eventually inevitable "4 pirates" situation.

• 2nd-least-senior pirate: same reasoning as above.

• Least senior pirate: the least senior pirate would agree to receive the coin since he/she would have a 0% chance to receive the gold as described in the eventually inevitable "4 pirates" situation.

Thus the result would be that no one dies and either the first, second, third, or fourth-least-senior pirate would receive the coin.

b. They want as many other pirates to live if it doesn't affect their outcome -

Senior most pirate gets the gold.

Back to Chapter 2

@@ Line 1: / Line 1: @@
-=Introduction to Algorithms=
+This problem is a famous game-theoretical scenario called the pirate game (http://en.wikipedia.org/wiki/Pirate_game). Assume the senior pirate gets to vote.
-===Finding Counter Examples===
+Where there is only 1 indivisible dollar:
+pirates - The senior pirate gets it.
++ pirates - The least senior pirate gets it.
-:[[1.1]]. Show that <math>a + b</math> can be less than <math>\min(a,b)</math>.
+In general, every 2 + 2^K (k >= 1) pirate will survive, while the others will die
+'''Another Answer''' :
+Assume senior pirate also gets to vote.
-:1.2. Show that <math>a \times b</math> can be less than <math>\min(a,b)</math>.
+Based on pirates inherent tendency -
+'''a.''' They want to kill other pirates even if it does not affect their outcome -
-:[[1.3]]. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the fastest route between <math>a</math> and <math>b</math> is not the shortest route.
+pirates:  Senior gets it.
+pirates: Least-senior pirate gets it because the 2nd-least-senior pirate will vote for kill; so in order to live, he/she must give the gold to the least-senior pirate.
-:1.4. Design/draw a road network with two points <math>a</math> and <math>b</math> such that the shortest route between <math>a</math> and <math>b</math> is not the route with the fewest turns.
+pirates: 2nd or 3rd-least-senior pirate will get gold (equally likely) because 1st will vote for kill irrespective of whether he/she gets the gold or not, and the 2nd or 3rd-least-senior pirate will vote for the plan if he/she
+gets the gold respectively.
+pirates - This pirate is certainly going to die regardless of his/her proposal since there will be at least 3 pirates that don't get the gold and thus vote to kill him/her. This will eventually lead to the above situation where the 2nd or 3rd-least-senior pirate will receive the gold.
-:[[1.5]]. The ''knapsack problem'' is as follows: given a set of integers '<math>S = \{s_1, s_2, \ldots, s_n\}</math>, and a target number <math>T</math>, find a subset of <math>S</math> which adds up exactly to <math>T</math>.
+pirates: The 5th-least-senior pirate will vote for whatever plan the most senior pirate proposes—if the proposal falls down to him/her, then he/she is guaranteed to die as explained above. In order to get the last vote, the most senior pirate can give the gold to any of the remaining four pirates. The reason for each is below—recall, the desire to have the gold surpasses the desire to kill another pirate (e.g., if Pirate A has a 50% chance of getting the gold without killing anyone vs. a 49% chance of getting the gold and killing everyone else, he/she will choose the former):
-For example, there exists a subset within <math>S = \{1, 2, 5, 9, 10\}</math> that
-adds up to <math>T=22</math> but not <math>T=23</math>.
-Find counterexamples to each of the following algorithms for the knapsack
-problem.
-That is, giving an <math>S</math> and <math>T</math> such that the subset is
-selected using the algorithm does not leave the knapsack completely full,
-even though such a solution exists.
-#Put the elements of <math>S</math> in the knapsack in left to right order if they fit, i.e. the first-fit algorithm.
-#Put the elements of <math>S</math> in the knapsack from smallest to largest, i.e. the best-fit algorithm.
-#Put the elements of <math>S</math> in the knapsack from largest to smallest.
+• 4th-least-senior pirate: would agree to receive the coin, because as mentioned before, if the 5th-least-senior pirate decides, he/she will die. This will eventually result in this pirate having to give away the coin in order to live as described in the "4 pirates" situation.
-:1.6. The ''set cover problem'' is as follows: given a set ''S'' of subsets ''S1, . . . , Sm'' of the universal set ''U'' = {1, ..., ''n''}, find the smallest subset of subsets ''T ⊆ S'' such that ''∪ti∈T ti'' = ''U''. For example, consider the subsets ''S1'' = {1, 3, 5}, ''S2'' = {2, 4}, ''S3'' = {1, 4}, and ''S4'' = {2, 5}. The set cover of {1, . . . , 5} would then be ''S1'' and ''S2''.
+• 3rd-least-senior pirate: would agree to receive the coin since there would only be a 50% chance he/she would get it as described in the eventually inevitable "4 pirates" situation.
-:Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.
+• 2nd-least-senior pirate: same reasoning as above.
-:[[1.7]]. The ''maximum clique problem'' in a graph ''G'' = (''V'', ''E'') asks for the largest subset ''C'' of vertices ''V'' such that there is an edge in ''E'' between every pair of vertices in ''C''. Find a counterexample for the following algorithm: Sort the vertices of ''G'' from highest to lowest degree. Considering the vertices in order of degree, for each vertex add it to the clique if it is a neighbor of all vertices currently in the clique. Repeat until all vertices have been considered.
+• Least senior pirate: the least senior pirate would agree to receive the coin since he/she would have a 0% chance to receive the gold as described in the eventually inevitable "4 pirates" situation.
+Thus the result would be that no one dies and either the first, second, third, or fourth-least-senior pirate would receive the coin.
-===Proofs of Correctness===
+'''b.''' They want as many other pirates to live if it doesn't affect their outcome -
-:1.8. Prove the correctness of the following recursive algorithm to multiply two natural numbers, for all integer constants ''c'' ≥ 2.
+Senior most pirate gets the gold.
-::Multiply(''y, z'')
-:::''if z'' = 0 ''then'' return(0) ''else''
-:::return(Multiply(''cy'', [''z/c'']) + ''y'' · (''z'' mod ''c''))
-:[[1.9]]. Prove the correctness of the following algorithm for evaluating a polynomial ''anxn + an−1xn−1 + · · · + a1x + a0''.
+Back to [[Chapter 2]]
-::Horner(''a, x'')
-:::''p'' = ''an''
-:::for ''i'' from ''n'' − 1 to 0
-::::''p'' = ''p · x'' + ''ai''
-:::return ''p''
-:1.10. Prove the correctness of the following sorting algorithm.
-::Bubblesort (''A'')
-:::for ''i'' from ''n'' to 1
-::::for ''j'' from 1 to ''i'' − 1
-:::::if (''A''[''j''] > ''A''[''j'' + 1])
-::::::swap the values of ''A''[''j''] and ''A''[''j'' + 1]
-:[[1.11]]. The ''greatest common divisor of positive'' integers ''x'' and ''y'' is the largest integer ''d'' such that ''d'' divides ''x'' and ''d'' divides ''y''. Euclid’s algorithm to compute gcd(''x, y'') where ''x'' > ''y'' reduces the task to a smaller problem:
-:::::gcd(''x, y'') = gcd(''y, x'' mod ''y'')
-:Prove that Euclid’s algorithm is correct.
-===Induction===
-:1.12.
-:[[1.13]]
-:1.14
-:[[1.15]]
-:1.16
-:[[1.17]]
-:1.18
-:[[1.19]]
-:1.20
-===Estimation===
-:[[1.21]]. Do all the books you own total at least one million pages? How many total pages are stored in your school library?
-:1.22. How many words are there in this textbook?
-:[[1.23]]. How many hours are one million seconds? How many days? Answer these questions by doing all arithmetic in your head.
-:1.24. Estimate how many cities and towns there are in the United States.
-:[[1.25]]. Estimate how many cubic miles of water flow out of the mouth of the Mississippi River each day. Do not look up any supplemental facts. Describe all assumptions you made in arriving at your answer.
-:1.26. How many Starbucks or McDonald’s locations are there in your country?
-:[[1.27]]. How long would it take to empty a bathtub with a drinking straw?
-:1.28. Is disk drive access time normally measured in milliseconds (thousandths of a second) or microseconds (millionths of a second)? Does your RAM memory access a word in more or less than a microsecond? How many instructions can your CPU execute in one year if the machine is left running all the time?
-:[[1.29]]. A sorting algorithm takes 1 second to sort 1,000 items on your machine. How long will it take to sort 10,000 items. . .
-::(a) if you believe that the algorithm takes time proportional to n2, and
-::(b) if you believe that the algorithm takes time roughly proportional to n log n?
-===Implementation Projects===
-:1.30. Implement the two TSP heuristics of Section 1.1 (page 5). Which of them gives better solutions in practice? Can you devise a heuristic that works better than both of them?
-:[[1.31]]. Describe how to test whether a given set of tickets establishes sufficient coverage in the Lotto problem of Section 1.8 (page 22). Write a program to find good ticket sets.
-===Interview Problems===
-:1.32. Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.
-:[[1.33]]. There are twenty-five horses. At most, five horses can race together at a time. You must determine the fastest, second fastest, and third fastest horses. Find the minimum number of races in which this can be done.
-:1.34. How many piano tuners are there in the entire world?
-:[[1.35]]. How many gas stations are there in the United States?
-:1.36. How much does the ice in a hockey rink weigh?
-:[[1.37]]. How many miles of road are there in the United States?
-:1.38. On average, how many times would you have to flip open the Manhattan phone book at random in order to find a specific name?
-Back to [[Chapter List]]

Difference between pages "Chapter 1" and "2.55"

Latest revision as of 19:41, 10 September 2020

Navigation menu

Personal tools

Namespaces

Variants

Views

More

Search

Navigation

Tools