class1.txt

Eulerian path:
hitting every edge in a graph exactly once.

Every node that is not a start or ending node has to have even degree (even number of edges)

Every start and end node has to have odd degree

If a graph has only even degree nodes, it will also have a eulerian path.




3. NAIVE IMPLEMENTATION OF MULTIPLICATION (linear time)

def naive(a, b):
    x = a
    y = b
    z = 0
    while x > 0:
        z = z + y
        x = x - 1
    return z
    
    
5. RUSSIAN PEASANTS ALGORITHM (logarithmic)

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
    
    
    




8.

import math

def time(n):
    """ Return the number of steps 
    necessary to calculate
    `print countdown(n)`"""
    return 3 + (2 * math.ceil(n/5.0))

def countdown(x):
    y = 0
    while x > 0:
        x = x - 5
        y = y + 1
    print y

countdown(50)

print time(6)







9.
# counting steps in naive as a function of a

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

def time(a):
    # The number of steps it takes to execute naive(a, b)
    # as a function of a

    return (2*a +3)
    
    
    

RUSSIAN ALGO RECURSIVE


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)
    
    
    
    
    
    
    
    
    
    
HOMEWORK

3.
# Eulerian Tour Ver 1
#
# Write a function, `create_tour` that takes as
# input a list of nodes
# and outputs a list of tuples representing
# edges between nodes that have an Eulerian tour.
#

def create_tour(nodes):
    # your code here
    return [(node, nodes[(e+1)%len(nodes)]) for e, node in enumerate(nodes)]

#########

print create_tour([0, 1, 2, 3, 4, 5])

def get_degree(tour):
    degree = {}
    for x, y in tour:
        degree[x] = degree.get(x, 0) + 1
        degree[y] = degree.get(y, 0) + 1
    return degree

def check_edge(t, b, nodes):
    """
    t: tuple representing an edge
    b: origin node
    nodes: set of nodes already visited

    if we can get to a new node from `b` following `t`
    then return that node, else return None
    """
    if t[0] == b:
        if t[1] not in nodes:
            return t[1]
    elif t[1] == b:
        if t[0] not in nodes:
            return t[0]
    return None

def connected_nodes(tour):
    """return the set of nodes reachable from
    the first node in `tour`"""
    a = tour[0][0]
    nodes = set([a])
    explore = set([a])
    while len(explore) > 0:
        # see what other nodes we can reach
        b = explore.pop()
        for t in tour:
            node = check_edge(t, b, nodes)
            if node is None:
                continue
            nodes.add(node)
            explore.add(node)
    return nodes

def is_eulerian_tour(nodes, tour):
    # all nodes must be even degree
    # and every node must be in graph
    degree = get_degree(tour)
    for node in nodes:
        try:
            d = degree[node]
            if d % 2 == 1:
                print "Node %s has odd degree" % node
                return False
        except KeyError:
            print "Node %s was not in your tour" % node
            return False
    connected = connected_nodes(tour)
    if len(connected) == len(nodes):
        return True
    else:
        print "Your graph wasn't connected"
        return False

def test():
    nodes = [20, 21, 22, 23, 24, 25]
    tour = create_tour(nodes)
    return is_eulerian_tour(nodes, tour)













9.

# Write a function, `count`
# that returns the units of time
# where each print statement is one unit of time
# and each evaluation of range also takes one unit of time

def count(n):
    # Your code here to count the units of time
    # it takes to execute clique
    return 2 + n + (n*(n-1))/2

print count(4)

def clique(n):
    print "in a clique..."
    for j in range(n):
        for i in range(j):
            print i, "is friends with", j
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
10.
# Find Eulerian Tour
#
# Write a function that takes in a graph
# represented as a list of tuples
# and return a list of nodes that
# you would follow on an Eulerian Tour
#
# For example, if the input graph was
# [(1, 2), (2, 3), (3, 1)]
# A possible Eulerian tour would be [1, 2, 3, 1]

def find_eulerian_tour(graph):
        tour=[]
        startNode = graph[0][0]
        newgraph = graph[0:]
        find_tour(startNode,newgraph,tour)
        if len(tour) - 1 == len(graph):
            return tour
        return False

def find_tour(node, graph, tour): 
    for (a,b) in graph:
        if a==node:
            graph.remove((a,b))
            find_tour(b,graph,tour)
        elif b==node:
            graph.remove((a,b))
            find_tour(a,graph,tour)
    tour.insert(0,node)
            
            
        
print find_eulerian_tour([(1, 13), (1, 6), (6, 11), (3, 13),
(8, 13), (0, 6), (8, 9),(5, 9), (2, 6), (6, 10), (7, 9),
(1, 12), (4, 12), (5, 14), (0, 1),  (2, 3), (4, 11), (6, 9),
(7, 14),  (10, 13)])