6 - Shortest Path (15pts) This exercise shows yet another problem that can be reduced into the shortest path problem. The Ithaca Community Center is creating a library for is members. It needs to build shelving to shelve 200 4" high books, 100 8" high books, and 80 12" high books Each book is 0.5" thick. They may build 4" high, 8" high, and 12" high shelves, or combinations of them. All books of a certain height have to go on the same type of shelf. In other words, they are not allowed to split the books of a certain height and put them on different shelves. They still have several ways to store the books. For example, an 8" high shelf may be built to store all the 4-inch and all the 8" high books, and a 12" high shelf for the all the 12" books. Another example: a 4" high shelf may be built to store all the 4" high books, an 8" high shelf for all the 8" high books and a 12" high shelf for the 12" books. Another example: a 12" high shelf might be built to store all the books. There are more combinations Costs: it costs $2300 to build a shelf. There is a cost of $5 per square inch for book storage. (Assume that the area required to store a book is given by the height of storage area times the book's thickness. If a 12" high shelf is used to store 8" high books, the storage area for the 8" high books should be calculated based on a 12" height) Show how this problem can be reduced into the shortest path problem to determine how the library should shelve the books, minimizing cost. Solve it by hand indicating how they will store the books and the cost. Hint: Construct a graph with nodes labeled 0", "4", "8", and "12." The labels on the nodes refer to having a shelf of that height installed. (The "0" node, corresponds to having no shelf installed.) Create a directed edge from node i to node j (withi cj) with cost Cijequal to the cost of adding a shelf of height j that contains all books of height larger than i and less than or equal to j. So, for example, an edge from node "4" to node "12" will have cost C.4,12 equal to the cost of installing a shelf of height 12" that contains all 12" high books and all 8" high books (but none of height 4") 6 - Shortest Path (15pts) This exercise shows yet another problem that can be reduced into the shortest path problem. The Ithaca Community Center is creating a library for is members. It needs to build shelving to shelve 200 4" high books, 100 8" high books, and 80 12" high books Each book is 0.5" thick. They may build 4" high, 8" high, and 12" high shelves, or combinations of them. All books of a certain height have to go on the same type of shelf. In other words, they are not allowed to split the books of a certain height and put them on different shelves. They still have several ways to store the books. For example, an 8" high shelf may be built to store all the 4-inch and all the 8" high books, and a 12" high shelf for the all the 12" books. Another example: a 4" high shelf may be built to store all the 4" high books, an 8" high shelf for all the 8" high books and a 12" high shelf for the 12" books. Another example: a 12" high shelf might be built to store all the books. There are more combinations Costs: it costs $2300 to build a shelf. There is a cost of $5 per square inch for book storage. (Assume that the area required to store a book is given by the height of storage area times the book's thickness. If a 12" high shelf is used to store 8" high books, the storage area for the 8" high books should be calculated based on a 12" height) Show how this problem can be reduced into the shortest path problem to determine how the library should shelve the books, minimizing cost. Solve it by hand indicating how they will store the books and the cost. Hint: Construct a graph with nodes labeled 0", "4", "8", and "12." The labels on the nodes refer to having a shelf of that height installed. (The "0" node, corresponds to having no shelf installed.) Create a directed edge from node i to node j (withi cj) with cost Cijequal to the cost of adding a shelf of height j that contains all books of height larger than i and less than or equal to j. So, for example, an edge from node "4" to node "12" will have cost C.4,12 equal to the cost of installing a shelf of height 12" that contains all 12" high books and all 8" high books (but none of height 4")