Assignment 3

Due Thurs, Sep 20

Please create a single zip file named <userid>-hw3.zip (i.e. kay-hw3.zip) that contains three files:
hw3-1.py (the solution of question 1)
hw3-2.py (the solution of question 2)
hw3-3.py (the solution of question 3)

Email your solutions to kay <at> ischool. Include comments in each script stating your name, the name of any collaborators, and approximate time it took you to complete the exercise.

1. Write a script that prompts the user for their name. Print the name with the letters reversed. You may use s.lower() and s.upper() to change a string s to lowercase and uppercase letters.

Enter your name: Paul
Luap

Hint: use a loop that counts downward.

2. Write a script that prompts the user for an integer, N. Display an NxN checkerboard as shown:

Enter a size: 4
X X
 X X
X X
 X X

Enter a size: 5
X X X
 X X
X X X
 X X
X X X

3. As we discussed in the first lecture, logarithms were invented in the 17th century and used to simplify calculations, most prominently for ship navigation. Teams of human calculators would work for years to create vast logarithm tables, so it was essential to have a fast algorithm for their computation. The algorithm in class was given by Euler in 1748. It only requires multiplication and taking square roots, which could be done quickly by existing algorithms.

Your job is to implement Euler’s algorithm. This algorithm is an example of bisection search, but it can also be written in a simpler guess-and-check form:

We want to find x = Log₁₀N, where 1<N<100. This means that x is the number such that 10^x = N. We will begin with a guess and then update it, bringing the exponent 10^guess closer and closer to N.

a. Begin with a guess of 0, a step of 1, and factor of 10. This means that the exponent is currently 10^guess = 10⁰ = 1. This is less than N, so the first guess is too low.

b. We have chosen factor so that factor = 10^step. If we add the step to the guess, we can compute the new exponent by 10^{guess + step} = 10^guess * 10^step = 10^guess * factor. So the new exponent would simply be the old exponent times factor. If this is still less than N, replace guess by guess + step, and the exponent by the exponent times the factor.

c. Next, we divide the step by 2. This means that the new factor must be 10^{step / 2} = (10^step)^1/2, which is the square root of the old factor. Compute this using math.sqrt(factor) (or, if you are already comfortable with functions, you can use your own square root script from the algorithms lecture). Return to step b.

Continue this algorithm until step is less than the desired precision (you may use epsilon = 0.00001). You might notice that this algorithm is similar to the digit-by-digit square root algorithm from class. In fact, this is precisely a digit-by-digit algorithm in base 2! We are adding steps of 1, 1/2, 1/4.., which are written in binary as 1, 0.1, 0.01... This means that after we set a particular digit in binary, it never changes.

Optional Bonus: Once you have your script working for 1<N<100, revise it so that it can take any N. You may use the relationships, Log (10N) = Log N + 1, and Log (N / 10) = Log N – 1.