DOC PREVIEW
Berkeley COMPSCI 172 - Problem Set

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CS172 Computability & Complexity (Spring’09)Instructor: Mihai Pˇatra¸scu GSI: Omid EtesamiProblem Set 8 Due: Monday, April 131. The Travelling Salesman Problem (TSP) is the following: Given a complete graph G withweighted edges, find a cycle visiting every node exactly once, such that the total length of the cycleis minimized. (You can imagine that the nodes are the destinations that a salesman wants to visit;he needs to visit all of them in some order, to minimize his total travel time.)In this problem, you will solve the Planar TSP problem. The nodes will be points (x, y) in theplane; the distance between nodes (x1, y1) and (x2, y2) will bep(x1− x2)2+ (y1− y2)2.Implement code that reads n and the coordinates of the n points (assume each is a floatingpoint number). The code should output the length of the minimal cycle visiting all nodes.Email the source code (in C, Java, or Pyhton) to [email protected] as an attachment to anemail with the subject CS172-HW8-P1. Also email the answers to the following questions:(a) What is the running time of your algorithm, using O(·) notation? (You will probably implementsome backtracking algorithm.)(b) If you generate n = 10 points randomly with coordinates in [0, 1], what is the (estimated)average length of the tour? You should compute this estimation by running your code on,say, 100 random instances, and taking the average of the outputs.(c) What is the largest n, such that your code typically finishes in under 10 seconds when run oninstances of n random points?2. In the Monotone TSP problem, the goal is to find the shortest cycle satisfying:• the cycle starts at the Western-most point (minimum x).• the cycle visits some nodes going only towards East (x increases at every step), until it reachesthe Eastern-most point.• the cycle visits other nodes going only West, until it returns to the Western-most point.• each node is visited exactly once.Assume that no two points have the same x coordinate (no two points are on the same longitude).Implement an algorithm running in time O(n3) which solves the Monotone TSP problem on npoints. Email the source code (in C, Java, or Pyhton) to [email protected] as an attachment toan email with the subject CS172-HW8-P2.Also email the answers to the following questions:(a) Briefly describe how your algorithm works. (Hint: use dynamic programming.)(b) If you generate n = 100 points randomly with coordinates in [0, 1], what is the (estimated)average length of the tour? You should compute this estimation by running your code on,say, 100 random instances, and taking the average of the outputs.(c) What is the largest n, such that your code typically finishes in under 10 seconds when run oninstances of n random points?13. The TSP problem was not a language (the output was a number, not accept/reject). Here isa language for the so-called “decision version” of TSP:L =(G, k) | the graph G has a cycle of length at most k visting all nodes onceIn the language, the graph G is given by specifying the cost of every edge. For simplicity, assumethat the cost of every edge is an integer between 1 and 1000.(a) Prove that L ∈ NP.(b) Prove that if L ∈ T IME(f (n)), then the TSP problem (outputting the length of the shortestcycle) can be solved in time O(f(n) · lg n).4. Prove that the following language is in coNP:L =(G, k) | the longest simple path in G has length at most kA simple path is a path that does not visit any node more than once.5. We define 2HROTM to be 2-head Read-Only Turing Machines. These are Turing Machineswith two heads that can be moved independently over the same tape. The machines are read-only,i.e. they may not write on the tape at all.(a) Show that the halting problem for 2HROTM is decidable.(b) Show that the emptiness problem for 2HROTM is


View Full Document

Berkeley COMPSCI 172 - Problem Set

Download Problem Set
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?