Comp 200 hw05

  1. (3pts) Upon hearing about the problem of finding a Traveling Salesperson tour, an initial reaction is to say "construct a tour by starting at any city, and proceed to the nearest unvisited city." This is known as a greedy algorithm, since it makes its choice based on what seems best at the moment (but not necessarily in the long run).

    Your Task: Give a counterexample to this claim: that is, give a map where this greedy algorithm does not give the shortest tour. (A map being dots (cities) you've drawn on paper; remember that a tour ends back in the start city.) (Try to find a map which demonstrates this property clearly.)

    Extra Credit (1pt): Find a counterexample with the smallest possible number of cities; argue that no counterexample can have fewer cities than yours.

    To think about: How bad is the greedy algorithm on your map -- what is the ratio of the greedy tour to the optimal tour? Can you find a counterexample with a worse ratio? For any number k, do you think you can find a counterexample with a ratio worse than k (i.e. the ratio can be made arbitrarily bad)? [This topic can be pursued as a project.]

  2. (3pts) First, two definitions: Your Task Reduce (a) the problem of efficiently answering ``Given a graph, what is the smallest number of colors needed to color it?'' to (b) the problem of efficiently answering ``Yes or no: Given a graph and a number K, is the graph K-colorable?'' (Note that you are not solving either of these problems -- you are simply stating a relationship between the two problems, so that any algorithm for the latter gives rise to an algorithm for the former.)
    In doing the reduction, you may ask the second question repeatedly; is your procedure guaranteed to eventually yield an answer?
    You can express your answer in concise and precise english, or you can express it in scheme, writing the function fewest-colors-needed: Graph --> number, where you can use as a helper function the already-written is-colorable?: Graph, number --> boolean. Note that you are not given a number K; just a graph. (If you appeal to is-colorable?, then you must say what number you are providing it.)
    (Yes, this is actually problem 7.10 in Harel.)

  3. (4pts)

    We have discussed several graph problems in hw and class, but who cares about graphs? The reason they are helpful is because they abstract out everything except for "nodes" and "relations between nodes" (edges); this is a very general framework which can express many properties of interest, without including irrelevent info.

    For instance, you can consider nodes as actors, with an edge between two actors if they have both been in the same film. Such a graph has been constructed, and you can ask about shortest-paths to Kevin Bacon at the web site http://www.cs.virginia.edu/~bct7m/bacon.html.

    1. Using this web site, find the longest shortest-path you can, between any two connected actors.

    2. Suppose you are throwing a party for all actors, and you have three rooms in your house. Translate the graph statement "This graph is 3-colorable" into a statement mentioning only actors, co-starring, and an interesting room assignment. (It's a pretty simple statement; i just want to stress the translation between graph-space and actor-space.) (Note that it might be true or false that the graph is 3-colorable; your translated actors/rooms statement will be correspondingly true or false.)

    3. Do you think the statement is true, that the graph really 3-colorable? Support your answer concisely. (Would you guess this graph is 10-colorable? 1000-colorable? What is the smallest number of colors which you are sure would suffice?)

  4. Do one of the following two problems:
    1. Reduce graph 3-coloring to graph 4-coloring.
      That is, suppose you have a friend Frannie "Four-Color" Collins, to whom you can give a graph, and she'll soon tell you whether it is four-colorable. Then doing the reduction means setting up Ye Olde Three-Coloring Shoppe: people will come to you with graphs, and you need to tell them whether their graph is three-colorable. (You can of course create a map related to your input, and then ask Frannie about its four-colorability.)

      You can describe how your shoppe does the work in english, but be concise and precise. You also can think of this as writing the function is3colorable?, where you are allowed to call a helper function is4colorable?. Explain why your procedure gives the correct answer (reason about both the case where Frannie's answer is yes, and where Frannie's answer is no).

    2. Recall ``Halt?'' from lecture (Given a program P and an input I, does P halt given I?). Consider a similar problem, ``Halt-on-17?'' (Given a program P, does it halt given 17?).

      1. Reduce Halt-on-17?, to Halt?. (Easy.)

      2. Reduce Halt to Halt-on-17. That is, when somebody comes to you with an instance of Halt, you need to construct a program P2 which you can give to your buddy, who solves Halt-on-17. (Harder. Hint: P2 may take an input, but it doesn't have to use it!)

      3. Given the previous two results, what can you say about the comparative difficulty of these two problems?
      You may express your reductions as (one-line) Scheme programs, if you like. Both of these are shorter than (from lecture) reducing twisted to Halt (which was a three-line program).
    3. (4pts) An estimation, in the spirit of Hofstadter Chpt 6. Read about the corporate promo of the mir impact, in particular the comment about the insurance.

      1. Approximately, what might the cost of the free tacos actually be, if the target were hit? Make reasonable approximations, and mention what they are. There are approx. 283million americans.

      2. What is the likelihood (at the time the campaign was started), that target is hit? Assume that mir might hit anywhere in a 10,000km by 200km swath, with equal probability; also assume that the core of mir is a sphere 8m in diameter (a crude equivalence based on the core being a 13m by 4m(?) rectangle)
        (Hint: Just concentrate on the central point of the core -- how far away from the center of the target would it have to be, to touch a circular target at all?3)

      3. What is the expected ("average") cost of this offer, to the insurance company? (Just multiply the two previous numbers.) (Good insurance companies usually charge about 45% more than the expected costs, to cover the overhead of running a business, plus covering reasonable protection for cash-flow exigencies.)

      4. We've estimated the immediate costs of the offer (the insurance company's point of view). This seems to say that Taco Bell is out the money they paid the insurer, and whether or not the target is hit they are insulated from any costs/gains. But Taco Bell ain't dumb, they don't support insurance companies for no reason. What does Taco Bell expect to get out of the whole thing, if the target is hit? If not? (These answers aren't numeric, and there are a lot of things a MANA student might think of; just list one or two that come to mind.)

      4. 3: ..to hit a circular target.. Note that we are actually reducing "probability of a randomly-placed circle (M) overlapping a target (T)" to "probability of a randomly-placed point (M') falling inside a [slightly larger] target (T')". In this case both problems are both efficiently computable, but the latter is conceptually easier to handle.

      This approach -- shrinking the moving object and growing the target -- is routinely used in "robotic path-planning": finding a path for a robot to navigate around obstacles (e.g., furniture). This problem is simplified by considering the robot as a single point, but "growing" all the obstacles correspondingly. We then have the conceptually easier problem of moving a single point around [slightly different] obstacles. (back)