Written Addition#

# we ignore the table for the moment

# N-digit numbers are given as a list
X = [3,2,3]
Y = [9,5,8]
print("X=",X)
print("Y=",Y)

N = len(X)
print(N)

X= [3, 2, 3]
Y= [9, 5, 8]
3

def add(a,b):
    """adds two numbers, a and be have to have equal number of digits"""
    assert len(a) == len(b), "This implementation expects equal-length digits"
    ret = []
    carry = False # Track whether we need to add a one to the next digit
    for i in range(len(a)):
        table_result = a[len(a)-1-i] + b[len(b)-1-i]  # this is just from right to left
        if carry:
            table_result = table_result +1 # increment if previous was too large
            carry = False
        if table_result >= 10: # set up carry and correct digit to one digit
            table_result = table_result - 10
            carry = True
        ret = [table_result, *ret] # collect results
    if carry:
        ret = [1, *ret] # final carry
    return ret
    
print(add(X,Y))
323+958

[1, 2, 8, 1]

The * Operator#

Given any iterable construction python (like a list, anything you can run a for loop over), you can replace the iterable container with its values by using the * operator as above where we create the return value.

Complexity of an Algorithm#

Ideas from the class

how often you access data
how often you have a certain instruction
the runtime in the sense of the number of loops / nesting of loops
the growth depending on the problem size

Complexity (independent of the actual machine) is the rate of growth of instructions based on the size of the input.

Variants for size of the ouput exist as well

Recursion#

\[ n! = \prod_{i=1}^n i\]

This can be solved directly as a loop, see factorial below. However, we can also give a recursion formula

\[ n! = n \cdot (n-1)!\]

$$ 0! = 1! = 1$$’

# sequential
def factorial (n):
    ret = 1
    for i in range(n):
        ret = ret * (i+1)
    return ret;

factorial(5)

def factorial2(n):
    if n == 1:
        return 1
    return n * factorial2(n-1)

factorial2(5)
    

def compute_factorial_unless_larger_than(n, t):
    if n == 1:
        return 1
    tmp = n *  compute_factorial_unless_larger_than(n-1,t)
    if tmp > t:
        return False
    return tmp

compute_factorial_unless_larger_than(5, 100)

# Inefficient, as we cannot stop the recursion procedure at the moment where we are finding that the treshold is exceeded.
# Useless computation is the consequence:
# Solution:
# - Exceptions are often interpreted as errors, but they can unwind the stack and are sometimes just signals of success.
    

False

def compute_factorial_unless_larger_than2(n, t):
    ret = 1
    for i in range(n):
        ret = ret * (i+1)
        if ret > t:
            return False
    

Take-Away Message:#

Recursion is elegant, very often it is easier to proof correctness, often source code is shorter, avoids local variables, and many other good things, but it can be slower (because you cannot easily stop the recursion), has a size bound in practice (the call stack is not unlimited). Tail recursion (wikipedia) can always be reformulated as a loop and full recursion can always be simulated using an explicit stack data variable

Strings with ” vs. ‘#

# The results are the same
x = "test"
y = 'test'
print(x,y)

# But, the " is being processed by formatting while the other is not
# The not case first
# NEed to look up on the history of it, it used to be as I tried to explain, but it is not

test test

Dictionaries#

# Dictionary

x = dict()
print(x)
x = {}
print(x)
# Dictionary is key-value
data = {"name": "TUM", "type": "university", "numberofstudents": 42 }
# accessed using the keys as indices
print (data["name"])
print(data)
for x in data:
    print("%s ==> %s" % (x, str(data[x])))
    
# you can do the same as with list expressions

x = {"id_%d" %(x): x for x in range(100)}
print(x)
# Dictionaries are quite good at accessing few elements 

data = [[1,2],[3,4],[5,6]]
# task is to find a point with Y == 6
# good solution (especially if many times you are looking for a specific value of y)

index = {y:x for x,y in data}
print("Found for 6:", index[6])

{}
{}
TUM
{'name': 'TUM', 'type': 'university', 'numberofstudents': 42}
name ==> TUM
type ==> university
numberofstudents ==> 42
{'id_0': 0, 'id_1': 1, 'id_2': 2, 'id_3': 3, 'id_4': 4, 'id_5': 5, 'id_6': 6, 'id_7': 7, 'id_8': 8, 'id_9': 9, 'id_10': 10, 'id_11': 11, 'id_12': 12, 'id_13': 13, 'id_14': 14, 'id_15': 15, 'id_16': 16, 'id_17': 17, 'id_18': 18, 'id_19': 19, 'id_20': 20, 'id_21': 21, 'id_22': 22, 'id_23': 23, 'id_24': 24, 'id_25': 25, 'id_26': 26, 'id_27': 27, 'id_28': 28, 'id_29': 29, 'id_30': 30, 'id_31': 31, 'id_32': 32, 'id_33': 33, 'id_34': 34, 'id_35': 35, 'id_36': 36, 'id_37': 37, 'id_38': 38, 'id_39': 39, 'id_40': 40, 'id_41': 41, 'id_42': 42, 'id_43': 43, 'id_44': 44, 'id_45': 45, 'id_46': 46, 'id_47': 47, 'id_48': 48, 'id_49': 49, 'id_50': 50, 'id_51': 51, 'id_52': 52, 'id_53': 53, 'id_54': 54, 'id_55': 55, 'id_56': 56, 'id_57': 57, 'id_58': 58, 'id_59': 59, 'id_60': 60, 'id_61': 61, 'id_62': 62, 'id_63': 63, 'id_64': 64, 'id_65': 65, 'id_66': 66, 'id_67': 67, 'id_68': 68, 'id_69': 69, 'id_70': 70, 'id_71': 71, 'id_72': 72, 'id_73': 73, 'id_74': 74, 'id_75': 75, 'id_76': 76, 'id_77': 77, 'id_78': 78, 'id_79': 79, 'id_80': 80, 'id_81': 81, 'id_82': 82, 'id_83': 83, 'id_84': 84, 'id_85': 85, 'id_86': 86, 'id_87': 87, 'id_88': 88, 'id_89': 89, 'id_90': 90, 'id_91': 91, 'id_92': 92, 'id_93': 93, 'id_94': 94, 'id_95': 95, 'id_96': 96, 'id_97': 97, 'id_98': 98, 'id_99': 99}
Found for 6: 5

Principles of Programming

Written Addition

Contents