Difference between pages "Chapter 11" and "Chapter 4"

From The Algorithm Design Manual Solution Wiki
(Difference between pages)
Jump to navigation Jump to search
 
 
Line 1: Line 1:
=NP-Completeness=
+
=Sorting=
  
===Transformations and Satisfiability===
+
===Applications of Sorting: Numbers===
  
:[[11.1]]. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:
+
:[[4.1]]. The Grinch is given the job of partitioning <math>2n</math> players into two teams of <math>n</math> players each. Each player has a numerical rating that measures how good he or she is at the game. The Grinch seeks to divide the players as ''unfairly'' as possible, so as to create the biggest possible talent imbalance between the teams. Show how the Grinch can do the job in <math>O(n log n)</math> time.
:::<math> (x\or y \or \overline z \or w \or u \or \overline v) \and (\overline x \or \overline
+
[[4.1|Solution]]
y \or z \or \overline w \or u \or v) \and (x \or \overline y \or \overline z \or w \or u \or \overline v)\and (x \or \overline y) </math>
 
[[11.1|Solution]]
 
  
  
:11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
+
:4.2. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, <math>S = {6, 13, 19, 3, 8}</math>, 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
:::<math>(x \or \overline y \or z) \and (\overline x \or y \or \overline z) \and(\overline x \or y \or z) \and (x \or \overline y \or \overline x) </math>
+
:(a) Let <math>S</math> be an ''unsorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''maximizes'' <math>|x-y|</math>. Your algorithm must run in <math>O(n)</math> worst-case time.
 +
:(b) Let <math>S</math> be a ''sorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''maximizes'' <math>|x - y|</math>. Your algorithm must run in <math>O(1)</math> worst-case time.
 +
:(c) Let <math>S</math> be an ''unsorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''minimizes'' <math>|x - y|</math>, for <math>x \neq y</math>. Your algorithm must run in <math>O(n log n)</math> worst-case time.
 +
:(d) Let <math>S</math> be a ''sorted'' array of <math>n</math> integers. Give an algorithm that finds the pair <math>x, y \in S</math> that ''minimizes'' <math>|x - y|</math>, for <math>x \neq y</math>. Your algorithm must run in <math>O(n)</math> worst-case time.
  
  
:[[11.3]]. Prove that 4-SAT is NP-hard.
+
:[[4.3]]. Take a list of <math>2n</math> real numbers as input. Design an <math>O(n log n)</math> algorithm that partitions the numbers into <math>n</math> pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus, the third partition has 10 as its maximum sum, which is the minimum
[[11.3|Solution]]
+
over the three partitions.
 +
[[4.3|Solution]]
  
  
:11.4. ''Stingy'' SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer <math>k</math>, find a satisfying assignment in which at most <math>k</math> variables are true, if such an assignment exists. Prove that stingy SAT is NP-hard.
+
:4.4. Assume that we are given <math>n</math> pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an <math>O(n)</math> algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.
 +
:For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).
  
  
:[[11.5]]. The ''Double SAT'' problem asks whether a given satisfiability problem has '''at least two different satisfying assignments'''. For example, the problem <math>{{v1, v2}, {v_1, v_2}, {v_1, v_2}}</math> is satisfiable, but has only one solution <math>(v_1 =F, v_2 = T)</math>. In contrast, <math>{{v_1, v_2}, {v_1, v_2}}</math> has exactly two solutions. Show that Double-SAT is NP-hard.
+
:[[4.5]]
[[11.5|Solution]]
 
  
  
:11.6. Suppose we are given a subroutine that can solve the traveling salesman decision problem on page 357 in (say) linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.
+
:4.6
  
  
:[[11.7]]. Implement a SAT to 3-SAT reduction that translates satisfiability instances into equivalent 3-SAT instances.
+
:[[4.7]]
[[11.7|Solution]]
 
  
  
:11.8. Design and implement a backtracking algorithm to test whether a set of clause sets is satisfiable. What criteria can you use to prune this search?
+
:4.8
  
  
:[[11.9]]. Implement the vertex cover to satisfiability reduction, and run the resulting clauses through a satisfiability solver code. Does this seem like a practical way to compute things?
+
:[[4.9]]
[[11.9|Solution]]
 
  
===Basic Reductions===
 
  
:11.10. An instance of the ''set cover'' problem consists of a set <math>X</math> of <math>n</math> elements, a family <math>F</math> of subsets of <math>X</math>, and an integer <math>k</math>. The question is, does there exist <math>k</math> subsets from <math>F</math> whose union is <math>X</math>? For example, if <math>X = \{1,2,3,4\}</math> and <math>F = \{ \{1,2\}, \{2,3\}, \{4\}, \{2,4\} \}</math>, there does not exist a solution for <math>k=2</math>, but there does for <math>k=3</math> (for example, <math> \{1,2\}, \{2,3\}, \{4\}</math>). Prove that set cover is NP-complete with a reduction from vertex cover.
+
:4.10
  
  
:[[11.11]]. The ''baseball card collector problem'' is as follows. Given packets <math>P_1, \ldots, P_m</math>, each of which contains a subset of this year's baseball cards, is it possible to collect all the year's cards by buying <math>\leq k</math> packets? For example, if the players are <math> \{Aaron, Mays, Ruth, Steven \} </math> and the packets are
+
:[[4.11]]
:::<math> \{ \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\}, \{Mays,Steven\} \}, </math>
 
:there does not exist a solution for <math>k=2</math>, but there does for <math>k=3</math>, such as
 
:::<math> \{Aaron,Mays\}, \{Mays,Ruth\}, \{Steven\} </math>
 
:Prove that the baseball card collector problem is NP hard using a reduction from vertex cover.
 
  
 +
===Applicatoins of Sorting: Intervals and Sets===
  
:11.12. The ''low-degree spanning tree problem'' is as follows. Given a graph <math>G</math> and an integer <math>k</math>, does <math>G</math> contain a spanning tree such that all vertices in the tree have degree ''at most'' <math>k</math> (obviously, only tree edges count towards the degree)? For example, in the following graph, there is no spanning tree such that all vertices have a degree less than three.
+
:4.12
\fixedfigsize{pictures/lowdegree.png}{1.0in}
 
#Prove that the low-degree spanning tree problem is NP-hard with a reduction from Hamiltonian ''path''.
 
#Now consider the ''high-degree spanning tree problem'', which is as follows. Given a graph <math>G</math> and an integer <math>k</math>, does <math>G</math> contain a spanning tree whose highest degree vertex is ''at least'' <math>k</math>? In the previous example, there exists a spanning tree with a highest degree of 8. Give an efficient algorithm to solve the high-degree spanning tree problem, and an analysis of its time complexity.
 
  
  
:[[11.13]].In the minimum element set cover problem, we seek a set cover <math>S \subseteq C</math> of a universal set <math>U = {1, . . . , n}</math> such that sum of the sizes of the subsets in <math>S</math> is at most <math>k</math>.
+
:[[4.13]]
::(a) Show that <math>C = {{1, 2, 3}, {1, 3, 4}, {2, 3, 4}, {3, 4, 5}}</math> has a cover of size 6, but none of size 5 because of a repeated element.
 
::(b) Prove that this problem is NP-hard. (Hint: set cover remains hard if all subsets are of the same size.)
 
[[11.13|Solution]]
 
  
  
:11.14. The ''half-Hamiltonian cycle problem'' is, given a graph <math>G</math> with <math>n</math> vertices, determine whether <math>G</math> has a simple cycle of length exactly <math>[n/2]</math>, where the floor function rounds its input down to the nearest integer. Prove that this problem is NP-hard.
+
:4.14
  
  
:[[11.15]]. The 3-phase power balance problem asks for a way to partition a set of n positive integers into three sets <math>A</math>, <math>B</math>, or <math>C</math> such that <math>\sum_{i} a_i = \sum_{i} b_i = \sum_{i} c_i</math>. Prove that this problem is NP-hard using a reduction from integer partition or subset sum (see Section 10.5 (page 329)).
+
:[[4.15]]
[[11.15|Solution]]
 
  
  
:11.16. Show that the following problem is NP-complete:
+
:4.16
:* ''Problem:'' Dense subgraph
 
:* ''Input:'' A graph <math>G</math>, and integers <math>k</math> and <math>y</math>.
 
:* ''Output:'' Does <math>G</math> contain a subgraph with exactly <math>k</math> vertices and at least <math>y</math> edges?
 
  
  
:[[11.17]]. Show that the following problem is NP-complete:
+
===Heaps===
:* ''Problem:'' Clique, no-clique
 
:* ''Input:'' An undirected graph <math>G=(V,E)</math> and an integer <math>k</math>.
 
:* ''Output:'' Does <math>G</math> contain both a clique of size <math>k</math> and an independent set of size <math>k</math>.
 
[[11.17|Solution]]
 
  
 +
:[[4.17]]
  
:11.18. n ''Eulerian cycle'' is a tour that visits every edge in a graph exactly once. An ''Eulerian subgraph'' is a subset of the edges and vertices of a graph that has an Eulerian cycle. Prove that the problem of finding the number of edges in the largest Eulerian subgraph of a graph is NP-hard. (Hint: the Hamiltonian circuit problem is NP-hard even if each vertex in the graph is incident upon exactly three edges.)
 
  
 +
:4.18
  
:[[11.19]]. Show that the following problem is NP-hard:
 
:*''Problem:'' Maximum Common Subgraph
 
:*''Input:'' Two graphs <math>G_1 = (V_1, E_1)</math> and <math>G_2 = (V_2, E_2)</math>, and a budget <math>b</math>.
 
:*Output: Two sets of nodes <math>S_1 \subseteq V_1</math> and <math>S_2 \subseteq V_2</math> whose deletion leaves at least <math>b</math> nodes in each graph, and makes the two graphs identical.
 
[[11.19|Solution]]
 
  
 +
:[[4.19]]
  
:11.20. A ''strongly independent'' set is a subset of vertices <math>S</math> in a graph <math>G</math> such that for any two vertices in <math>S</math>, there is no path of length two in <math>G</math>. Prove that strongly independent set is NP-hard.
 
  
 +
:4.20
  
:[[11.21]]. A ''kite'' is a graph on an even number of vertices, say <math>2n</math>, in which <math>n</math> of the vertices form a clique and the remaining <math>n</math> vertices are connected in a tail that consists of a path joined to one of the vertices of the clique. Given a graph and a goal g, the ''max kite'' problem asks for a subgraph that is a kite and contains <math>2g</math> nodes. Prove that ''max kite'' is NP-hard.
 
[[11.21|Solution]]
 
  
===Creative Reductions===
+
===Quicksort===
  
:11.22. Prove that the following problem is NP-complete:
+
:[[4.21]]
:* ''Problem:'' Hitting Set
 
:* ''Input:'' A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>.
 
:* ''Output:'' Does <math>S</math> contain a subset <math>S'</math> such that <math>|S'| \leq k</math> and each subset in <math>C</math> contains at least one element from <math>S'</math>?
 
  
  
:[[11.23]]. Prove that the following problem is NP-complete:
+
:4.22
:* ''Problem:'' Knapsack
 
:* ''Input:'' A set <math>S</math> of <math>n</math> items, such that the <math>i</math>th item has value <math>v_i</math> and weight <math>w_i</math>.  Two positive integers: weight limit <math>W</math> and value requirement <math>V</math>.
 
:* ''Output:'' Does there exist a subset <math>S' \in S</math> such that <math>\sum_{i \in S'} w_i \leq W</math> and <math>\sum_{i \in S'} v_i \geq V</math>?
 
:(Hint: start from integer partition.)
 
[[11.23|Solution]]
 
  
  
:11.24. Prove that the following problem is NP-complete:
+
:[[4.23]]
:* ''Problem:'' Hamiltonian Path
 
:* ''Input:'' A graph <math>G</math>, and vertices <math>s</math> and <math>t</math>.
 
:* ''Output:'' Does <math>G</math> contain a path which starts from <math>s</math>, ends at <math>t</math>, and visits all vertices without visiting any vertex more than once? (Hint: start from Hamiltonian cycle.)
 
  
  
:[[11.25]]. Prove that the following problem is NP-complete:
+
:4.24
:* ''Problem:'' Longest Path
 
:* ''Input:'' A graph <math>G</math> and positive integer <math>k</math>.
 
:* ''Output:'' Does <math>G</math> contain a path that visits at least <math>k</math> different vertices without visiting any vertex more than once?
 
[[11.25|Solution]]
 
  
  
:11.26. Prove that the following problem is NP-complete:
+
:[[4.25]]
:* ''Problem:'' Dominating Set
 
:* ''Input:'' A graph <math>G=(V,E)</math> and positive integer <math>k</math>.
 
:* ''Output:'' Is there a subset <math>V' \in V</math> such that <math>|V'|\leq k</math> where for each vertex <math>x \in V</math> either <math>x \in V'</math> or there exists an edge <math>(x,y)</math>, where <math>y \in V'</math>.
 
  
  
:[[11.27]]. Prove that the vertex cover problem (does there exist a subset <math>S</math> of <math>k</math> vertices in a graph <math>G</math> such that every edge in <math>G</math> is incident upon at least one vertex in <math>S</math>?) remains NP-complete even when all the vertices in the graph are restricted to have even degrees.
+
:4.26
[[11.27|Solution]]
 
  
  
:11.28. Prove that the following problem is NP-complete:
+
:[[4.27]]
:* ''Problem:'' Set Packing
 
:* ''Input:'' A collection <math>C</math> of subsets of a set <math>S</math>, positive integer <math>k</math>.
 
:* ''Output:'' Does <math>S</math> contain at least <math>k</math> disjoint subsets (i.e., such that none of these subsets have any elements in common?)
 
  
  
:[[11.29]]. Prove that the following problem is NP-complete:
+
===Mergesort===
:* ''Problem:'' Feedback Vertex Set
 
:* ''Input:'' A directed graph <math>G=(V,A)</math> and positive integer <math>k</math>.
 
:* ''Output:'' Is there a subset <math>V' \in V</math> such that <math>|V'|\leq k</math>, such that deleting the vertices of <math>V'</math> from <math>G</math> leaves a DAG?
 
[[11.29|Solution]]
 
  
 +
:4.28
  
:11.30. Give a reduction from Sudoku to the vertex coloring problem in graphs. Specifically, describe how to take any partially filled Sudoku board and construct a graph that can be colored with nine colors iff the Sudoku board is solvable.
 
  
===Algorithms for Special Cases===
+
:[[4.29]]
  
:[[11.31]]. A Hamiltonian path <math>P</math> is a path that visits each vertex exactly once. The problem of testing whether a graph <math>G</math> contains a Hamiltonian path is NP-complete.
 
There does not have to be an edge in <math>G</math> from the ending vertex to the starting vertex of <math>P</math>, unlike in the Hamiltonian cycle problem. Give an <math>O(n+m)</math>-time algorithm to test whether a directed acyclic graph <math>G</math> (a DAG) contains a Hamiltonian path. (Hint: think about topological sorting and DFS.)
 
[[11.31|Solution]]
 
  
 +
:4.30
  
:11.32. Consider the ''k''-clique problem, which is the general clique problem restricted to graphs in which every vertex has degree at most <math>k</math>. Prove that ''k''-clique has an efficient algorithm for any given <math>k</math>, meaning that <math>k</math> is a constant.
 
  
 +
===Other Sorting Alogrithims===
  
:[[11.33]]. The <math>2</math>-SAT problem is, given a Boolean formula in 2-conjunctive normal form (CNF), to decide whether the formula is satisfiable. <math>2</math>-SAT is like <math>3</math>-SAT, except that each clause can have only two literals. For example, the following formula is in <math>2</math>-CNF: <math> (x_1 \or x_2) \and (\bar{x}_2 \or x_3) \and (x_1 \or \bar{x}_3) </math>
+
:[[4.31]]
:Give a polynomial-time algorithm to solve <math>2</math>-SAT.
 
[[11.33|Solution]]
 
  
  
:11.34, Show that the following problems are in NP:
+
:4.32
#Does graph <math>G</math> have a simple path (i.e., with no vertex repeated) of length <math>k</math>? \#Is integer <math>n</math> composite (i.e., not prime)?
 
#Does graph <math>G</math> have a vertex cover of size <math>k</math>?
 
  
  
:[[11.35]]. Until 2002, it was an open question whether the decision problem ''Is integer <math>n</math> a composite number, in other words, not prime?'' can be computed in time polynomial in the size of its input. Why doesn't the following algorithm suffice to prove it is in P, since it runs in <math>O(n)</math> time?
+
:[[4.33]]
  PrimalityTesting(<math>n</math>)
+
 
      composite := <math>false</math>
+
 
      for i := 2 to <math>n-1</math> do
+
:4.34
        if <math>(n\,\bmod\,i) = 0</math> then
+
 
            composite := <math>true</math>
+
 
[[11.35|Solution]]
+
:[[4.35]]
 +
 
 +
 
 +
:4.36
 +
 
 +
 
 +
:[[4.37]]
 +
 
 +
 
 +
:4.38
 +
 
 +
 
 +
===Lower Bounds===
 +
 
 +
:[[4.39]]
 +
 
 +
 
 +
:4.40
 +
 
 +
 
 +
===Searching===
 +
 
 +
:[[4.41]]
 +
 
 +
 
 +
:4.42
 +
 
 +
 
 +
===Implementaion Challenges===
 +
 
 +
:[[4.43]]
 +
 
 +
 
 +
:4.44
 +
 
 +
 
 +
:[[4.45]]
 +
 
 +
 
 +
:4.46
 +
 
 +
===Interview Problems===
 +
 
 +
:[[4.47]]
 +
 
 +
 
 +
:4.48
 +
 
 +
 
 +
:[[4.49]]
 +
 
 +
 
 +
:4.50
 +
 
 +
 
 +
:[[4.51]]
 +
 
 +
 
 +
:4.52
 +
 
 +
 
 +
:[[4.53]]
  
  
 
Back to [[Chapter List]]
 
Back to [[Chapter List]]

Revision as of 15:28, 18 September 2020

Sorting

Applications of Sorting: Numbers

4.1. The Grinch is given the job of partitioning [math]\displaystyle{ 2n }[/math] players into two teams of [math]\displaystyle{ n }[/math] players each. Each player has a numerical rating that measures how good he or she is at the game. The Grinch seeks to divide the players as unfairly as possible, so as to create the biggest possible talent imbalance between the teams. Show how the Grinch can do the job in [math]\displaystyle{ O(n log n) }[/math] time.

Solution


4.2. For each of the following problems, give an algorithm that finds the desired numbers within the given amount of time. To keep your answers brief, feel free to use algorithms from the book as subroutines. For the example, [math]\displaystyle{ S = {6, 13, 19, 3, 8} }[/math], 19 - 3 maximizes the difference, while 8 - 6 minimizes the difference.
(a) Let [math]\displaystyle{ S }[/math] be an unsorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that maximizes [math]\displaystyle{ |x-y| }[/math]. Your algorithm must run in [math]\displaystyle{ O(n) }[/math] worst-case time.
(b) Let [math]\displaystyle{ S }[/math] be a sorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that maximizes [math]\displaystyle{ |x - y| }[/math]. Your algorithm must run in [math]\displaystyle{ O(1) }[/math] worst-case time.
(c) Let [math]\displaystyle{ S }[/math] be an unsorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that minimizes [math]\displaystyle{ |x - y| }[/math], for [math]\displaystyle{ x \neq y }[/math]. Your algorithm must run in [math]\displaystyle{ O(n log n) }[/math] worst-case time.
(d) Let [math]\displaystyle{ S }[/math] be a sorted array of [math]\displaystyle{ n }[/math] integers. Give an algorithm that finds the pair [math]\displaystyle{ x, y \in S }[/math] that minimizes [math]\displaystyle{ |x - y| }[/math], for [math]\displaystyle{ x \neq y }[/math]. Your algorithm must run in [math]\displaystyle{ O(n) }[/math] worst-case time.


4.3. Take a list of [math]\displaystyle{ 2n }[/math] real numbers as input. Design an [math]\displaystyle{ O(n log n) }[/math] algorithm that partitions the numbers into [math]\displaystyle{ n }[/math] pairs, with the property that the partition minimizes the maximum sum of a pair. For example, say we are given the numbers (1,3,5,9). The possible partitions are ((1,3),(5,9)), ((1,5),(3,9)), and ((1,9),(3,5)). The pair sums for these partitions are (4,14), (6,12), and (10,8). Thus, the third partition has 10 as its maximum sum, which is the minimum

over the three partitions. Solution


4.4. Assume that we are given [math]\displaystyle{ n }[/math] pairs of items as input, where the first item is a number and the second item is one of three colors (red, blue, or yellow). Further assume that the items are sorted by number. Give an [math]\displaystyle{ O(n) }[/math] algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).


4.5


4.6


4.7


4.8


4.9


4.10


4.11

Applicatoins of Sorting: Intervals and Sets

4.12


4.13


4.14


4.15


4.16


Heaps

4.17


4.18


4.19


4.20


Quicksort

4.21


4.22


4.23


4.24


4.25


4.26


4.27


Mergesort

4.28


4.29


4.30


Other Sorting Alogrithims

4.31


4.32


4.33


4.34


4.35


4.36


4.37


4.38


Lower Bounds

4.39


4.40


Searching

4.41


4.42


Implementaion Challenges

4.43


4.44


4.45


4.46

Interview Problems

4.47


4.48


4.49


4.50


4.51


4.52


4.53


Back to Chapter List