PLEASE ANSWER ONLY QUESTIONS 3 AND 4. below I will provide the answers for questions 1 and 2. What is being asked is to

Post by **answerhappygod** » Fri Jul 01, 2022 5:46 am

PLEASE ANSWER ONLY QUESTIONS 3 AND 4. below I will provide theanswers for questions 1 and 2.
What is being asked is to break down and optimize an algorithmusing a divide and conquer approach. For the input buffer, it needsto be sorted using quicksort, and for the output buffer, it needsto be organized using mergesort. Questions 1-4 should behandwritten or posted on a whiteboard to show how it wasmathematically broken down. Assignment is algorithm design.
Please solve algorithm(Divide and Conquer) and its partsusing both quicksort andmergesort. Quicksort is used when reading from inputfile. Mergesort is used when you merge the contents of the temporalfiles from the input buffers to output buffers. Please show allwork.
Please DO NOT SEND CODE, This is an algorithms question if youlook at the directions. Please answer all questions

: Please Answer Only Questions 3 And 4 Below I Will Provide The Answers For Questions 1 And 2 What Is Being Asked Is To 1 (305.9 KiB) Viewed 34 times

: Please Answer Only Questions 3 And 4 Below I Will Provide The Answers For Questions 1 And 2 What Is Being Asked Is To 2 (101.05 KiB) Viewed 34 times

: Please Answer Only Questions 3 And 4 Below I Will Provide The Answers For Questions 1 And 2 What Is Being Asked Is To 3 (226.88 KiB) Viewed 34 times

answer for #2

: Please Answer Only Questions 3 And 4 Below I Will Provide The Answers For Questions 1 And 2 What Is Being Asked Is To 4 (151.51 KiB) Viewed 34 times

Problem Statement 1. Sort (in ascending order) the items in a file of size 2ª KIB using limited memory. Note that x is a unsigned integer where x > 0. (a) Rules: i. The file is located in disk (not in memory) ii. Memory is limited to 2 input buffers and 1 output buffer (4KIB each) Total memory capacity 12 KIB iii. Assume that the contents of the file are unsigned integers separated by a comma delimiter. (i.e 3,1,3,100,99...) iv. The unsigned integers are not sorted v. The file can contain duplicated integers vi. When in a file, a digit from an integer is 1 byte (datatype is char). When in a buffer, an integer is 4 bytes (data type is integer). vii. All the buffers in memory support ±4 bytes of additional memory allocation. viii. You must use a Divide and Conquer algorithm to solve this problem ix. Temporary files, in disk, can only hold a max size of 4(2º)KIB where p is number of pass being processed x. The design of the algorithm to solve the problem must be recursive and using a divide and conquer approach (b) Input and Output i. Input: a file containing unsorted unsigned integers in the range of 0 and 100 (both inclusive). For example: 100,67,99,99,1,1,3,24,88,96,37,10,10,88,100,99,99 ii. Output: A file containing the sorted integers from the input file. For example: 1,1,3,10,10,24,37,67,88,88,96,99,99,99,99,100,100
Your work starts here 1. Design your algorithm for a given file of size 25 KIB first, and then do the same for a given file of size 2 KIB (for any given x). Note that x is a unsigned integer where x > 0. The best way to design your algorithm for this problem is to create diagrams to describe at the high level its process. Credit for this problem will be only given to those students that clearly define a step by step approach to solve this problem.
2. Write the recursive pseudocode that represents your algorithm in from problem (1) when the size of the input file is 2ª KIB. It must be clear and readable pseudocode to get credit.
3. Create a complete analysis of your pseudocode-algorithm. First compute its complexity and time complexity using the Back Substitution method, and then check your time complexity results using the master theorem. Show ALL your work to get credit
4. Optimize your pseudocode so now your algorithm should be able to deal with files of any size (not only 2). For instance in problem (1), we were assuming that the file size is in the form of 2 such as 2KIB, 4KIB, 16KIB..... However, your new optimization should include files of any size such as 3KIB, 37KIB... In addition, do you think that the time complexity of this algorithm has been optimized as a result of the modifications applied? Why? Show all your work to get credit
1) In the merge step, we actually merge two arrays, which are already sorted using recursion. Lets say the two arrays have size n and m respectively, the arrays are sorted ( in the recursion) and now we need to merge both the arrays to get a new sorted array of size n+m So we start from the first element of both the arrays and compare them, choose the smaller one and make it the first element of our new array and increment to pointer of the array from which we had chosen the number. Then we again compare both the value and similarly select the minimum and increment the pointer. e. g, Let say we have two arrays of (2, 4, 6) and (1, 3, 7) Now we will take another array of size 6( i.e. n+m). Let our array currently be () (no element for now) We will start with the first element of both the arrays. The elements are 2 and 1, we will choose 1 and add it to the new array so, new array is (1) Now, increase the pointer of the second array, now the elements are 2 and 3. so we'll choose 2 so, new array becomes (1, 2) Increment the pointer of the first array, i.e, now it will point to 4. Now the elements are 4 and 3, so we'll choose 3. new array becomes (1, 2, 3) Increment the pointer of second array., elements are 4 and 7. so, we will choose 4. new array {1, 2, 3, 4). Increment the pointer of first array, now elements are 6 and 7. we will choose 6 new array {1, 2, 3, 4, 6) Now, there is no element left from first arrays, so add all the remaining elements of second array. So, finally the new array becomes (1, 2, 3, 4, 6, 7) which is a sorted array after combining the two arrays we had earlier.
2) public void Merge(int[] values, int 11, int r1, int 12, int r2) { int n=r1-11+1;//size of left half int m=r2-12+1;//size of right half int[] a=new int[n];//temporary array int[] b=new int[m];//temporary array for(int i=0;i<n;i++)a=values[l1+i];//temporarily for(int i=0;i<m;i++)b=values[l2+i];//similarly [12, r2] part to b int index=11; int i=0; int i=0; while(i<n&&j<m) { if(a<b[j])values[index++]=a[i++]; else values[index++]=b[j++]; } while(i<n)values[index++]=a[i++]; while(j<m)values[index++]=b[j++]; storing the [11, r1] part of values to a