Algorithm
homework | Algorithm | assignment代写 – 这是一个Algorithm面向对象设计的practice, 考察Algorithm的理解, 涉及了Algorithm等代写方面, 这个项目是assignment代写的代写题目
COMP2119A Introduction to Data Structures and Algorithms homework 3 Due Date:7pm, Dec 4, 2022
Rules: discussion of the problems is permitted, but writing the assignment together is not (i.e. you are not allowed to see the actual pages of another student). Please make your answers precise and concise.
Course Outcomes
- [O1]. Mathematics foundation
- [O2]. Basic data structures
- [O3]. Problem solving
- [O4]. Implementation
- [O1](20 pts) Assume the array sizenis large enough. (a) What is the worst-case asymptotic running time of heap-sort? (b) What is the worst-case asymptotic running time of merge-sort? (c) What is the worst-case asymptotic running time of quick-sort? (d) Can heap-sort be done in-place? (e) Can merge-sort be done in-place? (f) Can quick-sort be done in-place? (g) Consider one item in an array that is sorted with mergesort. In asymptotic (big-O) terms, how many times can that one item move to a different location? (h) What is the asymptotic running time of quick-sort if the array is already sorted (or almost sorted) and the pivot-selection strategy picks the leftmost element in the range-to-be-sorted? (i) What is the asymptotic running time of quick-sort if the array is already sorted (or almost sorted) and the pivot-selection strategy picks the rightmost element in the range-to-be-sorted? (j) What is the asymptotic running time of quick-sort if the array is already sorted (or almost sorted) and the pivot-selection strategy picks the middle element in the range-to-be-sorted? In-place: Basically it means usingO(1) extra space. Checkhttps://en.wikipedia. org/wiki/In-place_algorithm. Choose answer for each question from{yes, no, O(nlogn),O(n^2 ),O(logn),O(n), O(
n),O(log logn)}. You do not need to prove your answer.
- [O3](25 pts) Modify randomized quick-sort to find thek-th smallest integer in an unsorted arrayA[1..n] of distinct integers. Your Algorithm should run in expected O(n) time.
- [O2](35 pts) You are given an integerband analmost sortedarrayA[1..n] of distinct integers, where each element can be misplaced by at mostbpositions. (i.e. the sorted position of thei-th elementA[i] is at leastiband at mosti+b.) You are asked to design algorithms to sort the arrayA. You need to optimize your running time and extra space. Analyze the running time and the extra space in terms ofnandb. [Hint: Modify selection sort? Use a heap?]
- [O3, O4](35 pts) There is a set ofngoods, and each goodiis labelled with a price pi, 0in 1 , 0 < pi 109. They are sorted in an increasing order with respect to the price at the beginning, andmaximum adjacent distance distis defined as the maximum difference between two adjacent elementswhen they are sorted, dist= max 0 i<n 1 (pi+1pi). Now, somehow, the goods are shuffled, so they may be no longer sorted. For example, after shuffle, price array is [14, 5 , 16. 12 , 11. 5 , 3. 2 ,7], anddist= 4. 5. Intuitively, we can just sort the shuffled array, and then find the maximum ad- jacent distance. However, it takes at leastO(nlogn) if we apply comparison-based sorting algorithms. Moreover, the price is a real number, so counting sort is also not applicable. The following algorithm findsdistin linear time. Fill in the blanks to complete the algorithm. double findMaxAdjDist(vector
& nums) { int size = nums.size(); if(size ==1 || size == 0) return 0; double min_v = 1000000001,max_v=-1; // min value and max value in nums // find the min and max value for( int i = 0;i < size; i++) { if (nums[i] > max_v) max_v = nums[i]; if (1._____________) 2._____________; }
double avg_dist = (max_v-min_v)/(size-1); // dist should be at
least avg_dist
if (avg_dist==0) return 0;
// bucket[i]: [min+i*avg_dist, min+(i+1)*avg_dist)
// bucket_min[i]: min value in bucket[i]
// bucket_max[i]: max value in bucket[i]
vector<double> bucket_min(size, 1000000001);
vector<double> bucket_max(size, -1);
int tmp;
for( int i = 0;i <= size-1; i++)
{
tmp = floor((nums[i]-min_v)/avg_dist);
if(nums[i]>bucket_max[tmp]) bucket_max[tmp] = nums[i];
if(nums[i]<bucket_min[tmp]) bucket_min[tmp] = nums[i];
}
double dist = -1,curr_max;
// If we go through each bucket, assume currently we are visiting
bucket[i]. curr_max is the max value in buckets from bucket[0] to
bucket[i]. Usually bucket_max[i] is the max value. However, bucket[
i] may be empty, and thats the reason why we need curr_max.
for( int i = 0;i < size-1; i++)
{
if(bucket_max[i]!=-1) 3.___________________;
if(bucket_max[i+1] != -1 && 4.______________)
5.____________________________;
}
return dist;
}