lab7¶

count_chars exercises the use of dictionaries. derivative uses the concept of finite differences to approximate a differential operator. The newton function implements a root finding algorithm (and makes use of the derivative function). The is_palindrome function exercises string processing. The is_palindrome function can be implemented using recursion (if you like to learn about this) but there exist other solutions as well.

Relevant Socratica videos:

`count_chars(s)`¶

Implement a function count_chars(s) which takes a string s and returns a dictionary. The dictionary’s keys are the set of characters that occur in string s. The value for each key is the number of times that this character occurs in the string s.

Examples:

In [ ]: count_chars('x')
Out[ ]: {'x': 1}

In [ ]: count_chars('xxx')
Out[ ]: {'x': 3}

In [ ]: count_chars('xxxyz')
Out[ ]: {'x': 3, 'y': 1, 'z': 1}

In [ ]: count_chars('Hello World')
Out[ ]: {'H': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'W': 1, 'r': 1, 'd': 1}

`derivative(f, x)`¶

This task has two parts.

Part 1

Write a function derivative(f, x) which computes a numerical approximation of the first derivative of the function f(x) using central differences. The value that the function returns is

\[\frac{f\left(x+\frac{\epsilon}{2}\right) - f\left(x-\frac{\epsilon}{2}\right)}{\epsilon}\]

with $\epsilon=10^{-6}$.

Example:

In [ ]: def f(x):
   ...:     return x * x

In [ ]: derivative(f, 0)
Out[ ]: 0.0

In [ ]: derivative(f, 1)
Out[ ]: 2.0000000000575113

In [ ]: derivative(f, 2)
Out[ ]: 4.000000000115023

Note that you may not get exactly the same numbers as shown above.

Part 2

Modify the derivative function such that it takes an optional third parameters eps to represent the greek letter epsilon ($\epsilon$) in the equation above. The parameter eps should default to 1e-6).

Examples:

In [ ]: import math

In [ ]: derivative(math.exp, 0, eps=0.1)
Out[ ]: 1.000416718753101

In [ ]: derivative(math.exp, 0)
Out[ ]: 1.0000000000287557

In [ ]: derivative(math.exp, 0, eps=1e-6)
Out[ ]: 1.0000000000287557

`is_palindrome(s)`¶

Implement a function is_palindrome(s) which takes a string s and returns the value True if s is a palindrome, and returns False otherwise. (Note that the return value is not the string “True” but the special Python value True — see the section True and False in the appendix below. The same applies to False.)

A palindrome is a word that reads the same backwards as forwards, such as “madam”, “kayak”, “radar” and “rotator”.

Examples:

In [ ]: is_palindrome('rotator')
Out[ ]: True

In [ ]: is_palindrome('radiator')
Out[ ]: False

In [ ]: is_palindrome('ABBA')
Out[ ]: True

We treat small letters (e.g. a) and capital letters (e.g. A) as different letters for this exercise: the string ABba is thus not a palindrome.

Hints for implementing a solution (Option 1):

if s is an empty string, then it is a palindrome.
if s is a string with one character, then it is a palindrome.
if the first letter of s is the same as the last letter of s, then s is a palindrome if the remaining letters of s (i.e. s[1:-1]) are a palindrome. This is algorithm is particularly easy to implement using recursion. (But you can also use a for loop.)

Recursion: to learn about recursion, take some time to study the output of this recursive factorial computation in the appendix below. Or check out the first 2 minutes and 40 seconds in this Socratica video on recursion.

Hints for implementing a solution (Option 2):

A completely different strategy would be to create a second string that contains the letters of s in reverse order
and compare that second string against s.

Appendix¶

True and False¶

True and False are special boolean values (of Python type bool), and different from strings. Here is some demonstration of this:

In [ ]: a = True

In [ ]: b = "True"

In [ ]: type(a)
Out[ ]: bool

In [ ]: type(b)
Out[ ]: str

In the function is_palindrome() above, you must return the bool value True or False, but not the string “True” or the string “False”.

Verbose recursive factorial implementation¶

We implement the factorial funcion $f(n) = n!$. We use recursion, i.e. the fact that $f(n) = n * f(n -1)$ and our knowledge that $f(1)=1$.

def f(n):
    """returns n*(n-1)*(n-2)*...*2*1"""

    if n == 1:
        return 1
    else:
        return n * f(n-1)

Here is a different implementation that prints more diagnostic output to the screen. Useful to understand how recursion works.

def f(n):
    """returns n*(n-1)*(n-2)*...*2*1

    As fsilent(n), but includes many print statements to explain flow of
    control"""

    print(f"=> Starting f({n})")
    if n == 1:
        print("if n==1 TRUE => Base case (n==1). Will return 1 and " +
              "leave function f(1)")
        return 1
    else:
        print(f"if n==1 FALSE => (n={n}), need to compute n*f(n-1) =" +
              f" {n}*f({n-1})")
        print(f"Will call f({n-1}) now ...")
        tmp1 = f(n-1)
        result = tmp1*n
        print(f"...returned from calling f({n-1}), back in f({n})")
        print(f"Multiply n*f(n-1) = {n}*f({n-1}) = {n}*{tmp1} = {result}," +
              f" leaving function f({n})")
        return result


# You may want to try different calls here, say f(1), f(2), f(3)
print(f(3))

Please submit your file lab7.py for this assignment.

Additional (voluntary) tasks are available in lab7-extra.

End of lab7.

lab7¶

count_chars(s)¶

derivative(f, x)¶

is_palindrome(s)¶

Appendix¶

True and False¶

Verbose recursive factorial implementation¶

`count_chars(s)`¶

`derivative(f, x)`¶

`is_palindrome(s)`¶