Polynomialtime randomized algorithm

Polynomialtime randomized algorithm

Problem complexity (15%)
This is a theoretical question. No coding and experimentation are required. The Hamiltonian cycle problem is a
closely related problem to the TSP. Given a graph G = (V, E), we can say that a cycle C is a Hamiltonian cycle if it
visits every vertex exactly once. Note that a cycle must start and end at the same vertex. For this assignment, you
may assume G is undirected.
Assume that you know the Hamiltonian cycle problem is NP-Complete (it is, but we wont prove it here). Answer
the following questions:
Question 1 (5%)
Assume the optimal solution to a symmetric TSP (sTSP) instance has length L. Given a TSP tour, W, show that
it is possible to check if W is an optimal solution to this symmetric TSP instance in polynomial time. This proves
that sT SP NP.
Question 2 (5%)
Show that the Hamiltonian cycle problem (HAM ) is polynomial-reducible to the symmetric travelling salesman
problem. That is, prove HAM P sT SP.
Question 3 (5%)
Given HAM P sT SP and HAM NP C, what can we conclude about the complexity class of sT SP?
Hint: you can answer question 3 in this section without first answering questions 1 and 2.
4 3-coloring problem (10%)
This is a theoretical question. No coding and experimentation are required. Suppose we are given a graph G = (V, E),
and we want to color each vertex with one of three colors (e.g., red, green and blue), even if we are not necessarily
able to give different colors to every pair of adjacent vertices. Rather, we say that an edge (u, v) is satisfied if the
colors assigned to u and v are different. The 3-coloring problem aims at identifying a 3-coloring (i.e., a specific way
of assigning one of the three colors to every vertex) that maximizes the number of satisfied edges.
Provide your answers to the following questions about the 3-coloring problem in your PDF final report.
Question 1 (5%)
Consider a 3-coloring that maximizes the number of satisfied edges, and let c
denote this number. Give a polynomialtime randomized algorithm that produces a 3-coloring that satisfies at least 2
3
c
edges. Prove that the expected number
of edges that can be satisfied by your randomized algorithm should be at least 2
3
c
.
Question 2 (5%)
Describe, with help of pseudo code, how tabu search can be used to find an approximate solution to the 3-coloring
problem.
5 Submission guidelines
5.1 Submission requirements
1. Program code for all tasks in Section 2. You should label the programs clearly. One suggestion is to use
separate directories e.g. part2 1/, part2 2/, … with all programs stored in their corresponding directories.
COMP361-T2, 2021 3 Assignment 4
For each program, please provide a readme file that specifies how to compile and run your program on the
ECS School machines (e.g.

PLACE THIS ORDER OR A SIMILAR ORDER WITH ASSIGNMENT GURUH TODAY AND GET AN AMAZING DISCOUNT

.

When you order professional assignments here, you will get: Original custom papers. We value your academic reputation. Just as well, we value the years of thorough work on our reputation for reliability and never compromise the originality of delivered papers. We will never endanger both. Every custom assignment is written from zero – the only possible first stage of work on the order is research. We apply the latest plagiary checking tools on the final stage, so plagiarism has no chance to emerge in your college assignment writing. Control over the order completion. To make the process of collaboration comfortable and efficient, we offer our clients to choose the writer themselves taking into account all the requirements and the budget. For you to save nerves, having entrusted your fateful task to some qualified “stranger”, we enable communication with the assigned writer in the process of order completion. Affordable assistance.
Previous PostApproximation algorithm case studyNext PostThe individual sections program question