**CSC 445 Homework 3 **

**CSC 445 Homework 3**

代写算法设计 The questions are drawn from the material in class, and in Chapters 9 and 15 of the text, on finding the kth-smallest element,

The questions are drawn from the material in class, and in Chapters 9 and 15 of the text, on finding the *k** th-smallest element*, and the

*technique.*

*dynamic programming*The homework is worth a total of 100 points. When point breakdowns are not given for the parts of a problem, each part has equal weight.

For general algorithm design questions, (i) present the ideas behind your algorithm in prose and pictures, (ii) argue that your algorithm is correct, and (iii) show your analysis that the algorithm meets the given time bound. Pseudocode is not required, but may aid in your analysis.

**For questions that ask you to design a ***dynamic programming *algorithm, be sure to use the four-part framework: 代写算法设计

*algorithm, be sure to use the four-part framework: 代写算法设计*

*dynamic programming*(1) * characterize *the recursive structure of an optimal solution,

(2) * derive *a recurrence equation for the value of an optimal solution,

(3) * evaluate *the recurrence bottom-up in a table, and

(4) * recover *an optimal solution from the table of solution values.

You will be graded on each part. Be sure to analyze the time for Parts (3) and (4) of your algorithm.

Remember to (a) start each problem on a * new page*, and (b) put your answers in the

*. If you can’t solve a problem, state this, and write only what you know to be correct. Neatness and conciseness counts.*

*correct order*

**(1) (Finding elements near the median) (10 points) 代写算法设计**

Given an unsorted array * A *of

*distinct numbers and an integer*

*n**, where 1*

*k*

*≤*

*k*

*≤**, design an algorithm that finds the*

*n**numbers in*

*k**that are*

*A**to the median of*

*closest in value**in Θ(*

*A**) time. (Note: Finding the numbers that are closest in*

*n**to the median has no relationship in general with how these numbers are ordered in the unsorted array*

*value**.)*

*A*

**(2) (Finding quantiles) (20 points)**

For a set * S *of

*numbers and an integer*

*n**, where 1*

*k*

*≤*

*k*

*≤**, the*

*n*

*k**of*

*th-quantiles**are*

*S*

*k**1 elements from*

*−**whose ranks in*

*S**divide the sorted set into*

*S**groups that are of equal size (to within one unit).*

*k*Given an unsorted array * A *of

*distinct numbers, design an algorithm that finds the*

*n**th-quantiles of*

*k**in*

*A**(*

*O**log*

*n**) time.*

*k*(Note: As an illustration, the 4-quantiles of a set of scores are the values that define the 25-, 50-, and 75-percentile cutoffs. Similarly, the 10-quantiles of a set are the values that define the 10-, 20-, 30-, …., and 90-percentile cutoffs.)

**(3) (Answering dynamic ***k*th-smallest queries) (bonus) (10 points) 代写算法设计

*th-smallest queries) (bonus) (10 points) 代写算法设计*

*k*Given a set of * n *numbers, the

*th-smallest element can be found in Θ(*

*k**) time using the algorithm we learned in class. Suppose we have a dynamic set*

*n**of numbers that changes over time, and we want to be able to efficiently support the operations of*

*S*(a) * inserting *a new number into set

*, and*

*S*(b) * finding *the

*th-smallest element in the current set*

*k**, for any*

*S**.*

*k*We could support both operations by representing * S *as an unsorted array

*. Inserting a new element would take just Θ(1) time. Finding the*

*A**th-smallest element, however, would take Θ(*

*k**) time. If there are many*

*n**th-smallest operations executed on set*

*k**, performing all of them will take a large amount of total time. We might like to speed up the time to find the*

*S**th-smallest, at a slight increase in the time to insert an element.Design an algorithm that (a) supports inserting an element into*

*k**in*

*S**(log*

*O**) time, and (b) supports finding the*

*n**th-smallest element of*

*k**in*

*S**(log*

*O**) time as well.*

*n*(Hint: Consider modifying a balanced binary search tree data structure.)

**(4) (Longest increasing subsequence) (20 points) **

Given a string * S *of numbers, an

*of*

*increasing subsequence**is any subsequence*

*S**of*

*T**such that the numbers in*

*S**, read left-to-right across*

*T**, are strictly increasing. For example, if*

*T**= (3*

*S**1*

*,**6*

*,**2*

*,**5*

*,**4), an increasing subsequence of*

*,**is*

*S**= (1*

*T**2*

*,**4).*

*,*Design a dynamic programming algorithm that finds the * longest *increasing subsequence of a string

*of length*

*S**in Θ(*

*n*

*n*^{2}) time.

(Note: Do * not *solve this problem by reducing it to the longest common subsequence problem. Instead design a dynamic programming algorithm from first principles.)

**(5) (Editing strings) (30 points) 代写算法设计**

Given two strings * A*[1 :

*] and*

*m**[1 :*

*B**], the*

*n**between*

*edit distance**and*

*A**is the minimum cost of a script that edits*

*B**into*

*A**. A script is a series of edit operations, each edit operation has a non-negative cost, and the cost of a script is the sum of the costs of its operations.*

*B*The allowed edit operations in a script are:

, which leaves a character unchanged, and has cost 0,*copy*, which replaces a character*substitute*with another character*a*, and has cost*b**c*_{sub},, which adds a character*insert*into a string, and has cost*a**c*_{ins},, which removes a character*delete*from a string, and has cost*a**c*_{del}, and, which replaces two adjacent characters*transpose*in a string by the characters*ab*, and has cost*ba**c*_{tra}.

Design a dynamic programming algorithm to compute the edit distance between * A *and

*and recover the corresponding edit script in Θ(*

*B**) time. You may assume that an optimal script never edits a given character more than once. The costs of operations are part of the input to your algorithm.*

*mn*(Hint: Order the operations in an edit script so they occur left-to-right across string * A*, and then examine the possible ways in which an optimal script could end.)

**(6) (Discrete knapsack) (20 points) 代写算法设计**

In the * discrete knapsack problem*, the input is a collection of

*items with associated weights*

*n*

*w*_{1}

*, w*_{2}

*, . . . , w*

_{n}*and values*

*v*_{1}

*, v*_{2}

*, . . . , v**, and a capacity*

_{n}*. Item*

*k**has weight*

*i*

*w*

_{i}*and value*

*v*

_{i }*. All weights*

_{ }

*w*

_{i}*and the capacity*

*are*

*k**. The output is a subset*

*positive integers**of the items*

*S**1*

*{**2*

*,*

*, . . . , n**, called a knapsack, such that the total weight of all the items in knapsack*

*}**is at most*

*S**, and the total value of all the items in*

*k**is maximum. In other words, a solution to the discrete knapsack problem is an optimal knapsack*

*S**of items that does not exceed the weight capacity*

*S**while having the greatest possible value.*

*k*Design a dynamic programming algorithm that solves the discrete knapsack problem in Θ(* nk*) time.

(Hint: Examine the items in the order 1* , *2

*, and consider knapsacks of all possible capacities.)*

*, . . . , n*Note that Problem (3) is a * bonus *question, and is

*required.*

*not*