CSCI 201 - Computer Science 1 Homework 5: Computing the aquare root. Due on Friday February 17 Objectives. The objectives of this aseignment are: 1. Learn how to track the mamber of aperations evaluated when a program runs. 2. Learn to dedign an algarithm that uses a loop to oompute better approamations. 3. Latn to compare the efficiency of two different coeverging processes. IMPORTANT Watch the ridinos for Lacture I and lecture 2 in Wook 5 of DeL (astarialn content) before gow start on this theck's asnignments. The sample oude for this asnignment is available in Courseinfo/TriangleAKDSeqreqrttent. cpp in CourseFiles. In class we studied two approaches that can be ssed to estimate the square root of a number. The two apptoaches for the square root are the Divide-and-conguer and Newfon's method. In both cases, we have a pre-defined constant eps which is used to check the goodness of the guess. The loop exits when the absolute value of the difference between the input number and the square of the guess is less than epn. Recall that we implemented and tested the perfocmsnce of the divide-and-conquer approach in class (see Courseinfo/TriangleANDSqrt/sqrt Test,cpp). Question 1. Newton's method worion by starting with an initial guess we'll use ( rum +1)/2 as List the sequence of operations that will be performed when we use this approach, and identify the repetition and the exit condition. Question 2. Construct a flowchart for the Nicwton's method using Raptor. Question 3. Write a Ct+ progratn that implements your flowchart. The progratn must count the number of divisiots and multiplications that the loop performed. Compile and test in a seript session. Comparing the two methods. When comparing two different approaches, it is important that we have a common framework. In the realm of computing this is done by creating a "test-suite" on which both the approaches are applied. The test-suite defines the data set and all the parametery needed for the problem. In this case our data set is the nuabers for which we compute the square root; the additional parameter is the amount of accuracy necded, which is specified by the value of epa. Our process is as folloss For nach nalue of eps ran the program on all the tumbers in the data set and note the sum of the number of multiplications and dirisions in each case. This process bs carried out for both programs and the results are noted in 2 tables. Step. 1. Defining the feat suile. We will tuse the teen input vilues starting frocn 0.2, increasing by 10% each tima. The eps valus are 0.1,0.05,0.02,0.01,0.005,0.002,0.001,0.0005,0.0002. Step 2. Collecting reaults. Constract a table with one tow for each data value and one columin for each eps value. We will have two such tables, one for divide-and-conquer and one for Newton's method. The table will be filled by running the program and recording the number af multiplications and divisions of the loop. For instance, the entry in the Newton table corresponding to data value 0.2 and eps value 0.002 will be the number of multiplications and divisions performed by Newton's method to find the square root of 0.2 with eps set to 0.002. For each column, compute the average. Step 3. Comparing the results. Compare the data from the two tables from two viewpoints: The total number of opertions. Which method do you think is performing fewer operations? Explain. The scalability of the aigorithm. Scalability refers to how well the algorithm scales up, i.e., how does the amount of resources used (in this case, the number of operations) increase with increased requirement (in this case, greater accuracy)?. Scalability is usually represented by a graph, that plots the resources usod against the requirements. Can you think of a way of doing that? What to upload on CourseFiles. Create a folder named Hwork5 within your CourseFiles folder and upload the following: 1. Answer to Question 1. 2. Flowchart from Question 2. 3. Script file and . epp file from Question 3. 4. The table of results from Step 2 . 5. Answers to questions in Step 3
