Problem 5.1 “近似率”定义

Suppose you have a maximization algorithm, A, that has an approximation ratio of 4. When run on some input π, A(π) = 12. What can you say about the true (correct) answer OPT = OPT(π)?

• OPT ≥ 3
• OPT ≤ 3
• OPT ≥ 12
• OPT ≤ 12
• OPT ≥ 48
• OPT ≤ 48

  Problem 5.2 零钱兑换贪心算法的“近似率”

  What is the approximation ratio of the BETTERCHANGE algorithm?

Problem 5.3 煎饼翻转算法实现

Design an approximation algorithm for the Pancake Flipping problem. What is its approximation ratio?
2016-07-Pancake-Flipping.pdf

Problem 5.4 断点消除算法与最优算法路径输出

Perform the BREAKPOINTREVERSALSORTalgorithm with π = 3 4 6 5 8 1 7 2 and show all intermediate permutations (break ties arbitrarily). Since BREAKPOINTREVERSALSORT is an approximation algorithm, there may be a sequence of reversals that is shorter than the one found by BREAKPOINTREVERSALSORT. Could you find such a sequence of reversals? Do you know if it is the shortest possible sequence of reversals?

Problem 5.5

Find a permutation with no decreasing strips for which there exists a reversal that reduces the number of breakpoints.

Problem 5.6

Can you find a permutation for which BREAKPOINTREVERSALSORT produces four times as many reversals than the optimal solution of the Reversal Sorting problem?

Problem 5.7

A DNA molecule is not always shaped like a line segment. Some simple organisms have a circular DNA molecule as a genome, where the molecule has no beginning and no end. These circular genomes can be visualized as a sequence of integers written along the perimeter of a circle. Two circular sequences would be considered equivalent if you could rotate one of the circles and get the same sequence written on the other.

Devise an approximation algorithm to sort a circular genomeby reversals (i.e., transform it to the identity circular permutation). Evaluate the algorithm’s performance guarantee.

Problem 5.8 更优算法

Devise a better algorithm (i.e., one with a better approximation ratio) for the Sorting by Reversals problem.

Problem 5.9

The swap sorting of permutation π is a transformation of π into the identity permutation by exchanges of adjacent elements. For example, 3142 → 1342 → 1324 → 1234 is a three-step swap sorting of permutation 3124. Problem 5.9 Design an algorithm for swap sorting that uses the minimum number of swaps to sort a permutation.

Design an algorithm for swap sorting that uses the minimum number of swaps to sort a permutation.

Problem 5.10

Design an algorithm for swap sorting that uses the minimum number of swaps to sort a circular permutation.

Problem 5.11

How many permutations on n elements have a single breakpoint? How many per-mutations have exactly two breakpoints? How many permutations have exactly three breakpoints?

Problem 5.12

Given permutations π and σ, a breakpoint between π and σ is defined as a pair of adjacent elements πi and πi+1 in π that are separated in σ. For example, if π = 143256 and σ = 123465, then π1 = 1 and π2 = 4 in π form a breakpoint between π and σ since 1 and 4 are separated in σ. The number of breakpoints between π=01432567 and σ=01234657 is three (14, 25 and 67), while the number of breakpoints between σ and π is also three (12,46 and 57).

Prove that the number of breakpoints between π and σ equals the number of breakpoints between σ and π.

Problem 5.13

Given permutations π1 = 124356, π2 = 143256 and π3 = 123465, compute the number of breakpoints between: (1) π1 and π2 , (2) π1 and π3 , and (3) π2 and π3 .

Problem 5.14

Given the three permutations π1 , π2 , and π3 from the previous problem, find an ancestral permutation σ which minimizes the total breakpoint distance between all three genomes and is the number of breakpoints between πi and σ).

Problem 5.15

Given three permutations π1 , π2 , and π3 from the previous problem, find an ancestral permutation σ which minimizes the total reversal distance between all three genomes and σ.

Analysis of genome rearrangements in multiple genomes corresponds to the following Multiple Breakpoint Distance problem: : given a set of permutations π 1 , . . . , π k , find an ancestral permutation σ such that is minimal, where is the number of breakpoints between πi and σ.

Problem 5.16

Design a greedy algorithm for the Multiple Breakpoint Distance problem and evaluate its approximation ratio.

Problem 5.17

Alice and Bob have been assigned the task of implementing the BREAKPOINTREVERSALSORTapproximation algorithm.

• Bob wants to get home early so he decides to naively implement the algorithm, without putting any thought into performance improvements. What is the run-ning time of his program?
• Alice makes some changes to the algorithm and claims her algorithm achieves the same approximation ratio as Bob’s (4) and runs in time . Give the pseudocode for Alice’s algorithm.
• Not to be outdone, Bob gets a copy of Alice’s algorithm, and makes an improve-ment of his own. He claims that in the case where every strip isincreasing, he can guarantee that there will be a decreasing strip in each of the nexttwo steps (rather than one as in BREAKPOINTREVERSALSORT).Bob believes that this will give his new algorithm a better approximation ratio than the previous algorithms. What is Bob’s improvement, and what approximation ratio does it achieve?

Problem 5.18 motif贪心搜索算法的“近似率”

Design an input for the GREEDYMOTIFSEARCH algorithm that causes the algorithm to output an incorrect result. That is, create a sample that has a strong pattern that is missed because of the greedy nature of the algorithm. If optimalScore is the score of the strongest motif in the sample and greedyScore is the score returned by GREEDYMOTIFSEARCH, how large can optimalScore/greedyScorebe?