follow the pdf and use the hw8 template and check with auto grader hw8_ag.p for 100%.
E7 – Prof. Alam Fall 2019, UC Berkeley Homework Assignment 8 Recursion The purpose of this lab is to give you more practice in the application of probability and introduce you to recursion with more focus on the recursion part. Since we are dealing with recursion, be very careful with infinity loop. Note: Use the template provided (HW8 Template.m) in the assignment download to com- plete this assignment. The template has a very specific format to enable auto-grading, and if the format is altered your assignment may not be properly graded (this will be apparent to you). Please also notice that variables in BOLD FONT will be checked to calculate your grade. In addition, the template file already reflects much of the content of the assignment. The due time is 11:59am Nov 8th, 2019. NO LATE HOMEWORK WILL BE ACCEPTED. Please upload the following files through the bCourses website: • HW8 Solution.m • HW8.pdf • Every functions you produced during homework • All generated plot files Directions to upload files can be found here. 1. Monte Carlo Simulation The purpose of this problem is to write a simple Monte Carlo simulation to estimate the constant π. Further information about Monte Carlo Simulation can be found here. This is done by first constructing a square with sides of length L. The square is covered with a circle of diameter L. Particles are randomly dropped on the entire square generated by a uniform distribution, which means all locations are equally probable. The number of particles within the circle are counted. As the total number of particles increases, the proportion of particles in the circle to the total number of particles approaches π 4 , which can be seen from Figure 1. (a) Write a function piMC with the function declaration line: 1 function [pi est] = piMC(n) 1 https://guides.instructure.com/m/4212/l/54353-how-do-i-upload-a-file-to-my-assignment-submission https://www.palisade.com/risk/monte_carlo_simulation.asp E7 – Prof. Alam Fall 2019, UC Berkeley Figure 1: the Monte Carlo simulation which estimates π by simulating the dropping of n particles onto a circle/square combo described above. In the first line of your function, add this command ‘rng(1)’. This command ensures that the random generator always produces the same sequence of random numbers and this is usually used to debug codes. Hint: For this problem, we can assume L is equal to 1. (b) Let the error e(n) = |πest − π|, where πest is calculated by the function piMC. Create an Error array which contains e(n) for n = 100, 1000, 10000, and 100000 and plot log(e(n)) as a function of log(n). The x and y axis labels should be ‘The natural logarithm of number of Particles’ and ‘Approximation’. The title should be ‘Monte Carlo Simulation’. Save the plot as .png file named ‘piMC.png’(generate .png file by the code). 2. The Golden Ratio Type the following at the command prompt. 1 axis([-20 20 -20 20]); 2 rectangle('Position',[5 5 13 8]); 3 rectangle('Position',[-5 -5 7 8]); 4 rectangle('Position',[-15 -15 9 6]); 2 E7 – Prof. Alam Fall 2019, UC Berkeley Which rectangle is more pleasing to your eyes? (You don’t need to include this answer in your report.) It is thought that rectangles where the ratio of the sides is close to the Golden Ratio are considered well-proportioned and “more pleasing”. Many buildings and artworks have the Golden Ratio in them, such as the Parthenon in Greece, Figure 2. The Golden Ratio Figure 2: the Parthenon in Greece is defined as the limit of the sequence of the (m+1)th Fibonacci number divided by the mth Fibonacci number as m approaches infinity. Recall: The mth Fibonacci number is defined recursively with, F (1) = 1, F (2) = 1, and F (m) = F (m− 1) + F (m− 2) for m > 2. For example F (3) = 2, F (4) = 3 and F (5) = 5. Define the mth Golden Ratio to be myGoldenRatio(m) = F (m) F (m+1) ,m > 2, where F (m) is the mth Fibonacci number. You are not allowed to use any for, while loop in this problem. (a) Write a recursive Matlab function myFibonacci that takes m as input and re- turns the mth Fibonacci number F . 1 function F = myFibonacci(m) (b) Program a Matlab function myGoldenRatio that takes m as input and returns the mth Golden Ratio R using your function in part (a). 1 function R = myGoldenRatio(m) (c) Use your function to find the 5th, 10th, and 15th Golden Ratio and store them in a 1-by-3 array G. Hint: Using command “format long” to see numbers up to 15 decimal places. 3 E7 – Prof. Alam Fall 2019, UC Berkeley 3. Express a number as sum of powers In this problem, we gonna study how to use recursion to count ways to express a number as sum of powers. Given two integers x and n, we want to get the number of ways to express x with n-th power of unique positive integers. You are not allowed to use any for, while loop in this problem. For example, Input : x = 100, n = 2 Output : 3 Explanation: There are three ways to express 100 as sum of positive integers raised to power 2. 100 = 102 = 82 + 62 = 12 + 32 + 42 + 52 + 72 Input : x = 100, n = 3 Output : 1 Explanation : The only combination is, 100 = 13 + 23 + 33 + 43 We can solve this problem by two steps. (a) First we can build a function Countsumi which takes x(the number to be ex- pressed), mypower(power) and a positive integer i, we use function Countsumi to count the number of ways to express x by mypower-th power of the unique positive integers which are greater or equal to i. The function Countsumi will be recursive. 1 function Num = Countsumi(x, mypower, i) (b) Based on the function Countsumi, then we can start to build Countsum, it will output number of ways Num to express x as sum of mypower-th powers of unique positive integers. The only difference between Countsumi and Countsum is the range of unique positive integers being used to express the target number x. 1 function Num = Countsum(x, mypower) 4. Pascal’s triangle Pascal’s triangle is a triangular array containing certain integers, which is named after the French mathematician Blaise Pascal (1623-1662). It is known as Pascal’s triangle in much of the Western world, although other mathematicians studied it centuries before him in India, Persia, China, Germany, and Italy. The triangle starts with a 1 on the top row. From there, each entry in a row is equal 4 E7 – Prof. Alam Fall 2019, UC Berkeley to the sum of the 2 numbers directly above it. If one of those two numbers does not exist, then a 0 is used, hence the left and right edges of the triangle are composed only of ones. Figure 3 graphically shows how each element in the triangle is created. MATLAB does not work with triangular-shaped matrices, so you will be creating a so-called left-justified Pascal’s triangle, as shown in Figure 4. You will write a recursive function that determines the value of an element given row and column numbers in the left-justified Pascal’s triangle. You are not allowed to use any for, while loop in this problem. This function should have the following declaration line: 1 function value = pascalsTriangle(row,col) Figure 3: Summing diagonal elements to create each successive element. Figure 4: Left justified Pascal’s triangle. Test your function by following ways. 5 E7 – Prof. Alam Fall 2019, UC Berkeley 1 >>>pascalsTriangle(5,1) 2 ans = 3 1 4 >>>pascalsTriangle(6,4) 5 ans = 6 10 7 >>>pascalsTriangle(8,5) 8 ans = 9 35 BTW, based on the structure left-justified Pascal’s triangle, the input row should be greater or equal to the input col. 5. The Towers of Hanoi is a famous mathematical game in which there are three pegs with several discs of varying diameter on one of the pegs. The discs are stacked such that no disc is on top another disc of greater diameter (see Figure 5). The objective is to move all of the discs to another peg while abiding by three rules: (a) Only one disc may be moved at a time; (b) only the top disc of any stack may be moved; (c) larger discs cannot rest on smaller discs. Figure 5: The Tower of Hanoi The fastest solution involves recursively breaking down the problem into smaller prob- lems: a tower is moved by moving all the discs except the bottom, and then moving the bottom. This remains the strategy until a ‘tower’ is a single disc, when moving among pegs becomes trivial. Let’s write a Matlab function which will give you the instruction of moving the tower of Hanoi as followings. You are not allowed to use any for, while loop in this problem. 1 function instruction = hanoi(d,origin,inter,target) (a) d: the number of discs on the initial tower. 6 E7 – Prof. Alam Fall 2019, UC Berkeley (b) origin: the peg on which the discs are originally stacked. (c) inter: an intermediate peg used for transferring discs. (d) target: the final peg on which the discs should be stacked. The origin, inter, target all are 1-by-1 character arrays. Your function will give instructions to instruction, which will be a 2-D character arrays with each row corre- sponding to one move. For example, 1 >> instructions = hanoi(2,'1','2','3') 2 instructions = 3 'Move one disk from peg 1 to peg 2' 4 'Move one disk from peg 1 to peg 3' 5 'Move one disk from peg 2 to peg 3' 6 7 >> tellmehow = hanoi(3,'A','B','C') 8 tellmehow = 9 'Move one disk from peg A to peg C' 10 'Move one disk from peg A to peg B' 11 'Move one disk from peg C to peg B' 12 'Move one disk from peg A to peg C' 13 'Move one disk from peg B to peg A' 14 'Move one disk from peg B to peg C' 15 'Move one disk from peg A to peg C' Hint: You may want to initially assign an empty string to output inst. That is, inst = ‘’. Be sure to verify that your code solves the problem by inputting a 4-disc tall tower to be transferred from peg 1 to peg 2 and and checking! 6. Palindrome number A palindromic number (also known as a numeral palindrome or a numeric palindrome) is a number that remains the same when its digits are reversed. Like 16461, for example, it is ”symmetrical”. The term palindromic is derived from palindrome, which refers to a word (such as rotor or racecar) whose spelling is unchanged when its letters are reversed. The first 30 palindromic numbers (in decimal) are: