Programming and Algorithms II
Degree in Bioinformatics
Fall 2018

***************************************************
*** Lab 2:                                      ***
*** Simple recursion                            ***
***************************************************

Part 1: 

The binomial(n,m) number is defined for every n >= m >= 0

binomial(n,m) = n! / (m! (n-m)!)               

By simplification, this is equal to:

binomial(n,m) = (n (n-1) ... (n-m+1)) / (m ... 1)   

It is mostly irrelevant for this lab, but binomial(n,m) happens to be 
the number of subsets of size m of a set of n elements. 
This implies that it is always a natural number,
which is not obvious (to me, at least) from the definitions above.

In everything that follows, do not use / (real division), 
only // (integer division). This means that you have to ensure 
that the division is exact, otherwise you will lose accuracy. 
No floats should appear anywhere, neither in the program
code nor during the computation.

Exercise 1: 
Observe that binomial(n,m) = binomial(n,m-1) * SOMETHING.
Find out the SOMETHING and use this formula to give a 
linear recursive algorithm to compute binomial(n,m). 
Which is the base case?

Use only // and not /, so you have to be sure that all divisions
you do are exact.

You can check your algorithm by executing, for example:

>>>print([binomial(5,m) for m in range(5+1)])

which sould give 

[1, 5, 10, 10, 5, 1]

Try doing it with n=200 instead of n=5.

Exercise 2 (optional, after you have done Parts 2 and 3 below):
Observe also that 
binomial(n,m) = binomial(n-1,m) * SOMETHING
and that 
binomial(n,m) = binomial(n-1,m-1) * SOMETHING

Give recursive algorithms based on these formulas.
Take care with the base cases.

--------------

Part 2:

Say that a string is a palindrome if it is the same read forwards
and backwards.

Give a recursive algorithm to decide if a string is a palindrome.
It should run in time O(length of the string). 

Use only the [] and len() operations on strings (s[i] gives the i-th 
character of a string).

Get inspiration from the "product of a list" problem in the theory slides
to make it efficient.

--------------------------

Part 3: 

Write a recursive function that takes two string s1 and s2 and tells
whether s1 is a prefix of s2. For example "ab" is a prefix of "abc", "abcd" and "ab",
but not of "ba" or "a".

Think on strings first. Base cases: When can you claim that s1 is a prefix of s2
right away, without looking into its content? When can you claim that s1 is for sure NOT 
a prefix of s1, only from its length? Otherwise, how do you do recursion by looking
at smaller pieces of s1 and s2?

Then add parameters to avoid copying substrings. Use only [] and len().

---------------


In all the labs: 
Aim at having clean code. Use functions a lot. Document your functions.