ݺߣ

ݺߣShare a Scribd company logo

HW4

•
•
S
Steve Merritt

This homework assignment for EECS 281 involves 4 problems related to data structures and algorithms: 1) Two dynamic programming problems about carrying items within weight/number limits. 2) Identifying algorithm types (greedy, divide-and-conquer, etc.) that match 4 pseudocode examples. 3) Calculating how many gold coins a pirate captain will keep based on voting among crew members. 4) Calculating probabilities that lost pirates will randomly sail home on maps of varying sizes.

1 of 6
Download to read offline
University of Michigan  EECS 281 Data Structures and Algorithms  Homework 4  Spring Semester, 2014    Assigned​:   06/14/14, 12:00pm  Due​:   06/20/14, 11:55pm  Instructions​: Homework is on 4 pages and is worth 20 total points. You must complete all                                problems. Enter all responses into the CTools Test Center. For Test Center questions, be sure                              to press the finish button to officially submit your answers. Please be sure to double check your                                  submissions via a confirmation from CTools before deciding that the homework is submitted. A                            key for the homework set will be posted after the due date.      Clarifications​:   ● Assume all C++ code to be C++11­standard compliant (compiled with ​­std=c++11​).    Homework Goals:  ● Demonstrate understanding of Dynamic Programming problems.    Honor Code: This work is to be completed individually.  ​Collaboration is not allowed.  Potential violations will be reported to the honor council. By submitting, you confirm                          that ​you have neither given nor received unauthorized help on this assignment​.       
Problem 1 (5 points)    The TSA has introduced a new rule at the Detroit Airport: you may only bring a maximum of K                                      items in your carry­on. Each item is assigned a value that represents how badly you want to                                  bring that item on the plane. Given that you want to bring N ​items (where N is greater than K)                                        and that you want to maximize the total value of the items you bring, answer the following                                  questions.     1.1​ Assuming the best possible algorithm, which algorithm family is suitable to find the most  optimal solution for your problem?       1.2​ In terms of K, N, or both, what is the worst­case runtime complexity of this algorithm?       For the rest of the questions, assume the TSA decided to revise their rule. The new rule allows  you to carry as many items as you want, as long as the total weight of all the items you carry on  is less than some weight W. Like in the previous questions, you are to figure out which different  items to take and how many of each.      1.3​ Assuming the best possible algorithm, which algorithm family is suitable to find the most  optimal solution?       1.4​ Assume that the weight of each unit item is always a multiple of 1 pound (1 lbs, 2 lbs, etc,  and not, say, 1.5 lbs), what is the worst­case runtime complexity of this algorithm in terms of W,  N, or both?          
Problem 2 (5 points)    Choose the algorithm that best describes each pseudocode given below.     2.1  void Algorithm1(node v)   node u     if (promising(v))     if (solution(v)) then     write solution     else     for each child u of v     Algorithm1(u)      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking            2.2  type Algorithm2(node v, type currBest)   node u   if (promising(v))   if (solution(v)) then   update(currBest)   else   for each child u of v   Algorithm2(u, currBest)   return currBest      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking    
2.3  int Algorithm3(int m, int size[], int val[])   bool possSet[0..n] //(0: absent, 1: present)     int maxVal = 0     for int i = 0 to 2^n ­ 1   possSet[] = genNextPower(n)     int setSize = findSize(possSet[])     int setValue = findValue(possSet[])     if setSize < m and setValue > maxVal     bestSet[] = possSet[]     maxVal = setValue     return maxVal      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking                   2.4  int Algorithm4(int n)  int a[0..n]     a[0] = a[1] = 1     for int i = 2 to n     a[i] = a[i ­ 2] + a[i ­ 1].     return a[n]      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking      
Problem 3: On Piracy and its Consequences (5 points)    Captain Drew “The Beard” DeOrio and his faithful crew of pirates are sailing the high seas,                                when they happen upon a merchant ship full of treasure ­ 100 gold coins! After scuttling the                                  merchant ship and marooning the sailors on a deserted island, the pirates gather to decide how                                to, in the eloquent words of James, “divvy the booty, yarr!”.    Although pirates are not generally known for following rules, when it comes to treasure there is                                a very specific protocol that must be followed. Pirates take treasure seriously.  1. The pirate in charge proposes a distribution of coins.  2. All the pirates vote on whether or not to accept this distribution.  3. If more than half the pirates vote against the distribution, the pirate in charge is thrown   overboard, the next pirate in line is made captain and the process is begun anew.    The hierarchy of command on Captain DeOrio’s vessel is as follows:  1. Captain Drew “The Beard” DeOrio  2. First Mate Dave “Foo­Bar” Paoletti  3. Helmsman Matt “Diffy” Diffenderfer  4. Galley Cook James “Stew­Pot” Juett  5. Lookout Kevin “Arrrrr!” Kiningham  6. Kevin’s parrot, “Squawky”  7. Deck Urchin Steve “Swabbie” Merritt    With this process in mind, how many coins will Captain DeOrio keep for himself?    Clarifications:  ● These are extremely logical pirates.  ● Pirates do not want to be thrown overboard.  ● Each pirate wants to maximize the amount of gold they receive.  ● Each pirate would prefer to throw another pirate overboard, if all other results would                            otherwise be equal.  ● Squawky is a logical pirate parrot.  ● Yes, there are hungry sharks in the water.  ● As pirates do not trust each other, no alliances or deals will be made.  ● The pirate in charge gets to vote too.    Hints:  ● Start from the base case and work your way backwards. With only two pirates, how                              many coins can the captain keep? With three pirates?  ● It may be helpful to make a table.       
Question 4: The Lost Boys (5 points)    After pillaging the merchant ship and arguing over who gets what, the pirates decide to throw                                Captain DeOrio overboard anyway. Unfortunately, as they realize after the fact, Captain DeOrio                          was the only one who knew the secret pirate­ship­sailing algorithm that they need to get home!     These are now some very lost pirates. But just how lost are they? Calculate the probability that,                                  if they choose a random course, these poor pirates will end up back at their secret                                pirate­lair­hideout (marked with an X on this map). Keep in mind that this is a sailing ship, and                                    can only sail with the wind (you may only move right or down).    What is the probability for:  1. A map of size 3 x 3?               (1 pt)  2. A map of size 12 x 12? (2 pts)  3. A map of size 26 x 26?             (2 pts)    Clarifications:  ● It’s okay to sail past/through whales.  ● Give answers as a percentage (0%­100%) rounded to the nearest whole number.  ● The pirate ship always begins in the upper left corner of the map.  ● Pirates will not sail off of the map. They’re not that dumb.  ● The pirate lair is always located in the lower right corner of the map.  ● As an example, a 2 x 2 map would have 4 possible paths (RIGHT, RIGHT­DOWN,                              DOWN, and DOWN­RIGHT), and 2 would lead home: 50%    Hints:  ● Remember, the probability of the pirates finding their way home is equivalent to the                            number of routes that lead home divided by the number of possible routes. 

More Related Content

HW4

  • 1. University of Michigan  EECS 281 Data Structures and Algorithms  Homework 4  Spring Semester, 2014    Assigned​:   06/14/14, 12:00pm  Due​:   06/20/14, 11:55pm  Instructions​: Homework is on 4 pages and is worth 20 total points. You must complete all                                problems. Enter all responses into the CTools Test Center. For Test Center questions, be sure                              to press the finish button to officially submit your answers. Please be sure to double check your                                  submissions via a confirmation from CTools before deciding that the homework is submitted. A                            key for the homework set will be posted after the due date.      Clarifications​:   ● Assume all C++ code to be C++11­standard compliant (compiled with ​­std=c++11​).    Homework Goals:  ● Demonstrate understanding of Dynamic Programming problems.    Honor Code: This work is to be completed individually.  ​Collaboration is not allowed.  Potential violations will be reported to the honor council. By submitting, you confirm                          that ​you have neither given nor received unauthorized help on this assignment​.       
  • 2. Problem 1 (5 points)    The TSA has introduced a new rule at the Detroit Airport: you may only bring a maximum of K                                      items in your carry­on. Each item is assigned a value that represents how badly you want to                                  bring that item on the plane. Given that you want to bring N ​items (where N is greater than K)                                        and that you want to maximize the total value of the items you bring, answer the following                                  questions.     1.1​ Assuming the best possible algorithm, which algorithm family is suitable to find the most  optimal solution for your problem?       1.2​ In terms of K, N, or both, what is the worst­case runtime complexity of this algorithm?       For the rest of the questions, assume the TSA decided to revise their rule. The new rule allows  you to carry as many items as you want, as long as the total weight of all the items you carry on  is less than some weight W. Like in the previous questions, you are to figure out which different  items to take and how many of each.      1.3​ Assuming the best possible algorithm, which algorithm family is suitable to find the most  optimal solution?       1.4​ Assume that the weight of each unit item is always a multiple of 1 pound (1 lbs, 2 lbs, etc,  and not, say, 1.5 lbs), what is the worst­case runtime complexity of this algorithm in terms of W,  N, or both?          
  • 3. Problem 2 (5 points)    Choose the algorithm that best describes each pseudocode given below.     2.1  void Algorithm1(node v)   node u     if (promising(v))     if (solution(v)) then     write solution     else     for each child u of v     Algorithm1(u)      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking            2.2  type Algorithm2(node v, type currBest)   node u   if (promising(v))   if (solution(v)) then   update(currBest)   else   for each child u of v   Algorithm2(u, currBest)   return currBest      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking    
  • 4. 2.3  int Algorithm3(int m, int size[], int val[])   bool possSet[0..n] //(0: absent, 1: present)     int maxVal = 0     for int i = 0 to 2^n ­ 1   possSet[] = genNextPower(n)     int setSize = findSize(possSet[])     int setValue = findValue(possSet[])     if setSize < m and setValue > maxVal     bestSet[] = possSet[]     maxVal = setValue     return maxVal      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking                   2.4  int Algorithm4(int n)  int a[0..n]     a[0] = a[1] = 1     for int i = 2 to n     a[i] = a[i ­ 2] + a[i ­ 1].     return a[n]      A. Brute­force   B. Greedy   C. Dynamic Programming   D. Divide and Conquer   E. Branch and Bound   F. Backtracking      
  • 5. Problem 3: On Piracy and its Consequences (5 points)    Captain Drew “The Beard” DeOrio and his faithful crew of pirates are sailing the high seas,                                when they happen upon a merchant ship full of treasure ­ 100 gold coins! After scuttling the                                  merchant ship and marooning the sailors on a deserted island, the pirates gather to decide how                                to, in the eloquent words of James, “divvy the booty, yarr!”.    Although pirates are not generally known for following rules, when it comes to treasure there is                                a very specific protocol that must be followed. Pirates take treasure seriously.  1. The pirate in charge proposes a distribution of coins.  2. All the pirates vote on whether or not to accept this distribution.  3. If more than half the pirates vote against the distribution, the pirate in charge is thrown   overboard, the next pirate in line is made captain and the process is begun anew.    The hierarchy of command on Captain DeOrio’s vessel is as follows:  1. Captain Drew “The Beard” DeOrio  2. First Mate Dave “Foo­Bar” Paoletti  3. Helmsman Matt “Diffy” Diffenderfer  4. Galley Cook James “Stew­Pot” Juett  5. Lookout Kevin “Arrrrr!” Kiningham  6. Kevin’s parrot, “Squawky”  7. Deck Urchin Steve “Swabbie” Merritt    With this process in mind, how many coins will Captain DeOrio keep for himself?    Clarifications:  ● These are extremely logical pirates.  ● Pirates do not want to be thrown overboard.  ● Each pirate wants to maximize the amount of gold they receive.  ● Each pirate would prefer to throw another pirate overboard, if all other results would                            otherwise be equal.  ● Squawky is a logical pirate parrot.  ● Yes, there are hungry sharks in the water.  ● As pirates do not trust each other, no alliances or deals will be made.  ● The pirate in charge gets to vote too.    Hints:  ● Start from the base case and work your way backwards. With only two pirates, how                              many coins can the captain keep? With three pirates?  ● It may be helpful to make a table.       
  • 6. Question 4: The Lost Boys (5 points)    After pillaging the merchant ship and arguing over who gets what, the pirates decide to throw                                Captain DeOrio overboard anyway. Unfortunately, as they realize after the fact, Captain DeOrio                          was the only one who knew the secret pirate­ship­sailing algorithm that they need to get home!     These are now some very lost pirates. But just how lost are they? Calculate the probability that,                                  if they choose a random course, these poor pirates will end up back at their secret                                pirate­lair­hideout (marked with an X on this map). Keep in mind that this is a sailing ship, and                                    can only sail with the wind (you may only move right or down).    What is the probability for:  1. A map of size 3 x 3?               (1 pt)  2. A map of size 12 x 12? (2 pts)  3. A map of size 26 x 26?             (2 pts)    Clarifications:  ● It’s okay to sail past/through whales.  ● Give answers as a percentage (0%­100%) rounded to the nearest whole number.  ● The pirate ship always begins in the upper left corner of the map.  ● Pirates will not sail off of the map. They’re not that dumb.  ● The pirate lair is always located in the lower right corner of the map.  ● As an example, a 2 x 2 map would have 4 possible paths (RIGHT, RIGHT­DOWN,                              DOWN, and DOWN­RIGHT), and 2 would lead home: 50%    Hints:  ● Remember, the probability of the pirates finding their way home is equivalent to the                            number of routes that lead home divided by the number of possible routes.