Cam Petitive and Opal T. Mull have to do readings for a class, but they dread going to the library! In typical MIT style, the library owns m books which students refer to by number, from 1 to m. Their professor gives the name of a book, b, each time she assigns a reading. If a student has the book checked out, they complete the reading swiftly and happily (cost 0). Otherwise, they have to walk across campus to check the book out from the library (cost 1). The library has lots of copies of each book, so students don't have to worry about reserving books or book shortages. The problem is, each student is only allowed to have k books checked out at any time, so students who have k books checked out must return one of their previously checked-out books when checking out a new one. Opal has somehow managed to figure out not only then readings, but also the optimal sequence of books to return, to minimize trips to the library. Cam hasn't done the same, but he thinks he can compete with Opal without knowing the readings or doing such complicated calculations. Note that the professor seems to enjoy repetition as a teaching tool, and doesn't hesitate to assign old readings. At the beginning of the semester, both Cam and Opal have zero books checked out. (a) [15 points) The library doesn't set explicit due dates, so Cam thinks he can exploit this by holding on to his books for as long as possible. He works out the following strategy for each reading b: If b is already checked out, he does not go to the library, and completes the reading swiftly and happily. Otherwise, he checks out b from the library as follows: - If Cam hasn't reached his limit of k books checked out yet, he doesn't return any books. - Otherwise, he returns the book with the most recent check out date. Prove that Cam's strategy is not competitive with Opal's if k 2. That is, prove that there are input sequences of length n such that the ratio of Cam's to Opal's library trips tends to oo as n tends to oo. (b) (25 points) The semester has progressed (both Opal and Cam have the same k books checked out), and now Cam thinks he has a better idea. Cam keeps his k library books stacked up on his desk, to remember the last time each was used for a reading. Whenever a reading is assigned, if Cam has the book already, he slides it out, does the reading, and places it on the top of the stack. If Cam has to go to the library, he slides out the bottom book from the stack, returns that one, and puts his newly checked-out book on the top of the stack when he gets back. Use the potential method to prove that Cam's strategy is k-competitive with Opal's. That is, for any sequence of reading assignments of length n, the ratio of Cam's to Opal's library trips is no more than k. Hint: At any time let SCAM be the set of books that Cam has checked out, and let Sort be the set of books that Opal has checked out. Use the potential function 0 = (b) where S = SCAM Sopr is the set of books that Cam has which Opal doesn't and w() is how high up book b is on Cam's shelf, with the bottom book's height (bottom) = 1 and the top book's height wbtop) = k. (c) (5 points) Which aspect of the proof for part (b) does not work if you were to try to prove Cam's original strategy is k-competitive with the same potential function? (d) (15 points) Cam makes a friend in the class, Amy Ortez. Amy is intrigued to see that her book-return strategy is very similar to Cam's. Amy keeps her books on a shelf instead of in a stack. If she needs to go to the library, she slides out the rightmost book from the shelf, returns it, and inserts her newly checked out book to the left of her other books upon returning. Whenever a book is assigned which she already has checked out, Amy slides it out, does the reading, and then places it back where it was located on the shelf. Use the potential method to prove that Amy's strategy is also k-competitive with Opal's. Cam Petitive and Opal T. Mull have to do readings for a class, but they dread going to the library! In typical MIT style, the library owns m books which students refer to by number, from 1 to m. Their professor gives the name of a book, b, each time she assigns a reading. If a student has the book checked out, they complete the reading swiftly and happily (cost 0). Otherwise, they have to walk across campus to check the book out from the library (cost 1). The library has lots of copies of each book, so students don't have to worry about reserving books or book shortages. The problem is, each student is only allowed to have k books checked out at any time, so students who have k books checked out must return one of their previously checked-out books when checking out a new one. Opal has somehow managed to figure out not only then readings, but also the optimal sequence of books to return, to minimize trips to the library. Cam hasn't done the same, but he thinks he can compete with Opal without knowing the readings or doing such complicated calculations. Note that the professor seems to enjoy repetition as a teaching tool, and doesn't hesitate to assign old readings. At the beginning of the semester, both Cam and Opal have zero books checked out. (a) [15 points) The library doesn't set explicit due dates, so Cam thinks he can exploit this by holding on to his books for as long as possible. He works out the following strategy for each reading b: If b is already checked out, he does not go to the library, and completes the reading swiftly and happily. Otherwise, he checks out b from the library as follows: - If Cam hasn't reached his limit of k books checked out yet, he doesn't return any books. - Otherwise, he returns the book with the most recent check out date. Prove that Cam's strategy is not competitive with Opal's if k 2. That is, prove that there are input sequences of length n such that the ratio of Cam's to Opal's library trips tends to oo as n tends to oo. (b) (25 points) The semester has progressed (both Opal and Cam have the same k books checked out), and now Cam thinks he has a better idea. Cam keeps his k library books stacked up on his desk, to remember the last time each was used for a reading. Whenever a reading is assigned, if Cam has the book already, he slides it out, does the reading, and places it on the top of the stack. If Cam has to go to the library, he slides out the bottom book from the stack, returns that one, and puts his newly checked-out book on the top of the stack when he gets back. Use the potential method to prove that Cam's strategy is k-competitive with Opal's. That is, for any sequence of reading assignments of length n, the ratio of Cam's to Opal's library trips is no more than k. Hint: At any time let SCAM be the set of books that Cam has checked out, and let Sort be the set of books that Opal has checked out. Use the potential function 0 = (b) where S = SCAM Sopr is the set of books that Cam has which Opal doesn't and w() is how high up book b is on Cam's shelf, with the bottom book's height (bottom) = 1 and the top book's height wbtop) = k. (c) (5 points) Which aspect of the proof for part (b) does not work if you were to try to prove Cam's original strategy is k-competitive with the same potential function? (d) (15 points) Cam makes a friend in the class, Amy Ortez. Amy is intrigued to see that her book-return strategy is very similar to Cam's. Amy keeps her books on a shelf instead of in a stack. If she needs to go to the library, she slides out the rightmost book from the shelf, returns it, and inserts her newly checked out book to the left of her other books upon returning. Whenever a book is assigned which she already has checked out, Amy slides it out, does the reading, and then places it back where it was located on the shelf. Use the potential method to prove that Amy's strategy is also k-competitive with Opal's