Description

• 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

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.4 (3.5

or 3.5 is   fine       too)

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.4 or   3.5        or   3.6(and    then      some    extra     digits)

If you do  not know    how      to   do  this,      read    the material      provided     with      Lab 1.   It    explains      it    step      by   step

Do all   the exercises  labeled as

Task in your  head i.e. on  a paper

Later     on if   you    wish, you     can    type   them into    a     computer    (or copy/paste     from  the     solutions     once  I     poste them)

 

Task 1:

• What do   the following     two programs     print?
• What do   functions     orange  and guave do           when    called    with      positive integer  as   input      argument?  (answer in    plain     language)
• 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:

• What does        the  following        program print?
• Write one sentence        that describes       abstractly       (in       plain       English)  what       the  function mulberry       does        when      called      with positive  integer   as       input

• 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:

• What does      the following     program      print?
• Write one sentence      that       describes     abstractly      (in  plain     English) what     the function      cantaloupe  does      when    called    with      positive integer  as   input

• 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.

• 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:

• What does      the following     program      print?
• Write one sentence      that       describes     abstractly      (in  plain     English) what     the function      almond does             given     a     list  of   numbers      lst as     input     argument?
• 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:

• What does      the following     program      print?
• 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.
• 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:

• What does      the following     program      print?
• 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)
• 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.

 

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   recursive way   (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.

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

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:

Recursion:  Programming Exercise  3

• A string    is    a     palindrome if     it    reads  the same     from      the left and from      the   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      Test       your  function.
• Notice: a     word     of   length   n is a       palindrom   if     1^st and   n^th letter      are the same,

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

Idea/Strategy

Checking  if   a   string is   a   palindrome  can    be divided   into    two  subproblems:

1. Check if the     1^st 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     2^nd subproblem is the  same as the     original   problem but  smaller   in  size.

Useful string methods:    lower(),  and  string slicing

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       You may       find Python’s  string    method .isalpha()     useful.
• Test your      function       with      the following     at  least:

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.

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)?