Each of the following problems can be solved with techniques taught in lecture. Construct a simple...

Transcribed Image Text:

Each of the following problems can be solved with techniques taught in lecture. Construct a simple directed graph, write an algorithm for each problem by black-boxing algorithms taught in lecture, and analyze its runtime. You do not need to provide proofs of correctness. (a) The CS 170 course staff is helping build a roadway system for PNPenguin's hometown in Antarctica. Since we have skill issues, we are only able to build the system using one-way roads between igloo homes. Before we begin construction, PNPenguin wants to evaluate the reliability of our design. To do this, they want to determine the number of reliable igloos; an igloo is reliable if you are able to leave the igloo along some road and then return to it along a path of other roads. However, PNPenguin isn't very good at algorithms, and they need your help. Given our proposed roadway layout, design an efficient algorithm that determines the number of reliable igloos. (b) There are p different species of Pokemon, all descended from the original Mew. For any species of Pokemon, Professor Juniper knows all of the species directly descended from it. She wants to write a program that answers queries about these Pokemon. The program would have two inputs: a and b, which represent two different species of Pokemon. Her program would then output one of three options in constant time (the time complexity cannot rely on p): (1) a is descended from b. (2) is descended from a. (3) a and b share a common ancestor, but neither are descended from each other. Unfortunately, Professor Juniper's laptop is very old and its SSD drive only has enough space to store up to O(p) pieces of data for the program. Give an algorithm that Professor Juniper's program could use to solve the problem above given the constraints. Hint: Professor Juniper can run some algorithm on her data before all of her queries and store the outputs of the algorithm for her program; time taken for this precomputation is not considered in the query run time. (c) Bob has n different boxes. He wants to send the famous "Blue Roses' Unicorn" figurine from his glass menagerie to his crush. To protect it, he will put it in a sequence of boxes. Each box has a weight w and size s; with advances in technology, some boxes have negative weight. A box a inside a box b cannot be more than 15% smaller than the size of box b; otherwise, the box will move, and the precious figurine will shatter. The figurine needs to be placed in the smallest box x of Bob's box collection. Bob (and Bob's computer) can ask his digital home assistant Falexa to give him a list of all boxes less than 15% smaller than a given box c (i.e. all boxes that have size between 0.85 to 1 times that of c). Bob will need to pay postage for each unit of weight (for negative weights, the post office will pay Bob!). Find an algorithm that will find the lightest sequence of boxes that can fit in each other in linear time (in terms of the graph). Hint: How can we create a graph knowing that no larger box can fit into a smaller box, and what property does this graph have? Each of the following problems can be solved with techniques taught in lecture. Construct a simple directed graph, write an algorithm for each problem by black-boxing algorithms taught in lecture, and analyze its runtime. You do not need to provide proofs of correctness. (a) The CS 170 course staff is helping build a roadway system for PNPenguin's hometown in Antarctica. Since we have skill issues, we are only able to build the system using one-way roads between igloo homes. Before we begin construction, PNPenguin wants to evaluate the reliability of our design. To do this, they want to determine the number of reliable igloos; an igloo is reliable if you are able to leave the igloo along some road and then return to it along a path of other roads. However, PNPenguin isn't very good at algorithms, and they need your help. Given our proposed roadway layout, design an efficient algorithm that determines the number of reliable igloos. (b) There are p different species of Pokemon, all descended from the original Mew. For any species of Pokemon, Professor Juniper knows all of the species directly descended from it. She wants to write a program that answers queries about these Pokemon. The program would have two inputs: a and b, which represent two different species of Pokemon. Her program would then output one of three options in constant time (the time complexity cannot rely on p): (1) a is descended from b. (2) is descended from a. (3) a and b share a common ancestor, but neither are descended from each other. Unfortunately, Professor Juniper's laptop is very old and its SSD drive only has enough space to store up to O(p) pieces of data for the program. Give an algorithm that Professor Juniper's program could use to solve the problem above given the constraints. Hint: Professor Juniper can run some algorithm on her data before all of her queries and store the outputs of the algorithm for her program; time taken for this precomputation is not considered in the query run time. (c) Bob has n different boxes. He wants to send the famous "Blue Roses' Unicorn" figurine from his glass menagerie to his crush. To protect it, he will put it in a sequence of boxes. Each box has a weight w and size s; with advances in technology, some boxes have negative weight. A box a inside a box b cannot be more than 15% smaller than the size of box b; otherwise, the box will move, and the precious figurine will shatter. The figurine needs to be placed in the smallest box x of Bob's box collection. Bob (and Bob's computer) can ask his digital home assistant Falexa to give him a list of all boxes less than 15% smaller than a given box c (i.e. all boxes that have size between 0.85 to 1 times that of c). Bob will need to pay postage for each unit of weight (for negative weights, the post office will pay Bob!). Find an algorithm that will find the lightest sequence of boxes that can fit in each other in linear time (in terms of the graph). Hint: How can we create a graph knowing that no larger box can fit into a smaller box, and what property does this graph have?

Answer rating: 100% (QA)

a To solve this problem we can construct a directed graph where each igloo is represented by a node and there is a directed edge from igloo A to igloo B if there is a oneway road from A to B Then we c... View the full answer