CS101 - Homework 5

Due: 2018-03-21 11:59p

Objectives

Gain more practice with recursion
Gain practice with iteration (for loops and while loops)
Gain practice with lists

[10 points] Prelab

Before coming to lab on Thursday / Friday, read this entire homework write-up and complete the prelab.

[10 points] Stairs

Using turtle graphics, write a recursive function drawStairs(len, levels) to draw pictures such as the one to the right. Assume the turtle starts in the top left corner, facing right. The first square should have a side length of "len", and each subsequent square should have 1/2 the size. There should be a total of "levels" squares. Do this all in one continuous drawing motion; Do not pick up the pen, and do not repeat any lines. Employ the following strategy: (1) draw a half-square, (2) recursively draw the rest of the squares, (3) draw the last half-square to return to the starting position and orientation. For testing, feel free to use the following code.

def drawStairsScene():
    """ 
    Moves the turtle to the top left of the screen and draws a staircase.
    """
    # pick up the pen and move the turtle so it starts at the left edge of the canvas 
    turtle.penup()
    turtle.goto(-turtle.window_width()/2 + 20, turtle.window_height()/2 - 20)
    turtle.pendown()    

    # draw the tree by calling your function
    drawStairs(200,5)

    # finished
    turtle.done()

[5 points] Testing for primality

Write a function isPrime(n) that tests whether its input parameter n is prime or not. Input can be assumed to be a positive integer; output is True or False. Use a for loop. (Recall that the primes include 2, 3, 5, 7, 11, 13, 17, 19, 23, ...)

[5 points] Print primes

Write a function printPrimes(n) that prints the first n primes. For example, printPrimes(5) would print 2, 3, 5, 7, 11. Input can be assumed to be a positive integer. Use a while loop.

[5 points] GCD, take 2

Write a function GCD2(a,b) that uses a loop (for or while?) to determine the greatest common divisor of a and b.

[5 points] Encryption

In class we discussed a simple function shift_letter(c, num) that returns the character in variable c shifted by num, eg, shift_letter('b',3) would return 'e'. The characters used include the lowercase letters followed by a space, ie, 'abcdefghijklmnopqrstuvwxyz ', so shift_letter('y',4) would return 'b'.

Use this function to help you implement a simple Caesar encryption method. Write a function caesar_encrypt(msg, shift) that "encrypts" the text in msg by shifting each character by shift characters.

To decrypt a message, we can use our caesar_encrypt function, but now, give it a negative number. Encrypt a message or two and make sure that you can decrypt them.

Decrypt the following message with number offset 5: htruzyjwexhnjshjenxestertwjefgtzyehtruzyjwxeymfsefxywtstrcenxefgtzyeyjqjxhtujx

You don't have to write it down, but it's a good check to make sure you've got things working.

Keep in mind our encryption schemes will only work for lowercase letters a-z and space. (You don't need to do any error checking of the input, just assume it is composed of spaces and lowercase letters.)

[5 points] First primes

Write a function firstPrimes(n) that returns a list containing the first n primes. For example, firstPrimes(5) would return the list [2, 3, 5, 7, 11]. Input can be assumed to be a positive integer. Use a while loop.

[5 points] Factors

Write a function factors(n) that returns a list containing all factors of input parameter n. For example, factors(5) would return the list [1, 5]. factors(32) would return the list [1, 2, 4, 8, 16, 32]. Input can be assumed to be a positive integer. Use a for loop.

Optional - Challenge problem 1 [2 extra points]

Make a copy of your code from the drawStairs() problem and modify it to draw pictures like the one on the right. Unlike in the previous problem, here it is ok to retrace steps or draw the same line twice. Only very slight changes to your code from the previous problem should be required. However, your recursive function should now only have one parameter 'len', the sidelength of the overall figure. The line spacing within the figure should be 10 pixels. We used side length of 200 to generate this picture.

Optional - Challenge problem 2 [2 extra points]

Use Turtle graphics to draw the recursive leaf shown here and to the right. To help with choosing values for constants, this picture was generated with the following settings:

initial stem length is 50
the base case stops drawing if the stem length <= 0.2
the next leaf to the front is .9*stemLength, to the right by 3 degrees
the leaf on the left is .28*stemLength, to the left by 60 degrees
the leaf on the right is .33*stemLength, to the right by 55 degrees, drawn one-third of the way up the stem

More challenge [1 extra point]: Notice that the leaves on the above image curl both up and down. Find an elegant way to revise your code so that all the leaves curl up as in the recursive leaf shown here and below.

Optional - Challenge problem 3 [2 extra points]

Write a function sumNested(L) that takes in a nested list of integers and returns the sum of all the lists. A nested list of integers contains 0 or more integers AND 0 or more nested lists of integers. For example,


sumNested([]) = 0
sumNested([1, 2, 3, 4, 5]) = 15
sumNested([1, [2, [3]], 4, 5]) = 15
sumNested([1, [2, [3], []], [], 4, 5]) = 15
sumNested([[2, 4, 6, 8], [3, 6, 9], [1, [1, 10]]]) = 50

Hint: The isinstance() function may be of use -- run help(isinstance) in your shell.

Turning in your work

Before submitting, see the grading rubric and make sure you have followed all instructions correctly.

Please put all of your functions into a single Python file called username_hw5.py, where username is your Middlebury username.

Be sure to comment your code. The top of the file should include a multiline comment that lists your name, the name of the assignment, and the date, at a minimum. Each function should also include a multiline comment (enclosed in triple-quotes) at the beginning of the body of the function describing what the function does.

Take a screenshot of your output for the stairs problem (and for any of the challenges that you complete as well). (On a Mac use Cmd-Shift-4 to select a region on the screen; on Windows use the Snipping Tool application. The resulting screenshot will be saved to the desktop.)

Please submit your file username_hw5.py as well as your screenshot(s) using the CS 101 submit script. You will need to use the script once for every file that you submit. Please enter the same amount of time each time you fill out the form.