MAT 420 – Fall 2016 – B. Welfert
⃝c 2016 Arizona State University – School of Mathematics & Statistics
MAT 420 Midterm DIRECTIONS
• This exam includes 5 problems worth 20 points each
• For each problem include in your exam a printout of any code you wrote yourself, example
runs, and/or appropriate figures when needed.
• Clearly label each problem/question in your exam. Make sure your name appears clearly on the first page.
• Turn in your work on Blackboard by 11:59pm on Tuesday, October 25. Your submission should include:
1. a PDF file midterm LASTNAME.pdf containing all material (codes, output, explanations) 2. a tarball with your files (codes), identified by problem numbers
• For (10) extra points you can turn in a LATEXversion of your exam/answers.
1. Given a function f and a value x the purpose of this exercise is to evaluate the accuracy of
the quantity
Q(h)≡ −f(x−2h)+16f(x−h)−30f(x)+16f(x+h)−f(x+2h)
12h2 as an approximation of a derivative of f at x.
a) (5 pts) Which derivative of f at x does Q(h) approximates as h → 0?
b) (10 pts) Write a Perl code to determine the optimal value of h numerically on a computer
with machine epsilon ε.
c) (10 pts) Justify the results by considering roundoff and truncation errors.
2. Write a Perl program code.pl which determines the prime numbers less than a given integer N ≥ 1 as a list of values. For example ./code.pl 10 should return 2 3 5 7. Use the sieve of Eratosthenes to determine the prime numbers. Your program should work at least up to N = 10000. Grade will depend on whether your program yields the correct answer (80%) and on its efficiency (20%). Exception handling (e.g., a negative integer input) will also be considered.
3. The Linux command ls -lt lists information about files in a given directory. Write an awk program which creates a file filesize.dat containing the file name and its size on each line for regular files only (not directories), as well as the total size of these files on the last line. Include a test case in your exam.
MAT 420 – Fall 2016 – B. Welfert
⃝c 2016 Arizona State University – School of Mathematics & Statistics
4. Consider the following sequence of operations:
a = 4/3; b = a-1; c = b+b+b; eps = 1-c;
a) Verify that eps= 0 in exact arithmetic.
b) Verify that eps is the machine epsilon ε on a computer (you can verify by hand in single
precision IEEE format or by using an awk command/script)
c) What is the advantage of this method of computing ε over the one described in the awk program in example below?
1 #!/usr/bin/awk -f
2 BEGIN {
3 eps = 1
4 while (1+eps>1) eps/=2
5 printf(“%22.16e\n”,2*eps) 6 exit
Run script with (do not forget chmod +x) $./macheps.awk
2.2204460492503131e-16
When trying to store a number 1 < x < 1 + ε the computer uses the closest CN (1 or 1 + ε) instead (rounding)
There is no computer number between 2 and 2 + 2ε = 2(1 + ε) (the factor 2 only amounts to a shift by 1 in the exponent field). More generally, the gap between two consecutive CNs around x scales with x as ε|x|. We write
fl(x)=x(1+α) forsome|α|=|fl(x)−x|≤ε.
|x| 2
The quantity f (x+h)−f (x−h) is called a centered derivative approximation. Determine 2h
d)
the best choice of h = 1, ε1/3,ε2/3,ε when applied to the function f(x) = x4 at x = 1 (awk
script)
5. We consider the “Towers of Hanoi” problem with n = 7 disks of different sizes and 3 pegs (or towers, labeled A, B, C) is described on the Wikipedia page
Write a recursive Matlab program to determine the sequence of moves to bring all disks to peg C starting with all disks at peg A, given the fact that
(a) only one disk can be moved at a time and
(b) a larger disk cannot be on top of a smaller disk.
After each move record the position for each disk by the peg it is located at. The starting position is AAAAAAA (from smallest = top on the left to largest = bottom on the right), and the last position is CCCCCCC. Determine the sequence of moves (i.e. a sequence of 7-letter strings).
2