15-110 PA6 Sample Solutions - Spring 2018

1.

def left(tree, index):
    if 2*index >= len(tree):
        return None
    else:
        return tree[2*index]

def right(tree, index):
    if 2*index+1 >= len(tree):
        return None
    else:
        return tree[2*index+1]

def parent(tree, index):
    if index // 2 == 0:
        return None
    else:
        return tree[index // 2]

2.

def bst_search(bst, key):
    index = 1
    while index < len(bst) and bst[index] != None:
        value = bst[index]
        if key == value:
            return True
        if key < value:
            index = 2 * index
        if key > value:
            index = 2 * index + 1
    return False

3.

def bst_search2(bst, key, index):
    if index >= len(bst):
        return False
    value = bst[index]
    if value == None:
        return False
    if key == value:
        return True
    if key < value:
        return bst_search2(bst, key, 2*index)
    else:
        return bst_search2(bst, key, 2*index+1)

4.

def create_graph1():
    f = float("inf")
    graph = [ [ 0, 1, 1, 1 ], [ 1, 0, 1, 1 ], [ 1, 1, 0, 1 ], [ 1, 1, 1, 0]]
    return graph

def create_graph2():
    f = float("inf")
    graph = [ [ 0, 1, f, f ], [ 1, 0, 1, 1 ], [ f, 1, 0, 1 ], [ f, 1, 1, 0]]
    return graph

def create_graph3():
    f = float("inf")
    graph = [ [ 0, 1, f, f ], [ 1, 0, 1, 1 ], [ f, 1, 0, f ], [ f, 1, f, 0]]
    return graph

def create_graph4():
    f = float("inf")
    graph = [ [ 0, 1, 1, 1, f, f], [ 1, 0, 1, f, 1, f], [ 1, 1, 0, 1, 1, f],
              [ 1, f, 1, 0, f, 1], [ f, 1, 1, f, 0, 1], [ f, f, f, 1, 1, 0 ]]
    return graph

def cluster_coeff(G, n):
    numnodes = len(G)
    # compute neighborhood of node
    neighborhood = []
    for i in range(numnodes):
        if G[n][i] == 1:
            neighborhood.append(i)
    # compute number of links within neighborhood
    numlinks = 0
    for j in neighborhood:
        for k in neighborhood:
            if j != k and G[j][k] == 1:
                 numlinks = numlinks + 1
    m = len(neighborhood)
    maxlinks = m * (m-1)
    return numlinks / maxlinks