Analysis of algorithms

Mathematics of algorithms
1)Formalize what you’re doing
2)analyzing correctness
2)analyzing the efficiency

Measuring Times
Simplifying assumptions
1. a simple statement takes one unit of time (e.g. x = x + 1 => 1 unit)
2. a sequence of simple statement is the sum of the individual times (e.g. if y==4: z = z/2 => 2 units)
3. A Loop takes time equal to the body x iterations (e.g. for i in range(4): print i => 4 units)

Example 1 Product (naive algorithm)

#python code to multiple 2 number 
#by naive method
def product(a,b):
    x = a
    y = b
    z = o
    # the above consider as 3 units of time
    # x= a; y = b consider as 2 units of time
    while (x>0):
        z = z + y
        x = x -1
        # inside while loop 2 units of time 
    return z

#The number of steps it takes to execute
#execute product(a, b) as a function of a
def time(a):
    # 3(assign), 2(while)
    return a * 2 +3
        
print product(10,5) => 50
print time(5) => 23

#Recursive naive product:
def rec_naive(a,b):
	if a==0: return 0
	return b+ rec_naive(a-1,b)

rec_naive(17,6) => 102
Correctness of product(a,b) = ab
1.Claim: before or after “while” loop ab = xy+z
2.case: first time through, x=a, y=b, z=0 => ab = ab+0
3.Inductive step: if ab = xy + z (before)
then ab = x’y’+z’ (after)
x’ = x- 1, y’ =y, z’ = z+y
x’y’+z’ => (x-1)(y)+z+y => xy-y+z-y => xy+z => ab
we know ab= xy+z, so?
x = 0, xy +z = ab => 0.y+z = ab => z = ab
Running time of product(a,b)
rougly linear => t = cn

Example 2 Russian Peasant’s Algorithm ( Ancient Egyptian Multiplication)

def russian(a,b):
    x = a; y=b
    z = 0
    while (x>0):
        if x % 2 ==1: z = z + y
        y = y << 1
        x = x >> 1 
    return z
    
print russian(14,11)

x  y    z
14 11   0
7  22   0
3  44  22
1  88  66
0 176 154 

x14 >> 1
64 32 16 8 4 2 1
         1 1 1 0  14
         0 1 1 1  7  
         0 0 1 1  3
         0 0 0 1  1

y11 << 1
64 32 16 8 4 2 1
         1 0 1 1  11
       1 0 1 1 0  22  
    1  0 1 1 0 0  44
1   0  1 1 0 0 0  88
Correctness of russian(a,b)= ab
1.case i: x is odd x’ = x-1/2, y’ =2y, z’ =z+y
x’y’+z’ = (x-1)/2 * 2y +z +y => xy -y +z +y => xy + z = abcase ii : x is even x’ = x/2, y’ = 2y, z’ = z
x’y’+z’ = x/2 * 2y + z => xy +z = ab
Inductive step: if ab = xy + z holds
then ab = x’y’ + z’ afterwardshow many times can you divide a number x in half (rounding down ) before it hits zero
x 0 1 2 3 4 5 6 7 8 9 10 11
hits 0 1 2 2 3 3 3 3 4 4 4  4
log2x 0 1 1 1 2 2 2 2 3 3 3  3 => log2x + 1

log211 = round(3.4) = 3 + 1 = 4

Measuring times – Steps to execute
1.Don’t know number times while loop is going to execute (if x%2, y = , x =).
this is floor(log2a + 1)
2.3 (if x%2, y = , x =) units of time will execute + 1 (4th z=) will execute if x is odd
3(log2a+1)+ 3+ # of “on” bits in a => 4 (log2a) + 7
# of “on” bits in a = log2a>+1

The floor(log2a)+1 is the amount of times we need to compute inside the while loop, so we have 3 lines (if, y, x), therefore 3* floor(log2a))+1 = > 3floor(log2a)+3. if x is odd, floor(log2a)+1 the amount of time will compute, then we have 3 line that is non-recursive (before while loop), which is just a constant(‘+3’), finally total of 3floor(log2a)+3 +floor(log2a)+1 +3 => 4floor(log2a)+7

Product vs Russian – which one is faster?
product (223, 223) = 3 Seconds
Russian (21000, 21000) = 2 Milli seconds

Example: Measuring Times

Total 12 units of time

def times():
1x   s=0
     for i in range(10):
10x      s=s+1
1x   print s
def countdown(x):
1x    y =0
10x    while x >0 :
             x = x - 5
             y = y - 1
1x    print y
1x print countdown(50)

time(50) => 23 times => 3 + 2 * math.ceil(n/5.0)

Divide and Conquer – Break a problem into roughly equal sized sup problems, solve separately, combine result

for example, a x b = b+ b +b + ….+ b  => a even
      = b+b+…+b   b+b+…+b  (a times)
      = 2 (b+b+…+b) (a/2 times) (a/2 times) 

#rec-reussian recurrence relation

def rec_russian(a, b):
     if a == 0: return 0
     if a % 2 == 0: 2 * return rec_russian(a/2, b)
     return b + 2 * rec_russian((a-1)/2, b) 
Measuring times
The log2a+1 is the amount of times we need to compute inside the the recursive part of the function, so we have 3 lines, therefore 3* (log2a+1) = > 3log2a+3. if a == 0, only one step is executed, which is just a constant(‘+1’), finally total of 3log2a+3+1 => 3log2a+4
Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: