Homework 21
due Mon 4/8 in class

For the following problem, develop a recursive backtracking algorithm to solve the problem using the 16 step recursive backtracking development template. Give each of the steps; don't just give an algorithm — the point here is understanding the process and being able to apply it.

For the running time, indicate the size of the search space (give the branching factor and longest path). If both process input and produce output approaches seem viable, pick the one that seems best with respect to running time and discuss your choice in the running time step.

1. Using just four colors, color a (geographical) map so that no two bordering regions have the same color — or determine that it isn't possible.

   

2. You are planning a dinner party, with n guests to be seated at two tables. (Each table holds exactly half of the guests.) You also have a list of preferences — some pairs of guests would prefer to be seated at the same table, while other pairs prefer to be at different tables. (There may also be many pairs with no preference about tables.) List all the possible seating arrangements that respect the guests' preferences. (The order of seating around each table doesn't matter, just who is at which table.)