PYTHON

Write a recursive function that takes a string as an input and returns the reverse of the string.

Write a recursive function rec_string that produces the output shown below for the corresponding function calls. Write a main function to test the function.

Method call rec_string(abcde), will produce the following output:

*

e

de

cde

bcde

abcde

Method call rec_string(abc), will produce the following output:

*

c

bc

abc

Write a recursive function for Euclid's algorithm to find the greatest common divisor (gcd) of two positive integers. gcd is the largest integer that divides evenly into both of them. For example, the gcd(102, 68) = 34. You may recall learning about the greatest common divisor when you learned to reduce fractions. For example, we can simplify 68/102 to 2/3 by dividing both numerator and denominator by 34, their gcd. Finding the gcd of huge numbers is an important problem that arises in many commercial applications. We can efficiently compute the gcd using the following property, which holds for positive integers p and q:

If p > q, the gcd of p and q is the same as the gcd of q and p % q.

Draw the 11-item hash table resulting from hashing the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, and 16, using the hash function h(i) = (2i + 5) mod 11 and assuming collisions are handled by linear probing.

How many comparisons are needed to find39 in the table?

How many comparisons are needed to determine that 5 is not in the table? Briefly explain.

Draw the 11-item hash table of the previous exercise, assuming collisions are handled by chaining?

How many comparisons are needed to find39 in the table?

How many comparisons are needed to determine that 5 is not in the table? Briefly explain.