Question

The *4*-CLIQUE problem is defined as follows: Given a
graph *G*, does it have a clique of size *4*? Is this
problem in ** P**? Yes, no, unknown? Justify
your answer (if your answer is “yes”, briefly describe a
polynomial-time algorithm).

Answer #1

The Clique Problem: Given a graph G and an integer k, does G contain a k-clique?

**“Problem Instance” – the specific cases**

Ex: Does contain a 4-clique? (no)

Ex: Does contain a 3-clique? (yes)

**Problems as Sets of “Yes” Instances**

Ex: CLIQUE = { (G,k) | G contains a k-clique }

E.g., ( , 4) ∉ CLIQUE

E.g., ( , 3) ∈ CLIQUE

**POLYNOMIAL-TIME ALGORITHM --**

A *polynomial-time algorithm* is an algorithm whose
execution time is either given by a polynomial on the size of the
input, or can be bounded by such a polynomial.

Problems that can be solved by a polynomial-time algorithm are
called ** tractable** problems.

**For example**, most algorithms on arrays can use
the array size, n, as the input size. To find the largest element
in an array requires a single pass through the array, so the
algorithm for doing this is O(n).

Sorting algorithms usually require either O(n log n) or
O(n^{2}) time. Heapsort takes O(n log n) time in all cases.
Quicksort takes O(n log n) time on average, but O(n^{2})
time in the worst case.

Regarding O(n log n) time, note that

- The base of the logarithms is irrelevant, since the difference is a constant factor, which we ignore; and
- Although n log n is not, strictly speaking, a polynomial, the
size of n log n is bounded by n
^{2}, which*is*a polynomial.

**PLEASE GIVE A THUMBSUP IF IT WAS HELPFUL AND LEAVE A
COMMENT FOR ANY QUERY.**

**THANKS.**

Question 1
a) To show that 3-CNF is NP-complete, we take some NP-complete
problem, say SAT, and find a polynomial-time reduction from SAT to
3-CNF. Illustrate a polynomial-time reduction that takes as input
an input F of SAT F = (¬x1 ∨ x2 ∨ x3) ∧ (x4 ⇔ ¬x5) and outputs an
input f(F) of 3-CNF so that f(F) is a “yes” instance of 3-CNF iff F
is a “yes” instance of SAT.
b) Let F be an input to...

Problem 4 . Hibbard’s gap sequence for Shellsort is
defined as follows.
2 k − 1, 2 k−1 − 1, 2 k−2 − 1, . . . , 7, 3, 1
where k is the largest number satisfying 2k − 1 < N.
(b) Implement Shellsort with Hibbard’s gap sequence, with
Shell’s gap sequence, and with a gap sequence of your own
invention, and compare them on three input/output examples for
duplicate-free arrays of size 10, 100, and 1000 (one...

1. Suppose you are given 3 algorithms A1, A2 and A3 solving the
same problem. You know that in the worst case the running times are
T1(n) = (10^4)n, T2(n) = 10n , T3(n) = (10^3)(n^3) log10 n (a) Which algorithm is the
fastest for very large inputs? Which algorithm is the slowest for
very large inputs? (Justify your answer.) (b) For which problem
sizes is A1 the best algorithm to use (out of the three)? Answer
the same question...

Given a directed acyclic graph G= (V,E), vertex s∈V, design a
dynamic programming algorithm to compute the number of distinct
paths from s to v for any v∈V.
1. Define subproblems
2. Write recursion
3. Give the pseudo-code
4. Analyze the running time.

You are given a directed acyclic graph G(V,E), where each vertex
v that has in-degree 0 has a value value(v) associated with it. For
every other vertex u in V, define Pred(u) to be the set of vertices
that have incoming edges to u. We now define value(u) = ?v∈P red(u)
value(v). Design an O(n + m) time algorithm to compute value(u) for
all vertices u where n denotes the number of vertices and m denotes
the number of edges...

You are given the independent jobs A(5), B(7), C(10), D(12),
E(6), F(4), G(3).
(a) Using the alphabetical order priority list above, if the
jobs are scheduled on 3 processors, what is the completion
time?
(b) If the decreasing time algorithm is used to schedule the
jobs on 3 processors, what is the completion time? 21 Incorrect:
Your answer is incorrect.
(c) If the decreasing time algorithm is used to schedule the
jobs on 3 processors, which is the second job...

An exponential algorithm requires 4^n (four to the power n)
steps to solve a problem with an input of size n. Suppose
it has been found that using today's computer, a direct
implementation of that algorithm would be able to handle an input
size of 30 in 10 years. If the computer is speeded up by a factor
of 100 (with no other changes), what input size can be processed in
the same time? Explain your answer.
(Hint: speeding up...

We are given the following CSP problem.
The variables and domains are as follows.
A: {4, 5, 6, 7, 8}
B: {10, 20, 30, 40}
C: {2, 3, 4}
D: {28, 43, 56, 77, 94, 114}
The constraints are:
A + C is odd.
A + D is a square of an integer.
B + D < 60.
Solve this problem using the following heuristics and
algorithms.
• Use backtracking search.
• For variable ordering, use MRV. If there are...

Consider the intitial value problem x2y''+2xy'-12y=0,
y(1)=4, y'(1)=5 How many solutions does this problem have on the
interval I=(0, positive infinity). Explain your answer

I have the following problem. Of the problem, I think about (a)
as follows, but I cannot understand (b). Please tell me the
solution to the problem of (b) .
the problem:
Suppose you are in charge of setting the price for commercial
advertisements shown during Enemies, a top network television show.
There is a 60-minute slot for the show. However, the running time
for the show itself is only 30 minutes. The rest of the time can be
sold...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 4 minutes ago

asked 21 minutes ago

asked 26 minutes ago

asked 26 minutes ago

asked 29 minutes ago

asked 43 minutes ago

asked 56 minutes ago

asked 59 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago