Comp 200 Homework 5

Due in class Wed 20 Mar 2002

  1. Upon hearing about the problem of finding a Traveling Salesperson tour (TSP), 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, representing cities, you've drawn on paper.) Remember that a tour always ends back in the start city. Try to find a map which demonstrates this property clearly. Also, give the running time of this greedy algorithm in big-O notation, where N is the number of cities. Is it polynomial or exponential?

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

    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. 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? that is, can it be colored using only K different colors?" (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. We have discussed several graph problems in 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. 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-Colouring 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).

  5. Recall the function halts? from lecture (Given a program P and an input I, does P halt given I?). Consider a similar function halts-on-17? that takes only one argument. (Given a program P, does it halt when given 17 as input?).

    1. Reduce halts-on-17?, to halts?. (Easy.)
    2. Reduce halts? to halts-on-17?: That is, when somebody comes to you with an instance of halts?, you need to construct a program P2, which you pass on to a function your buddy wrote, halts-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 halts? (which was a three-line program).