当前位置:天才代写 > 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 > Algorithm作业代写 算法设计代写

Algorithm作业代写 算法设计代写

2021-09-29 17:09 星期三 所属: 作业代写,留学生作业代写-北美、澳洲、英国等靠谱代写 浏览:718

CSC 445 Homework 1 

Algorithm作业代写 (1)(Best-case time) (10 points)  Show how to take nearly any algorithm (even a poor one), and modify it so that it has good best-case time.

The questions are drawn from Chapters 1 and 2 of the text, and from the introductory lectures in class on algorithm design for the Maximum Sum Subarray Problem. The homework is worth a total of 100 points.

For questions that ask you to design an algorithm, you should:

(i) describe an algorithm for the problem using prose and pictures,
(ii) argue that your algorithm is correct, and
(iii) analyze the running time of your algorithm.

Pseudocode is not required, but do clearly explain the ideas behind your algorithm. As a general rule, only give high-level pseudocode if it aids the time analysis of your algorithm, or if it is needed to clarify the steps.

Remember to (a) start each problem on a new page, and (b) put your answers in the correct order. If you can’t solve a problem, state this, and write only what you know to be correct. Neatness and conciseness counts.

 

(1)(Best-case time) (10 points)  Algorithm作业代写

Show how to take nearly any algorithm (even a poor one), and modify it so that it has good best-case time.

To answer this question, describe a procedure that (1) takes as input a problem state-ment P together with an algorithm A that solves P, and (2) outputs a new algorithm Afor whose best-case running time is “as good as possible.” An intelligent human being (such as yourself) should be able to carry out your procedure.

(Note: The original algorithm A might be very ineffiffifficient. So what does this tell you about best-case time?)

 

(2)(Counting flflips) (20 points)  Algorithm作业代写

A flip in an array A[1:n] of numbers is a pair of indices (i, j) such that i < j and A[i] > A[j]. In other words, a flflip is a pair of elements that are not in sorted order.

(a) (10 points) Find an array of length n over the elements {1, . . . , n} that maximizes the number of flflips, and prove that it is optimal.

(b) (10 points) Suppose you run insertion sort on an array of length n that has k flips. Derive a tight big-O-bound on the running time of insertion sort as a function of both n and k, and explain your analysis.

(Note: Recall that insertion sort processes increasingly longer prefifixes of the input array. After having sorted prefifix A[1:i], it sorts prefifix A[1:i+1] by inserting element A[i+1] into its correct sorted position in A[1:i].)

(c) (bonus) (10 points) By modifying merge sort, design an algorithm that counts  the number of flflips in an array of length n in O(n log n) time.

(Note: There can be Θ( ) flflips in an n-element array, so your algorithm cannot explicitly list them and achieve the time bound. It is possible to count flflips without listing them.)

 

Algorithm作业代写
Algorithm作业代写

 

(3)(2-D maximum-sum subarray) (30 points)

In the 2-D Maximum-Sum Subarray Problem, you are given a two-dimensional m × n array A[1 : m, 1 : n] of positive and negative numbers, and you are asked to fifind a subarray A[a : b, c : d], where 1 a b m and 1 c d n, such that the sum of its elements, ∑a i b c j d A[i, j], is maximum.

(a) (30 points) Using exhaustive search, design an algorithm that runs in O() time using O(min{m, n}) working space.

The working space of an algorithm is the memory it uses beyond what is needed to store the input.

(Hint: First design a straightforward algorithm that achieves O( ) time, and then optimize it.)

(b) (bonus) (10 points) Using divide-and-conquer, design an algorithm that runs in O(n log n) time using O(n) working space, by dividing the array vertically.

(Hint: You may need to know that the recurrence

T(m, n) = 2 T(m, n/2) + O(n)

has the solution T(m, n) = O(n log n).)

 

(4)(Minimum positive-sum subarray) (40 points)  Algorithm作业代写

In this variation of the Maximum-Sum Subarray Problem, you are given a one-dimensional array A[1 : n] of positive and negative numbers, and you are asked to fifind a subarray A[i: j] such that the sum of its elements is both: (1) strictly greater than zero, and (2) minimum. In other words, you want to fifind a subarray of smallest positive sum.

(a) (40 points) Using the divide-and-conquer strategy, design an algorithm that fifinds a minimum positive-sum subarray in an array of length n in O(n log² n) time. (Hint: Recall that n numbers can be sorted in O(n log n) worst-case time. You may also need to know that the recurrence

T(n) = 2 T(n/2) + O(n log n)

has the solution T(n) = O(n log² n).)

(b) (bonus) (10 points) Using an incremental strategy, now design an algorithm that fifinds a minimum positive-sum subarray in O(n log n) time. The incremental strategy proceeds by solving a subproblem of size k, adding one element, and updating the solution to solve a problem of size k+1.

(Hint: You may fifind a balanced search tree useful.)

Bonus questions (like Problems 2(c), 3(b), and 4(b) above) are not required. Bonus points are tallied separately, and are considered at the end of the semester for students who fall below the cutoffff for a letter grade.

 

Algorithm作业代写
Algorithm作业代写

 

更多代写:Cs计算机代考 exam考试代考 英国CS代写 论文代写推荐 留学生paper代写 金融学代考

合作平台:随笔代写 论文代写 写手招聘 英国留学生代写

 

 

天才代写-代写联系方式