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)
need to have odd number endings, eg starts with 1 but end with 3.
Need for Math
Theory stuff (Math) helps
Formalize what you are doing
Analyze correctness
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)
Last updated