scribble

Adrian Statescu

About GitHub LinkedIn Xing Contact

01 Jan 2021
Warmup algorithms

We’ll begin our study of algorithms in a practical way, looking at four problems and multiple algorithmic solution for each problem. This lets us begin with one of the most important ideas in our field: not only are there many ways to solve a problem, but some solutions - we’ll see - can be much more efficient than others.

First example: Factorial

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# iteration
def factorial( n ):
    r = 1
    for i in range(1, n + 1):
        r *= i
    return r

>>> factorial(5)
>>>120    

# tail recursion
def factorial2( n , a ):

    if n == 1:

       return a

    else:

      return factorial2(n - 1, a * n)     

>>>n = 5
>>>factorial2(n,1)
>>>120
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# recursion
def factorial3( n ):

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

# Divide et Impera O(n log n) Time Complexity          
def factorial4( first, last ):

    if first == last:
       return first
    else:
        middle = (first + last) >> 1   
        a = factorial4(first, middle)
        b = factorial4(middle + 1, last)
        return a * b

>>> factorial4(1, 5)
>>>120    

Second example: Fibonacci

Third example: Euclid

Fourth example: Permutation

About GitHub LinkedIn Xing Contact