Search the whole station

# 算法设计代写 hybrid sorting algorithm代写 sums代写

793

## CSC 445 Homework 2 (version 1)

The questions are drawn from the material in Chapters 3, 4, and Appendix A of the text, and the lectures in class on asymptotics, sums, recurrences, and divide-and-conquer. The homework is worth a total of 100 points.

For algorithm design questions, present the ideas behind your algorithm in prose and pictures, be sure to argue that your algorithm is correct, and give your analysis to show the algorithm meets a given time bound. Pseudocode is not required, but may aid your time analysis.

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.

### (2) (Hybrid sorting) (30 points) 算法设计代写

Insertion sort is one of the fastest algorithms in practice for sorting an array of length n when n is small. Its worst-case running time is Θ(n2 ), however, so for large n merge sort will be faster in the worst case as it runs in Θ(n log n) time.

Consider the following hybrid sorting algorithm, which tries to combine the best features of insertion sort and merge sort. Suppose we divide the sorting problem into subproblems as in merge sort, but use insertion sort to solve a subproblem once it is small enough. More precisely, suppose we divide the input array into [n/k] lists of length at most k, sort each list using insertion sort, and then merge them into one sorted list, where k is a parameter.

The following questions analyze the running time of this hybrid algorithm.

(a) (10 points) Show that [n/k] lists, each of length at most k, can be sorted by insertion sort in Θ(nk) worst-case time.

(b) (10 points) Show that the sorted sublists from Part (a) can be merged into one sorted list in Θ(n log(n/k)) worst-case time.

(c) (10 points) By Parts (a) and (b), the hybrid sorting algorithm runs in worst-case time Θ(nk + n log(n/k)). We would like to choose k as a function of n so that the worst-case order of growth for this hybrid algorithm is no worse than the order of growth for merge sort. What is the fastest rate of growth of k for which this holds?Be sure to prove your answer.

(Hint: Answering this requires two steps: (1) coming up with a function f(n)

such that if k = Θ(f(n)), the hybrid algorithm runs in O(n log n) time; and (2) showing that if k = ω(f(n)), the hybrid algorithm runs in ω(n log n) time.)

### (3) (Understanding asymptotics) (25 points) 算法设计代写

(a) (15 points) Order the following functions according to their rate of growth. Specifically, group the functions into equivalence classes such that functions f and g are in the same class iff f  Θ(g), and then order the equivalence classes from slowest to fastest growing.

For each successive pair of functions (f, g) in your order, state the relationship between f and g, namely either f  Θ(g) or f  o(g).

(Hint: First form a rough initial order of the functions, and then use insertion sort on this list to obtain the fifinal order. To determine the relationship between two functions, take a limit of their ratio, or use the list of asymptotic properties given in class.)

(b) (10 points) Using the definition of Θ, prove the following.

Theorem

For any two functions f(n) and g(n) that are asymptotically non-negative,

f(n) + g(n) = Θ(max{f(n), g(n)}) .

(c) (bonus) (10 points) Find a function that grows faster than any polynomial, but slower than any exponential. More precisely, find a function f(n) such that both f ∈ ω(na ) for all a, and f ∈ o(bn ) for all b > 1, where a and b are constants. Prove that your function satisfies these properties.

### (4) (Solving recurrences) (20 points) 算法设计代写

Derive a Θ-bound on the solution to each of the following recurrences. Do not worry about taking floors or ceilings of arguments.

(a) T(n) = 4 T(n/2) + n2n.

(b) T(n) = 32 T(n/4) + n2n.

(c) T(n) = 3 T(n/2) + n lg n.

(d) T(n) = 3 T(n/3) + n lg n.

(e) (bonus) (10 points) T(n) = T(√n) + 1.

### (5) (Reducing kth-smallest to median-finding) (15 points)

If we have an algorithm that finds the kth-smallest element of an n element set, we can obtain an algorithm for finding the median element simply by calling the kth-smallest algorithm with k = [ (n+1)/2] . This question asks you to do the converse.

Given an algorithm that finds the median element of an n element set in Θ(n) time, design an algorithm that finds the kth-smallest element for arbitrary k in Θ(n) time using the median-finding algorithm. Be sure to analyze the running time of your algorithm.

(Note: Do not invoke the linear-time kth-smallest algorithm presented in class and the book. You must reduce the problem of finding the kth-smallest element to the problem of finding the median.)

Note that Problems (3)(c) and (4)(e) are bonus questions, and are not required.

### Related recommendations

• #### 物理攻击与对策代写 CS579/ECE599代写 算法代写 Python代写

193

CS579/ECE599 Assignment Homework 1 物理攻击与对策代写 Please complete this assignment (100 pts total) and submit your report/program code on Canvas (all files compressed in one .zip witho...

View details
• #### 算法设计考核代写 c++考核代写 c++代写 程序设计代写

768

C++ 算法设计考核代写 一、考核题目 （一）病毒株种类 [问题描述] 2019年末一种从未出现过的新型病毒开始在全球迅速蔓延，并且不断变异，人类社会面临了极大的威胁。全球科学家开始共同抗疫。科学家通过研究...

View details
• #### 算法作业代写 Algorithm代写 CS代写 cs算法课业代写

767

Algorithm in Action CSCI-570 Homework 4 算法作业代写 1 Compute Max-Flow And Min-Cut 2 Escape From the Building In this problem, we need to decide whether there is a feasible plan for all th...

View details
• #### 高效算法与难题代写 Efficient Algorithms and Intractable代写

714

CS 170 Efficient Algorithms and Intractable Problems Homework 4 高效算法与难题代写 Design an efficient algorithm that given a directed graph G determines whether there is a vertex v from wh...

View details
1