## Description

Starting Lab 11

• Open a browser and log into Brightspace

• On the left hand side under Labs tab, find lab11 material

contained in lab11-students.zip file

• Download that file to the Desktop and unzip it.

2

Before starting, always make sure you

are running Python 3

This slide is applicable to all labs, exercises, assignments … etc

ALWAYS MAKE SURE FIRST that you are running Python 3.

That is, when you click on IDLE (or start python any other way)

look at the first line that the Python shell displays. It should say

Python 3.

If you do not know how to do this, read the material provided

with Lab 1. It explains it step by step

3

4

Later on if you wish, you can type them

into a computer (or copy/paste from the

solutions once I poste them)

Do all the exercises labeled as

Task in your head i.e. on a

paper

Task 1: (a) What do the following two programs print?

(b) What do functions orange and guave do when called with positive integer as

input argument? (answer in plain language)

(c) http://www.pythontutor.com/visualize.html#mode

Open file t1.py and copy both programs into Python Vizualizer. Make sure you

understand all the functions that are running (at the same time) as you step through

the execution of the program.

Task 2:

(a) What does the following program print?

(b) Write one sentence that describes abstractly (in plain English) what the function mulberry

does when called with positive integer as input argument.

(c) What would happen if we made mulberry(-3) call in the main, instead of mulberry (5)?

(d) http://www.pythontutor.com/visualize.html#mode

Open file t1.py and copy code below into Python Vizualizer. Make sure you understand how

the program is running and what it is doing as you step through its execution of the program.

(e) What is the maximum number of mulberry functions running at any one time, i.e. what is

the maximum number mulberry functions on the stack at any one time?

– What is the answer for general n?

– Make the call mulberry(1000) in Python shell instead mulberry(4) of and observe what

happened? Why did that happen?

Task 3:

(a) What does the following program print?

(b) Write one sentence that describes abstractly (in plain English) what the function

cantaloupe does when called with positive integer as input argument.

(c) http://www.pythontutor.com/visualize.html#mode

Open file t1.py and copy code below into Python Vizualizer. Make sure you

understand how the program is running and what it is doing as you step through the

execution of the program.

(d) What is the maximum number of cantaloupe functions running at any one time,

i.e. what is the maximum number cantaloupe functions on the stack at any one time?

What is the answer for general n?

Task 4:

(a) What does the following program print?

(b) Write one sentence that describes abstractly (in plain English) what the function

almond does given a list of numbers lst as input argument?

(c) http://www.pythontutor.com/visualize.html#mode

Open file t1.py and copy code below into Python Vizualizer. Make sure you

understand how the program is running and what it is doing as you step through the

execution of the program.

Task 5:

(a) What does the following program print?

(b) Write one sentence that describes abstractly (in plain English) what the function

fig does given a list of numbers lst as input argument and high=len(lst)-1.

(c) http://www.pythontutor.com/visualize.html#mode

Open file t1.py and copy code below into Python Vizualizer. Make sure you

understand how the program is running and what it is doing as you step through the

execution of the program.

Task 6:

(a) What does the following program print?

(b) Write one sentence that describes abstractly (in plain English) what the function

almond does (given strings s and ch as input and assuming ch contains only one

character)

(c) http://www.pythontutor.com/visualize.html#mode

Open file t1.py and copy code below into Python Vizualizer. Make sure you

understand how the program is running and what it is doing as you step through the

execution of the program.

11

Recursion: Paper Study

• Open file sum_prod.py

It contains contains 2 functions that both compute the

sum: 1+2+3 …+n. One computes it in the ‘usual’ way

using python’s loops (this is called, iterative solution),

and the other in a recursiveway (i.e. using function

calls that solve a problem on the smaller problem

instance)

Similarly sum_prod.py contains 2 function that both

compute the product 1*2*3…*n (thus they compute

n!, i.e. n factorial) in iterative and recursive way (as we

have seen in class)

Study with TAs and understand well all these 4 solutions.

12

Recursion: Programming Exercise 1

• Write a recursive function (do not use python’s

loops), called m, that computes the following series,

given positive integer i:

• In the “main” write a loop that tests your function m

by displaying values m(i) for i = 1, 2, . . . , 10, as

follows

m(1)= 0.3333333333333333

m(2)= 0.7333333333333334

m(3)= 1.161904761904762

m(4)= 1.6063492063492064

m(5)= 2.060894660894661

m(6)= 2.5224331224331227

m(7)= 2.9890997890997895

m(8)= 3.459688024393907

m(9)= 3.933372234920223

m(10)= 4.409562711110699

13

Recursion: Programming Exercise 2

• Write a recursive function, called count_digits,

that counts the number of digits in a given

positive integer n.

• Test your function:

>>> count_digits(0)

1

>>> count_digits(7)

1

>>> count_digits(73)

2

>>> count_digits(13079797)

8

>>>

14

Recursion: Programming Exercise 3

• A string is a palindrome if it reads the same from the left and from the

right. For example, word “kayak” is a palindrome, so is a name “Anna”, so is

a word “a”. Word “uncle” is not a palindrome.

• Write a recursive function, called is_palindrome, that returns True if the

input string is a palindrome and otherwise returns False. Test your

function.

• Notice: a word of length n is a palindrom if 1st and nth letter are the same,

AND 2nd and (n-1)st are the same, and so on … until we get to the “middle”

of the word.

>>> is_palindrome(‘blurb’)

False

>>> is_palindrome(‘a’)

True

>>> is_palindrome(‘anna’)

True

>>> is_palindrome(‘Anna’)

True

>>> is_palindrome(“A man, a plan, a canal —

Panama!”)

False

>>> is_palindrome(“Madam, I’m Adam”)

False

15

Checking if a string is a palindrome can be divided into

two subproblems:

1. Check if the 1st and the last character in the string are

the same

2. Ignore the two end characters and check if the rest of

the substring is a palindrome.

Notice that the 2nd subproblemis the same as the

original problem but smaller in size.

Useful string methods: lower(), and string slicing

Idea/Strategy

16

Recursion: Programming Exercise 4

• Refine your function is_palindrome, and call the modified version,

is_palindrome_v2, such that it ignores all characters but the characters

that correspond to the letters of English alphabet. You may find Python’s

string method .isalpha() useful.

• Test your function with the following at least:

>>> is_palindrome_v2(“A man, a plan, a canal — Panama!”)

True

>>> is_palindrome_v2(“Go hang a salami, I’m a lasagna

hog”)

True

>>> is_palindrome_v2(“Madam, I’m Adam”)

True

>>> is_palindrome_v2(“Madam, I’m”)

False

>>> is_palindrome_v2(‘blurb’)

False

>>> is_palindrome_v2(‘a’)

True

>>> is_palindrome_v2(‘Anna’)

True

17

Recursion: Programming Exercise 5: GCD

The greatest common divisor (GCD) of two integers (at least one of which is

not zero), is the largest positive integer that divides the numbers without a

remainder. For example, the GCD of 12 and 8 is 4.

The following technique is known as Euclid’s Algorithm because it appears in

Euclid’s Elements (Book 7, ca. 300 BC). It may be the oldest nontrivial algorithm.

The process is based on the observation that, if r is the remainder when a is

divided by b, then the common divisors of a and b are the same as the common

divisors of b and r. Thus we can use the equation

gcd(a,b) = gcd(b,r)

to successively reduce the problem of computing a GCD to the problem of

computing the GCD of smaller and smaller pairs of integers. For example,

gcd(36, 20) = gcd(20, 16) = gcd(16, 4) = gcd(4, 0) = 4

implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting

numbers, this repeated reduction eventually produces a pair where the second

number is 0. Then the GCD is the other number in the pair.

Write a recursive function called gcd that takes two integer parameters a and

b (you can assume a>=b) and that uses Euclid’s algorithm to compute and return

the greatest common divisor of the two numbers. Test your function.

18

Difficult question: GCD

What is the depth of the recursion (i.e. the maximum number of gcd

methods on the stack/memory) of your gcd function if you called it

with gcd(36, 20)? You can find this out by drawing the diagrams as

we did in class and or running your function and the gcd(36, 20) in

Python Visualizer.

Here is a difficult question and food for thought: What is the

maximum depth of the recursion of your gcd method for general a

and b (where a>=b)?