CSC190: Computer Algorithms and Data Structures Assignment 1




5/5 - (3 votes)

Part 1: Evaluating a continuous function
This part requires you to expand the function f located in the a1Part1.c file.
• One argument x of type float is passed to this function.
• This function will return a value of type float.
• The polynomial you will implement is f(x) = sin(x) + x
10 + (x − 1)2
• Please refer to the file Part1.txt for a sample result from this function.
• You can test your implementation of this function using the provided main.c file. As you are aware
from going through the preparation slides, in order to execute this program, all associated functions
must be compilable. Hence, ensure that before you test this function that other skeleton functions are
at bare minimum compilable. Then, compile all files using the command supplied in Sec 2. When you
examine the main.c file, you can observe that you must supply to the executable file the argument
‘1’ to invoke the f function (i.e. execute the program with ./run 1 after compilation).
Part 2: Implementing Numerical Integration using Simpson’s Method
This part is a continuation of Part 1. Here you will implement the function S located in a1Part2.c which
numerically integrates the function f in the interval [a, b] (i.e. R b
f(x)). Numerical integration is used in
solvers such as MATLAB in order to evaluate the integral of a function within a specified interval. The
Simpson’s method approximates the integral of a function by evaluating the following expression:
Z b
f(x) ≈
b − a
(f(a) + 4f(m) + f(b)) (1)
where m is the mid-point of the interval [a, b]. The Simpson’s method approximates the function f using a
third order polynomial. The error in this approximation is proportional to the fourth derivative evaluated
at ε ∈ [a, b] (i.e. f
(ε)). Hence if f is a third order polynomial, there will be no error introduced by this
numerical integration.
• Two arguments are passed to the function and these are the bounds of integration (i.e. [a,b]).
• The function will evaluate and return the approximate value of R b
f(x) in accordance to Eq. 1.
• main.c file can be used to test your implementation via the command ./run 2. Ensure that your
output matches the sample output provided in Part2.txt. You can integrate the expression f by
hand. Compute the correct value and check how different the result from this function is from the
actual value.
Part 3: Adaptive Numerical Integration
As you may have noticed in the previous section, the error in applying the Simpson’s method over a large
interval is significant. Here you will implement an adaptive version of the Simpson’s method which splits the
original interval into smaller halves until the error within each divided interval is lesser than the threshold .
Then, the Simpson’s method is applied to each one of these intervals and the results are summed. You will
adaptively implement this as functions may have high variations in one area and not vary so much in other
regions. It is necessary to divide the intervals extensively in the highly varying regions and not so extensively
in slowly varying regions. The original interval will be continually divided into half until the current interval
|S(a, m) + S(m, b) − S(a, b)|/15 < where S(a, b) is the application of the Simpson’s method to the interval [a, b] and m is the midpoint of the interval [a, b]. At this point, S(a, b) estimates the integral over the sub-interval [a, b] with sufficient accuracy and there is no need to further divide [a, b]. Hence, once the error over [a, b] satisfies the above threshold, S(a, b) can be applied to obtain the estimate of the integral over [a, b] (i.e. no need to use S(a, m) and S(m, b)). This is repeated throughout the entire original interval. You will implement the function simpsonsAdaptiveIntegration located in a1Part3.c as follows: 2 • Four arguments are supplied to this function and these are the interval of integration [a, b], (for the stopping criteria) and the length of the smallest interval allowed (in order to prevent too many iterations). • This function will be implemented iteratively (loops NOT recursion). In the iterative implementation, you will utilize a loop and an array to aid with the iterative division of intervals and evaluation of the integral over these sub-intervals. Note: we will check whether you have used recursion (you will lose all points for this part and code content if this is the case). • Define a macro called ARRAYSIZE in the a1.h file which is the size of the array that you will declare in the function simpsonsAdaptiveIntegration that will hold information about the intervals that are yet to be evaluated. • This function will not return any values. It will print the result of applying the adaptive Simpson’s method. Please refer to the file Part3.txt for the expected formatting of your output. • main.c file can be used to test your implementation via the command ./run 3. Ensure that your output matches expected output in Part3.txt. You can integrate the expression f by hand. Compute the correct value and check how different this result is from the output of the adaptive method. 3 Code Submission 3.1 Checklist ENSURE that your work satisfies the following checklist: • You submit before the deadline. • All files and functions retain the same original names. • Your code compiles without error in the ECF environment (if it does not compile then your maximum grade will be 1/20). • Do not resubmit any files in Assignment 1 after the deadline (otherwise we will consider your work to be a late submission). 3.2 Submission through submitcsc190s • Log onto your ECF account. • Ensure that your completed code compiles. • Browse into the directory that contains your completed code ( a1.h, a1Part1.c, a1Part2.c, a1Part3.c). • Submit by issuing the command: submitcsc190s 1 a1.h a1Part1.c a1Part2.c a1Part3.c 3