Social Network

Eulerian Path

The degree of a node in a graph is the number of edges connected to that node. For more information see http://en.wikipedia.org/wiki/Degree_(graph_theory)

$A \longrightarrow B \longrightarrow D \longrightarrow A \longrightarrow C \longrightarrow D$

$A \& D$ need to have odd number endings, eg $C \longrightarrow D$ starts with 1 but end with 3.

Need for Math

Theory stuff (Math) helps

1. Formalize what you are doing

2. Analyze correctness

3. Analyze efficiency

def naive(a, b):
    x = a
    y = b
    z = 0
    while x > 0:
        z = z + y
        x = x - 1
    return z


a = 12
b = 10
print(naive(a, b))

def russian(a, b):
    x = a
    y = b
    z = 0
    while x > 0:
        if x % 2 == 1:
            z = z + y

        y = y << 1  # bit shift to the left
        x = x >> 1  # bit shift to the right
                    # eg 17 >> 1 ==> 8

    return z

Divide and Conquer

def rec_russian(a, b):
    if a == 0: return 0
    if a % 2 == 0: return 2 * rec_russian(a/2, b)
    return b + 2 * rec_russian((a-1)/2, b)