Problem 2 (20 points). At the local library, the librarian is responsible for helping patrons find books. To find books faster, the librarian stores the books on the shelves alphabetically by title. The library has a limited budget but wants to have the widest variety of books as possible, so they decided to only keep a single copy of any given title. A recent storm and electrical surge fried their electronic card catalog that tracks where books are stored on the shelves. (a) When a patron comes in to look for a title, the librarian must help them locate the book, or report that it is checked out. While the library waits for a new electronic system, this must be done by personally looking through the inventory on the shelves. Give the decision tree the librarian should follow that avoids having to examine every book on the shelves, even in the situation that the book is checked out. (b) Derive a tight lower bound for any retrieval algorithm to solve this problem using a decision tree. Problem 3 (20 points). A minor league baseball team tracks statistics for all of its pitchers during a season, looking for players that can throw perfect games. (A perfect game is when a pitcher does not allow a single player from the opposing team to reach a base.) For a given pitcher, their record records 1 if they pitched a perfect game, 0 if they pitched but allowed players on base, and -1 if they did not play for each of the n games in the season. For example, their record may look like (0,0,1,-1,0,-1,1,-1,1,0,...). (a) Write pseudocode that reports if a pitcher ever threw a perfect game during the season. (b) What pitching record gives the best case running time for your algorithm? How many games need to be checked? (c) What pitching record gives the worst case running time for your algorithm? How many games need to be checked? (d) The team's corporate sponsor "Crazy Coffee is offering a year's worth of free coffee to any season ticket holder if the same pitcher throws two perfect games in a row, without any breaks between them. At the end of the season, they need to identify if any of the pitchers threw two consecutive perfect games. Write pseudocode that can determine if pitcher P earned free coffee for a year for all the season ticket holders by looking at fewer than n entries in P's record. Assume that n%3 = 1. (Hint: Start by looking at the first even game.] Problem 2 (20 points). At the local library, the librarian is responsible for helping patrons find books. To find books faster, the librarian stores the books on the shelves alphabetically by title. The library has a limited budget but wants to have the widest variety of books as possible, so they decided to only keep a single copy of any given title. A recent storm and electrical surge fried their electronic card catalog that tracks where books are stored on the shelves. (a) When a patron comes in to look for a title, the librarian must help them locate the book, or report that it is checked out. While the library waits for a new electronic system, this must be done by personally looking through the inventory on the shelves. Give the decision tree the librarian should follow that avoids having to examine every book on the shelves, even in the situation that the book is checked out. (b) Derive a tight lower bound for any retrieval algorithm to solve this problem using a decision tree. Problem 3 (20 points). A minor league baseball team tracks statistics for all of its pitchers during a season, looking for players that can throw perfect games. (A perfect game is when a pitcher does not allow a single player from the opposing team to reach a base.) For a given pitcher, their record records 1 if they pitched a perfect game, 0 if they pitched but allowed players on base, and -1 if they did not play for each of the n games in the season. For example, their record may look like (0,0,1,-1,0,-1,1,-1,1,0,...). (a) Write pseudocode that reports if a pitcher ever threw a perfect game during the season. (b) What pitching record gives the best case running time for your algorithm? How many games need to be checked? (c) What pitching record gives the worst case running time for your algorithm? How many games need to be checked? (d) The team's corporate sponsor "Crazy Coffee is offering a year's worth of free coffee to any season ticket holder if the same pitcher throws two perfect games in a row, without any breaks between them. At the end of the season, they need to identify if any of the pitchers threw two consecutive perfect games. Write pseudocode that can determine if pitcher P earned free coffee for a year for all the season ticket holders by looking at fewer than n entries in P's record. Assume that n%3 = 1. (Hint: Start by looking at the first even game.]