### CSC 148H past final exams ###
### August 2010 ###

### Question 1 ###

"""

Part a)

No, because not all levels are filled from the left to the right. (node '12'
has a right child, but no left child)

This violates the first property of a min heap: every 'level' is filled from
the left.

Part b)

Yes, it respects both properties of a min heap.

Part c)

No, because node '8' has a child smaller than him. (node '3')

This violates the second property of a min heap: no parent has a child with
a smaller value.

"""

### Question 2 ###

"""

Part a)

The list representing the new heap would be:
L = [1, 6, 2, 8, 9, 4, 5, 12]

Part b)

The list representing the new heap would be:
L = [5, 7, 9, 10, 12]

"""

### Question 3 ###

"""

Part a)

"""

def _parent(index):
    ''' Return the index of the parent of the specified index in a heap. '''

    return (index - 1) / 2

def _left_child(index):
    ''' Return the index of the left child of the specified index. '''

    return index * 2 + 1

def _right_child(index):
    ''' Return the index of the right child of the specified index. '''

    return index * 2 + 2

def is_min_heap(L):
    ''' Takes a list L and returns True if the list is a representation of a min
    heap and False otherwise. '''

    i = 0
    while _left_child(i) < len(L):
        if L[i] > L[_left_child(i)] or L[i] > L[_right_child(i)]:
            return False
        i += 1

    return True

"""

Part b)

Answer: Yes.

"""

### Question 4 ###

"""

Part a)

The output is: [100, 0, 0, 0]

Part b)

The output is: [0, 0, 0, 0]

"""

### Question 5 ###

class Node(object):
    ''' A linked list node containing data and a reference to the next node. '''
    def __init__(self, data):
        ''' A new node to hold data and no next node. '''
        self.data = data
        self.next = None

class LinkedList(object):
    ''' A linked list implementation of a list. '''
    def __init__(self):
        ''' A new empty list. '''
        self.head = None

def sum_every_other(L):
    ''' Takes a list L and returns the sum of every other element of L. '''

    if L == []:
        return 0
    else:
        return L[0] + sum_every_other(L[2:])

def duplicate(L):
    ''' Takes a list L and duplicates every node. It modifies L so that it
    contains every element from the original list twice in a row. '''

    for i in range(len(L)):
        L.insert(i + i, L[i + i])

### Question 6 ###

"""

The output is: 'AHH'

"""

### Question 7 ###

def reverse_stack(stack):
    ''' Takes as input a stack and returns a new stack that contains all the same
    items, but in reverse order. '''

    new_stack = Stack()
    return reverse_stack_helper(stack, new_stack)

def reverse_stack_helper(stack, new_stack):
    ''' A helper function for reverse_stack. '''

    while not stack.is_empty():
        new_stack.push(stack.pop())

    return new_stack

### Question 8 ###

class Node(object):
    ''' A node of a binary tree. '''

    def __init__(self, key):
        ''' A new node to hold data and with no children. '''

        self.key = key
        self.right = None
        self.left = None

class BinaryTree(object):
    ''' A binary tree. '''

    def __init__(self):
        ''' Creates an empty binary tree. '''

        self.root = None

def print_even(bst):
    ''' Prints the even values of a binary search tree in ascendin order. '''

    print_even_helper(bst.root)

def print_even_helper(node):
    ''' Prints the even values of a binary search tree rooted at the given
    node (in ascending order). '''

    if not node:
        return
    else:
        print_even_helper(node.left)
        print node.key
        print_even_helper(node.right)

### Question 9 ###

"""

Not necessary. :-)

"""

### Testing out the code. ###

##if __name__ == "__main__":

    ##a = Node(8)
    ##a.left = Node(3)
    ##a.left.left = Node(1)
    ##a.left.right = Node(6)
    ##a.left.right.left = Node(4)
    ##a.left.right.right = Node(7)
    ##a.right = Node(10)
    ##a.right.right = Node(14)
    ##a.right.right.left = Node(13)
    ##tree = BinaryTree()
    ##tree.root = a

    ##print_even(tree)

    ##L = [1,4,2,5,8,6,3]
    ##print is_min_heap(L)