Algorithms -- 2009-2010 -- info.uvt.ro/Laboratory 2

Notes

• Python notes (everything, including functions):
  • Python -- First Steps (in English);
  • Python -- Primii Paşi (in Romanian);

• Laboratory / seminar problem set 1:
  • in English (from profesor Daniela Zaharie);
  • in Romanian (from profesor Daniela Zaharie);

• Laboratory / seminar 2 problem set:
  • in English (from profesor Daniela Zaharie);
  • in Romanian (from profesor Daniela Zaharie);

Exercises

From the first problem set, exercises:

• similar to problem 8 (for en), or 9 (for ro), but for the function $\sum _{i=0}^{\mathrm{\infty }}\frac{x^i}{i!}$; (which is the approximation of $e^x$, where x in near to 0;)
• problem 9 (for en), or 10 (for ro) (Fibonacci sequence, and the fraction between two consecutive terms);

From the second problem set, exercises:

• 1, set operations:
  • membership;
  • union;
  • intersection;

Assignment

For submission please follow: assignment 2.

From the first problem set, exercises:

• problem 9 (for en), or 10 (for ro), point d, random number generation using congruential method; (see wikipedia:Linear congruential generator;)
• like in the context of the problem 8 (for en), or 9 (for ro): approximation of the function: $\sum _{i=0}^{\mathrm{\infty }}\frac{-1^i{x}^{2\cdot i}}{(2\cdot i)!}$

From the second problem set, exercises:

• in the context of problem 1, difference between two sets:
  • those elements that are in A but not in B; (see wikipedia:Complement (set theory)#Relative complement;)
  • symmetric difference (those elements that are either in A or in B); (see wikipedia:Symmetric difference;)

Solutions

• computing $\sum _{i=0}^{\mathrm{\infty }}\frac{x^i}{i!}$ with a given precision:

p = input ("precision = ")
x = input ("x (between 0 and 1) = ")

pt = 1 # previous term
ct = x # current term
cti = 2 # current term index
s = pt + ct # the sum

while abs (pt - ct) > p :
    pt = ct
    ct = float (pt * x) / float (cti)
    cti += 1
    s += ct

print s

# the result for x = 0.5 should be around to 1.6487

• approximation of the ratio between two consecutive Fibonacci terms:

p = 0.00001 # precission

pt = 1 # previous fibonacci term
ct = 1 # current fibonacci term
cr = float (ct) / float (pt) # current ratio
pr = cr + 2 * p # previous precission

while abs (pr - cr) > p :
    pr = cr
    a = pt
    pt = ct
    ct = ct + a
    cr = float (ct) / float (pt)

print cr

# the result should around 1.618