代写算法问题，解决 Hamiltonian Cycle Problem
，也就是哈密顿回圈问题。
Problem 1
Simple-Quicksort uses the last element of the array as a pivot. Randomized-
Quicksort uses a random array element as the pivot. In the worst-case both
algorithms take O (n^2) time to sort an array.
- Give an example worst-case input for Simple-Quicksort. Show that Simple- Quicksort takes O(n^2) time to sort this input.
- What is the expected running time for Simple-Quicksort on your input from (1) ?
- What is the expected running time for Randomized-Quicksort on your input from (1)?
- What is the worst-case running time for Randomized-Quicksort on your input from (1)?
- What is the worst-case input for Randomized-Quicksort?
Problem 2
NP-complete problems are considered unlikely to be in P because they can each
be reduced to Satisfiability and Satisfiability can be reduced to any problem
in NP (so they can all be reduced to each other). It is often difficult to
determine if any given problem is NP-complete and we require formal reductions
to actually prove this. However, even though a general problem such as
Satisfiability may be NP-hard, simplified versions of the problem may be in P.
For example, 3-Satisfiability is NP-complete while 2- Satisfiability
(satisfiability restricted to 2 variables per clause) is in P.
Consider the Hamiltonian Cycle problem: “Given a graph G, does G have a simple
cycle containing all of the vertices of G?” (Recall that a simple cycle
contains no edge or vertex twice) This problem is NP-complete because it can
be reduced from Vertex- Cover which can be reduced from 3-Satisfiability. Now
consider each of the following modifications of Hamiltonian Cycle. Do you
think it is NP-complete or in P? If you believe it is in P then give a brief
description of a method that will answer the question in polynomial time. If
you believe it is NP-complete then give a brief justification such as an NP-
complete problem that reduces to this problem (formal reductions are
technically required for this but outside of the scope of this course).
- Hamiltonian Cycle restricted to trees
- Hamiltonian Cycle restricted to directed acylic graphs
- Hamiltonian Cycle restricted to disconnected graphs
- “Given a graph G and a list of k cycles in G, is one of these cycles a Hamiltonian Cycle?”
- The Travelling Salesman problem: “Given a graph G with weighted edges, what is the simple cycle of G containing all of the vertices of G that has minimum weight (if any such cycle exists)?”
- Hamiltonian Cycle on hypergraphs. A hypergraph is a graph where the edges connect two or more vertices. Assume that a path through a hypergraph can follow an edge to only one of its endpoints.
- “Given a graph G does the graph contain a cycle of length k?” (Note: for this problem k is a constant, not an input variable)
