C200 Programming Assignment № 8
Computer Science
School of Informatics, Computing, and Engineering
March 30, 2019
Contents
Introduction 2
Problem 1: Newton Raphson Root Finding Algorithm 4
Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Newton-Raphson Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Derivative and Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Newton-Raphson Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Starting Code for Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Interactive Session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Output for Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Problem 2: Bisection Method for Root Finding 8
Bisection Algorithm from Numerical Analysis . . . . . . . . . . . . . . . . . . . . . . . 8
Starting Code for Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Problem 3: pygame 9
A Snapshot of Your Pygames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Starting Code for Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Problem 4: Root Find Secant 12
Secant Illustration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Secant Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Starting Code for Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Output for Problem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Assignment №9 Convergence, Recurrence, and Animation Page 1
Problem 5: Integration 14
Simpson’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Starting Code to Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
File Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Output to Problem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Problem 6: Seriously, Again? 17
Starting Code to Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Output to Problem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Assignment №9 Convergence, Recurrence, and Animation Page 2
Introduction
In this homework, you’ll work on convergence, approximation, and animation. For convergence,
you will implement three algorithms for root finding–tools that are necessary in many areas like
finance, biology, and geology. For approximation, you will implement Simpson’s Rule–a means
of computationally determining an integral. For animation, you will have fun with pygames and
a bouncing…square! Lastly, you’ll have practice with recursion and transforming it.
Add a new folder to your C200 folder named Assignment9. In this folder, you’ll have the
following Python files:
– fignewton.py
– mybisect.py
– game1.py
– secant.py
– easycalc.py
– rec.py
Make sure and commit your project and modules by 11pm, Wednesday April 3th 2019.
As always, all the work should be your own. You will complete this before Wednesday April,
3, 2019 11:00P. You will submit your work by committing your code to your GitHub repository.
You will not turn anything in on canvas. If your timestamp is 11:01P or greater, the homework
cannot be graded. So do not wait until 10:58P to commit your solution. As always, all the work
should be your own.
Assignment №9 Convergence, Recurrence, and Animation Page 3
Problem 1: Root Finding with Newton
We discussed in lecture the general problem of finding roots and how ubiquitous it is.
f(x) = 0 x ∈ [a, b] (1)
x is called a root. The Newton-Raphson is an algorithm to find roots that uses a function and
its derivative.
x0 = estimate (2)
xn+1 = xn 
To remind you, a derivative is a function that characterizes the way a function changes as inputs
change. Line 4 is the typical definition. Line 5 is the usual approximation of the derivative used
in many devices(5)
Figure 1: The root is x. Our approximation xn moves toward the root as long as we’re larger
than our threshold. Observe in the graphic that f(b) is positive and f(a) is negative insuring that
there exists a root x, f(x).
The following listing shows two versions of the Newton-Raphson for:
The first uses the explicit derivative (which isn’t very scalable) done by hand. The second
uses the approximation. With λ functions we can easily approximate the derivative and use the
algorithm without any changes.
Assignment №9 Convergence, Recurrence, and Animation Page 4
Listing 1: newton.py
1 f = lambda x: x**6 – x – 1
2 fp = lambda x: 6(x*5) – 1
3
4 def fpa(f):
5 h = .000001
6 return lambda x: (f(x+h)-f(x-h))/(2*h)
7
8 def newton(f,fp,x,tau):
9 def n(x,i):
10 while f(x) > tau:
11 print(“{0} {1:.5f} {2:.5f}”.format(i,x,f(x)))
12 x = x – f(x)/fp(x)
13 i += 1
14 return x
15 n(x,0)
16
17 newton(f,fp,1.5,.0001)
18 newton(f,fpa(f),1.5,.0001)
To complete this problem, you’ll need to become a little familiar with Python’s eval() function.
This function takes an expression as a string and returns the value of the expression. Here is a
short session for you to try:
Session Intractive

“lambda x: 2*x”
’lambda x: 2*x’
f = “lambda x: 2*x”
f(2)
Traceback (most recent call last):
File “<stdin>”, line 1, in <module>
TypeError:’str’object is not callable
eval(f)(2)
4
eval(“3 + 4”)
7
kitty = “3 + x”
hello = “lambda x: “
eval(hello+kitty)(3)
6

Here are three runs of the completed program:
Assignment №9 Convergence, Recurrence, and Animation Page 5
Session Output
Function: x**6-x-1
tau: .001
x0: 1.5
interations: 26
0 1.50000 8.89062
1 1.30049 2.53726
2 1.18148 0.53846
3 1.13946 0.04924
Press any key to continue . . .
Function: x**6-x-1
tau: .001
x0: 100
interations: 5
0 100.00000 999999999899.00000
1 83.33333 334897975410.20740
2 69.44444 112156653932.12268
3 57.87037 37561036350.73944
4 48.22531 12579115030.90415
number of iterations exceeded…
Press any key to continue . . .
Function: x**6-x-1
tau: .0001
x0: 100
interations: 29
0 100.00000 999999999899.00000
1 83.33333 334897975410.20740
2 69.44444 112156653932.12268

removed for readability

26 1.14271 0.08376
27 1.13488 0.00156
Press any key to continue . . .
Assignment №9 Convergence, Recurrence, and Animation Page 6
Deliverables Programming Problem 1
Get the code to run.
Run the interactive session using Python.
Change the code presented in the listing newton.py so that:

1. The user can input the function, the threshold tau, and the initial estimate x0.
2. There is a bound on the iterations. The bound on the iterations stops the
   algorithm when the loop has equaled or exceeded the bound should it not
   converge with the threshold tau.
3. The user can input a value for the bound on the iterations.
   Three runs of the program are shown in the output.
   Put your code into a new module named fignewton.py
   Assignment №9 Convergence, Recurrence, and Animation Page 7
   Problem 2: Bisection
   In this problem you’ll implement the bisection method. The general idea is to take an interval
   [a, b] where the root x? ∈ [a, b] exists and continually move halfway to either the left or right. I’m
   using the algorithm as it’s presented in Elementary Analysis 2nd ed., Atkinson. You should be
   excited you can interpret the pseudo-code! Here τ is our threshold and c is the approximation
   to x.
   B1 Define c = (a + b)/2
   B2 If b c ≤ τ , then accept c as the root and stop.
   B3 If sign[f(b)] · sign[f(c)] ≤ 0, then set a = c.
   Otherwise, set b = c. Return to step B1.
   You are free to implement this using for, while, or recursion, though my implementation is using
   a while loop. The sign() function should return -1 if the argument is non-positive (negative or
   zero) and return 1 if it’s positive.
   mybisect.py
4. f = lambda x: x**6 – x – 1
   2
5. def sign(x):

6. TO DO: Implement this function

   5
   6

7. def bisect(f,a,b,tau):

8. TO DO: Implement this function

9. Use the following print statement to display the data nicely

10. the c variable is from the algorithmic specification of the ←-

    bisection method seen above

11. print(“{0:.5f} {1:.5f} {2:.5f} {3:.5f} {4:.5f}”.format(a,b,c,b-c,f(c←-

    )))
    12
    13

12. bisect(f,1.0,2.0,.001)
    Programming Problem 2
    Complete the sign() and bisect() functions.
    Use the print supplied in the comments to display the output nicely.
    Extra credit if you implement the function using either a while- or a for-loop and then
    also using recursion.
    Put your code for this problem in a new module named mybisect.py
    Assignment №9 Convergence, Recurrence, and Animation Page 8
    Problem 3: pygames
    In this problem, you’ll be introduced to pygames–a nice module that has features to make games.
    The code we’re giving has a bouncing square. When the rectangle touches a side, it bounces
    back–we added a little noise to the bounce.
    Figure 2: A snapshot of the bounce game.
13. import pygame
14. import sys
15. import random as rn
    4
16. pygame.init()
    6
17. BLACK = (0,0,0)
18. WHITE = (255,255,255)
19. BLUE = (0,0,255)
20. RED = (255,0,0)
21. YELLOW = (255,255,0)
    12
22. class Rectangle:
    14
23. def __init__(self,color,loc):
24. self.loc = loc
25. self.color = color
    18
26. def my_draw(self,screen):
27. pygame.draw.rect(screen, self.color, self.loc)
    Assignment №9 Convergence, Recurrence, and Animation Page 9
    21
28. def my_move(self,xoffset,yoffset):
29. self.loc = [self.loc[0]+xoffset,self.loc[1]+yoffset] + self.loc←-
    [2:]
    24
    25
30. size = [300, 300]
31. screen = pygame.display.set_mode(size)
32. pygame.display.set_caption(“C200 CHANGE”)
    29
    30
33. r = Rectangle(RED, [0, 0, 20, 20])
    32
34. while True:
    34
35. pygame.time.wait(40)
    36
36. for event in pygame.event.get():
37. if event.type == pygame.QUIT:
38. pygame.quit()
39. sys.exit()
    41
40. screen.fill(WHITE)
    43
41. r.my_draw(screen)
    45
42. if r.loc[0] > 280:
43. xd = -rn.randint(1,3)
44. if r.loc[1] > 280:
45. yd = -rn.randint(1,3)
46. if r.loc[0] < 10:
47. xd = rn.randint(1,3)
48. if r.loc[1] < 10:
49. yd = rn.randint(1,3)
50. r.my_move(xd,yd)
    55
51. pygame.display.flip()
    Assignment №9 Convergence, Recurrence, and Animation Page 10
    Change
    You’ll need to install the pygames module.
    Run the code. We provide the code in game1.py.
    Modify the code that so that when the square hits the
    – top, its color is changed to yellow
    – bottom, its color is changed to blue
    – left side, its color is changed to red
    – right side, its color is changed to dark green. You do not need to change any
    code in the class (we will learn more about classes and objects soon) – use
    the code that changes the direction as a hint on how to change the color.
    You should decide what suffices for dark green.
    Put your code in a module named game1.py
    Assignment №9 Convergence, Recurrence, and Animation Page 11
    Problem 4: Secant Method
    The secant method uses two numbers to approximate the root, the two numbers being endpoints
    of a line whose intercept approximates x?. The graphic shows one of the circumstances (there
    are two, but it’s not necessary for the implementation here).
    Figure 3: The root is x. We use two points, x0, x1 to determine x2 which is the approximation
    Although the recurrence looks a little intimidating, the code is actually minimal!
    secant.py
52. def secant(f,x0,x1,tau):

53. TO DO: Implement function

54. Use the following print statement to display the data nicely

55. print(“{0:.5f} {1:.5f} {2:.5f} {3:.5f}”.format(x0,f(x0),f(x1),x0-x1)←-

    )
    5
    6

56. secant(f,2.0,1.0,.0001)
    Assignment №9 Convergence, Recurrence, and Animation Page 12
    Output
    2.00000 61.00000 -1.00000 1.00000
    1.00000 -1.00000 -0.91537 -0.01613
    1.01613 -0.91537 0.65747 -0.17445
    1.19058 0.65747 -0.16849 0.07292
    1.11766 -0.16849 -0.02244 -0.01488
    1.13253 -0.02244 0.00095 -0.00229
    Deliverables Programming Problem 4
    Complete the secant() function.
    Use the print supplied in the comments to display the output nicely.
    Extra credit if you implement the function using a while- or for-loop and then using
    recursion.
    Put your code for this problem in a new module named secant.py
    Assignment №9 Convergence, Recurrence, and Animation Page 13
    Problem 5: Simpson’s Rule
    In this problem, we will implement Simpson’s Rule–a loop that approximates integration over an
    interval. Suppose we want to find the value of the integral below:
    Z b
    a
    f(x) dx (9)
    We could use those pesky rules of integration–who’s got time for all that, right Or, as computer
    scientists, we could implement virtually all integration problems. Simpson’s Rule is way of
    approximating an integration using parabolas (See Fig. 4). For the integration, we have to pick
    an even number of subintervals n and sum them up.
    Figure 4: The function f(x) integrated over a, b is approximated by ?f(x) using n equally sized
    invervals. The yellow illustrates the error of the approximation.
    The rule is found on lines (14)-(15). Observe that when the index is odd that there is a
    coefficient of 4; when the index is even (excluding start and end), the coefficient is 2.
    (10)
    xi = a + ix, i = 0, 1, 2, . . . , n 1, n (11)
    x0 = a + 0x = a (12)
    xn = a + n
    [f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + 2f(x4) + . . . (14)
57. 2f(xn2 + 4f(xn1) + f(xn)] (15)
58. import math
    2

59. INPUT function fn, start is a, end is b,

60. n is an even number of intervals

    Assignment №9 Convergence, Recurrence, and Animation Page 14

61. RETURN approximate area under the curve

62. def simpson(fn,a,b,n):
63. delta_x = (b – a)/n
64. interval = lambda i: a + i*delta_x

65. TO DO: Implement the function

    10

66. convert string to either number or expression

67. def convert(x):
68. if x.isnumeric():
69. return float(x)
70. else:
71. return eval(x)
    17
72. with open(“funny.txt”, “r”) as xfile:
73. xlines = [d.split(“,”) for d in xfile.read().split(“\n”)]
    20
74. for i in xlines:
75. body = i[0]
76. fn = eval(“lambda x : ” + body)
77. a = convert(i[1])
78. b = convert(i[2])
79. n = convert(i[3])
80. answer = convert(i[4])
81. integration = simpson(fn,a,b,n)
82. error = abs((answer – integration)/answer)
83. print(“f(x) = {0} over [{1},{2}] is {3:.3f}”.format(body,a,b,←-
    integration))
84. print(“Actual answer is {0:.3f}”.format(answer))
85. print(“Error is {0:.3f}”.format(error))
    The csv is a file that contains the function, the start of the integration, the end of the integration,
    the number of intervals and the actual integration. The file (See Table 1.) has the
    following:
    3x
86. • 1, 0, 6, 2, 222
      x
      2
      , 0, 5, 6, 125/3
      sin(x), 0, π, 4, 2
      1/x, 1, 11, 6, ln(11)
      Table 1: The csv file.
      For example, the third row is the approximation to the integral
      Z π
      0
      sin(x) dx = 2
      using n = 4 intervals.
      Assignment №9 Convergence, Recurrence, and Animation Page 15
      f(x) = 3(x*2) + 1 over [0,6] is 222.000
      Actual answer is 222.000
      Error is 0.000
      f(x) = x**2 over [0,5] is 41.667
      Actual answer is 41.667
      Error is 0.000
      f(x) = math.sin(x) over [0,3.141592653589793] is 2.005
      Actual answer is 2.000
      Error is 0.002
      f(x) = 1/x over [1,11.0] is 2.449
      Actual answer is 2.398
      Error is 0.021
      Programming Problem 5
      Put the file integralfile.txt in your project to make it easy to read in.
      Complete the code.
      Put your finished code in a new module easycalc.py
      Assignment №9 Convergence, Recurrence, and Animation Page 16
      Problem 6: Making Recurrence Behave
      In this problem, we will be given two RE and you’ll implement it recursively, with tail-recursion,
      with memoization, and linearization. In this version, I think I’ve found a weakness in the dictionary
      – see if you find it too. Here are the equations:
      b(1) ∨ b(2) = 0 (16)
      b(n) ∧ even(n) = n 1 + b(n 1) (17)
      b(n) ∧ odd(n) = n
87. • 1 + b(n 1) (18)
      gg(0) = 1 (20)
      gg(n) = 1 + 2gg(n1) (21)

88. TIMER FUNCTION — deprecated in 3.8 FYI

89. so you might get messages — you can ignore them for now

90. import time
91. def ftimer(f,args):
92. time_start = time.clock()
93. f(args)
94. time_elapsed2 = (time.clock()-time_start)
95. return time_elapsed2
96. def even(x):

97. TO DO: IMPLEMENT

98. def odd(x):

99. TO DO:IMPLEMENT

100. Recursive

101. INPUT n

102. OUTPUT RE value

103. def b(n):

104. TO DO: IMPLEMENT

105. TAIL RECURSIVE FOR 3

106. def btr(n,s):

107. TO DO: IMPLEMENT

108. MEMOIZATION

     Assignment №9 Convergence, Recurrence, and Animation Page 17

109. USE THIS DICTIONARY

110. d = {2:0,1:0}
111. def bm(n):

112. TO DO: IMPLEMENT

113. LINEARIZATION

114. def bL(n):

115. TO DO: IMPLEMENT

116. for i in range(1,10):
117. print(“f({0}) = {1}, {2}, {3}, {4}”.format(i, b(i),btr(i,0),bm(i),bL(i←-) ))
118. fblist = [b, lambda i: btr(i,0), bm ,bL]
119. tlist = [round(ftimer(f,700)10*5,2) for f in fblist]
120. print(tlist)
121. print()

122. RECURSIVE IMPLMENTATION

123. INPUT N

124. OUTPUT RE VALUE

125. def gg(n):

126. TO DO: IMPLEMENT

127. TAIL RECURSIVE

128. def gtr(n,s):

129. TO DO:IMPLEMENT

130. MEMOIZATION DICTIONARY INSIDE

131. def gm(n):

132. TO DO: IMPLEMENT

133. LINEARIZATION

134. def gL(n):

135. TO DO:IMPLEMENT

136. fglist = [gg, lambda i: gtr(i,0),gm, gL]?
137. for i in range(0,10):
138. print(“f({0}) = {1}, {2}, {3}, {4}”.format(i,gg(i),gtr(i,0),gm(i),gL(←-
     i)))
     Assignment №9 Convergence, Recurrence, and Animation Page 18
     78
139. tlist = [round(ftimer(f,700)10*5,2) for f in fglist]
140. print(tlist)
     f(1) = 0, 0, 0, 0
     f(2) = 0, 0, 0, 0
     f(3) = 10, 10, 10, 10
     f(4) = 13, 13, 13, 13
     f(5) = 39, 39, 39, 39
     f(6) = 44, 44, 44, 44
     f(7) = 94, 94, 94, 94
     f(8) = 101, 101, 101, 101
     f(9) = 183, 183, 183, 183
     [99.59, 45.61, 6973.75, 28.6]
     f(0) = 1, 1, 1, 1
     f(1) = 3, 3, 3, 3
     f(2) = 7, 7, 7, 7
     f(3) = 15, 15, 15, 15
     f(4) = 31, 31, 31, 31
     f(5) = 63, 63, 63, 63
     f(6) = 127, 127, 127, 127
     f(7) = 255, 255, 255, 255
     f(8) = 511, 511, 511, 511
     f(9) = 1023, 1023, 1023, 1023
     [35.0, 34.79, 41.02, 20.12]
     Deliverables Programming Problem 6
     Put the file rec.py in your project to make it easy to read in.
     Complete the code.
     The file to turn in is rec.py
     Assignment №9 Convergence, Recurrence, and Animation Page 19

WX：codehelp