## On page 406 of Section 10.1.3, we give an implementation

On page 406 of Section 10.1.3, we give an implementation of the method setdefault as it might appear in the MutableMapping abstract base class. While that method accomplishes the goal in a general fashion, its efficiency is less than ideal. In particular, when the key is new, there will be a failed search due to the initial use of _ _getitem_ _, and then a subsequent insertion via _ _setitem_ _. For a concrete implementation, such as the UnsortedTableMap, this is twice the work because a complete scan of the table will take place during the failed _ _getitem_ _, and then another complete scan of the table takes place due to the implementation of _ _setitem_ _. A better solution is for the UnsortedTableMap class to override setdefault to provide a direct solution that performs a single search. Give such an implementation of UnsortedTableMap.setdefault.

## Alice has two queues, Q and R, which can store

Alice has two queues, Q and R, which can store integers. Bob gives Alice 50 odd integers and 50 even integers and insists that she store all 100 integers in Q and R. They then play a game where Bob picks Q or R at random and then applies the round-robin scheduler, described in the chapter, to the chosen queue a random number of times. If the last number to be processed at the end of this game was odd, Bob wins. Otherwise, Alice wins. How can Alice allocate integers to queues to optimize her chances of winning? What is her chance of winning?

## Suppose you are given a timetable, which consists of:• A

Suppose you are given a timetable, which consists of:

• A set A of n airports, and for each airport a in A, a minimum connecting time c(a).

• A set F of m flights, and the following, for each flight f in F:

◦ Origin airport a1(f) in A

◦ Destination airport a2(f) in A

◦ Departure time t1(f)

◦ Arrival time t2(f)

Describe an efficient algorithm for the flight scheduling problem. In this problem, we are given airports a and b, and a time t, and we wish to compute a sequence of flights that allows one to arrive at the earliest possible time in b when departing from a at or after time t. Minimum connecting times at intermediate airports must be observed. What is the running time of your algorithm as a function of n and m?