Reference no: EM13881358
1. For an undirected graph G = (V, E), a dominating set is a subset S ⊆ V such that for each vertex v ∈ V, v ∈ S or a neighbor u of v is in S. Prove that the dominating set problem DS (G, k) such that the graph C contains a dominating set S of size at most k is NP-complete.
2. We say that a problem (a language) L1 ⊆ A* is a linear-time reducible to problem (a language) L2 ⊆ B* (written L1 < L2) if there exists a linear-time computable function φ: A* → B* such that for all α1 α ∈ L1, if and only if φ(α) ∈ L2.
Suppose we know L1 < L2 (i.e., L1 is linear-time reducible to L2) and L2 < L3. Assume that, the time complexity of L2 is θ(n logn).
(a) What we can say about the time complexity of L1? Justify your answer.
(b) What we can say about the time complexity of L3? Justify your answer.
3. Define the class P and the class NP (try to use own words, if possible).
4. Given a table T with m columns and n rows filled with 0's and l's such that each row has at least one 1, and an integer k such that 1 < k < m. The decision problem is to find whether it is possible to choose k columns in T such that each row has at least one 1 at the intersection with the considered columns. Prove that the above decision problem is NP-complete.
5. Prove that the set cover problem U, F is NP-complete, even if for each element from U we have at most two subsets from the family F that cover this element.
6. For a set cover problem U, F construct a cover using greedy algorithm:
U = {1,2,3,4,5,6, 7}, F= {S1, S2, S3, S4, S5},
S1= (1,2,7), S2 = (3, 4, 7), S3 = (5, 6), S4 = (1, 3, 5), S5 = (2,4).
7. Find the cardinality of a maximum independent set of the following tree using dynamic programming algorithm.
|
Use of preferential duties is inconsistent
: Trying to explain why a country's use of preferential duties is inconsistent with the most-favored nations (MFN) treatment of trading partners by the country.
|
|
Indicate the type of account of oakley inc
: Oakley, Inc., reported the following items in its financial statements. For each item, indicate (1) the type of account (A = asset, L = liability, SE = stockholders' equity, R = revenue, E = expense, D = dividend) and (2) whether it is reported on th..
|
|
Using a search engine, search the phrase sec channel
: This chapter mentioned alleged fraudulent revenue reporting at Coca Cola and McAfee. Using a search engine, search the phrase SEC channel stuffing.
|
|
Draw a complete e-r diagram for the implementation
: The office uses three dental laboratories that provide supplies and services, such as fabricating dentures. Draw a complete E-R Diagram for the implementation.
|
|
What we can say about the time complexity
: What we can say about the time complexity of L1? Justify your answer. What we can say about the time complexity of L3? Justify your answer.
|
|
The completed spreadsheet problem 8-53.xls
: See the completed spreadsheet Problem 8-53.xls on the instructor website. That spreadsheet has two tabs.
|
|
Which of variables would you regard as endogenous
: Which of the variables would you regard as endogenous and which as exogenous?
|
|
Describe the factors involved in innovation systems design
: Describe the factors involved in innovation systems design. Explain the importance of innovation systems.
|
|
How might your experience have been different if the pos
: Briefly describe an example from your personal experience where you purchased something from a company that uses a POS system. How might your experience have been different if the POS system did not exist in the experience you described?
|