Sample Exercises

I have been asked for some sample exercises, so here are some for your practice. Many of these actually came from old quizzes that I used to give...

String Transposition

One way of encoding a string is to use a transpositon method. The best way to visualize string transposition is to think of it as writing the string into a box. Suppose our string is “Hello World!” and our box has 3 columns:

H e l
l o
W o r
l d !

To get the encoded string, we’d “read” it off going down each column. So our string would be “HlWleoodl r!”.

In your program, you should ask the user for the string, and also the key, which will give you the number of columns in your box. You can assume that the number of characters in the string will always be a multiple of the key. Some examples that you can try

  • String: “Hello World!”, key = 3, encoded string = “HlWleoodl r!”
  • String: “HK PolyU”, key = 4, encoded string = “HoKl yPU”

The main() function is given below. Your job is to write encode() and decode().

def main():
    string = input("Please type in the string")
    key = eval(input("What is the key?"))
    userChoice = input("Would you like to encode (e) or decode (d)?")
    if (userChoice == "e"):
        encode(string, key)
    if (userChoice == "d"):
        decode(string, key)
main()

Approximating Square Roots

One especially efficient algorithm for approximating square roots is called Newton's method.

Supposing that we have a number, x, for which we wish to find the root. We start with our guess of the square root as:

guess = x/2

Then we improve upon the guess by calculating a new value for guess:

guess = (guess + guess/2)/2

(Obviously, the guess on the right hand side would be the old value, calculated in the previous iteration.)

We would keep on doing this until we reach a specified accuracy -- i.e. when the change in values between successive calculations of guess is less than an accepted error value.

In this question, you will write a program that will calculate the square root of a given number to within 0.0000001 accuracy. Your program should also report how many iterations (rounds) it took before it arrived at the given value.

A sample run of your program should look like the following:

$ python SquareRoot.py
This program approximates the square root of a number
Gimme a number: 4
The approximate square root of 4 is 2.0
It took 1 iterations to get this result
$ python SquareRoot.py
This program approximates the square root of a number
Gimme a number: 100
The approximate square root of 100 is 10.0
It took 7 iterations to get this result
$ python SquareRoot.py
This program approximates the square root of a number
Gimme a number: 2
The approximate square root of 2 is 1.41421356237
It took 5 iterations to get this result

Monte Carlo Calculation of Pi

Over the years, there have been many attempts to approximate the value of π, using different methods. Some of them rely on mathematical series, others use geometry.

One of the most straightforward geometrical ways to estimate π is via the Monte Carlo method. The idea behind this method is to draw a circle inside a square whose side equals the diameter of the circle (i.e. the circle will touch the square at four points). For example, supposing that the center of the circle is at (1,1), and the radius of the circle is 1 (meaning that the diameter is 2). Then we would get this diagram:

If we calculate the areas of the circle and the square, we would obviously get:

  • Area of Square = 2 × 2 = 4
  • AreaofCircle= π × 12 = π

In addition, if we randomly pick a point with:

  • x-coordinate between 0 and 2
  • y-coordinate between 0 and 2

That point will obviously fall within the square.

In addition, there is π probability that it will fall within the circle as well.

Therefore, suppose that we now draw a lot of points, at random. Every time we draw a point, we check whether it falls in the circle. After a great many points, we should be able to estimate the value of π as:

π = number of points in the circle 4 total number of points

Write a function, calculatePi(), that will calculate the value of π for us using this method. calculatePi() takes only one parameter -- the number of points to generate.

Your function will need the following helper functions:

  • insideCircle(x1, y1, x2, y2, r) -- given a circle with center at (x1, y1) and radius r, returns True if the point (x2, y2) is inside the circle, and False if not.
  • distance(x1, y1, x2, y2) -- given two points (x1, y1) and (x2, y2), uses the Pythagoras Theorem to calculate the distance between these two points (and returns it).

You should only need these two functions in addition to calculatePi(). Anything more and you're thinking too much.

Some sample runs:

calculatePi(100)
3.12
calculatePi(1000)
3.108
calculatePi(10000)
3.1288
calculatePi(100000)
3.14996

As you can see, the calculated value gets closer to the true value of π as we use more points for the simulation.