SAN FRANCISCO STATE UNIVERSITY Computer Science Department CSC510 – Analysis of Algorithms Algorithm Challenge 2: Divide and Conquer Instructor: Jose Ortiz Full Name: Student ID: Assignment Instructions. Must read! Note: Failure to follow the following instructions in detail will impact your grade negatively. 1. This algorithm challenge is worth 9%, and will be graded using a grading point scale where the maximum possible grade is 9 points 2. Handwriting work or screenshots of your work are not allowed. In addition, all the pseudocode done in this algorithm challenge must be done using LaTeX. Students who fail to meet this policy won’t get credit for their work. Note that for pseudocode, I only want to see the compiled PDF psudocode, instead of the code to create the pseudocode. 3. Each section of this algorithm challenge is worth 2.25 points 4. Take into account that in this type of assignments, I am more interested in all the different approaches you take to solve the problem rather than on the final solution. 1 CSC510 Analysis of Algorithms Problem Statement 1. Sort (in ascending order) the items in a file of size 2x 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 ((#pass + 1) ∗ 4)KIB (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 Page 2 of 6 CSC510 Analysis of Algorithms Your work starts here 1. Describe the algorithm to solve the problem for a given file of size 25 first, and then describe the algorithm for a given file of size 2x (any given x). Note that x is a unsigned integer where x > 0. You can use tables, diagrams, paragraph description..... to describe the algorithm. Be as clear as possible, and define clearly each step taken during the process. Credit for this problem will be only given to those students that clearly define a step by step approach to solve this problem. Page 3 of 6 CSC510 Analysis of Algorithms 2. Write the pseudocode that represents your algorithm from problem (1). Note that in this problem, I am asking for the compiled LaTeX pseudocode (PDF format) instead of the LaTeX code that creates this pseudocode Page 4 of 6 CSC510 Analysis of Algorithms 3. Compute the complexity function, the I/O cost of operations, and the Θ(g(n)) time complex- ity of your algorithm using your pseudocode from problem (2). For the complexity function and time complexity use the substitution method and then check your result with the Master Theorem. For the I/O cost define it as a function of N. Where N is the number of blocks (4KIB) in pass 0 of this algorithm Page 5 of 6 CSC510 Analysis of Algorithms 4. Modify your algorithm from problem (1) to support files of any size (not only 2x). For in- stance in problem (1), we were assuming that the file size is in the form of 2x such as 2KIB, 4KIB, 16KB..... However, your new modification 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? Page 6 of 6