Homework

13.4.3. Homework#

  • Use these questions after class to check your understanding of the chapter concepts and coding skills.

  • Sign in from the account menu before you start working on the homework.

  • Complete all true/false and coding questions before you submit the homework.

  • Launch Live Code (the rocket) to write and run code in the coding cells.

  • Multiple submissions are allowed. The highest score is kept.

1. Stacks

Undo history is naturally modeled as a stack because the most recent action is removed first.

Hide code cell source

 
### Solution
# True
# A stack is last in, first out (LIFO). Each action is pushed on top, and undo pops the
# most recent action first.

2. Queues

A service line is naturally modeled as a queue because the earliest arrival should usually be served first.

Hide code cell source

 
### Solution
# True
# A queue is first in, first out (FIFO). New arrivals join at the back and the earliest
# arrival is served from the front.

3. Trees

A tree node can have any number of parents and still remain a tree.

Hide code cell source

 
### Solution
# False
# In a tree, every node except the root has exactly one parent, and the root has none. A
# node with more than one parent makes the structure a graph rather than a tree.

4. Graphs

Course prerequisites can be represented as a graph because courses can connect to other courses through dependency relationships.

Hide code cell source

 
### Solution
# True
# A graph is a set of nodes connected by edges. Each course is a node, and each
# prerequisite is an edge that connects the required course to the course that depends
# on it.

5. ADT Interfaces

An abstract data type is defined mainly by the exact variable names used inside its implementation.

Hide code cell source

 
### Solution
# False
# An abstract data type is defined by its interface: the operations it supports and how
# they behave, such as push and pop for a stack. The internal variable names are
# implementation details that can change without changing the ADT.

### 6. Use a stack
# Push three pages and pop the most recent page. Print exactly these two lines:
# # Back to: checkout
# # Remaining stack: ['home', 'products']
history = []

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
history = []
history.append("home")
history.append("products")
history.append("checkout")
last_page = history.pop()
print("Back to:", last_page)
print("Remaining stack:", history)

Back to: checkout
Remaining stack: ['home', 'products']

### 7. Traverse a binary tree
# Use the Node class to build this binary tree:
#         1
#       /   \
#      2     3
#     /     / \
#    4     5   6
# Write preorder, inorder, and postorder functions that each return a list of values.
# Print exactly these three lines:
# # Preorder: [1, 2, 4, 3, 5, 6]
# # Inorder: [4, 2, 1, 5, 3, 6]
# # Postorder: [4, 2, 5, 6, 3, 1]
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree = Node(1)
tree.left = Node(2)
tree.right = Node(3)
tree.left.left = Node(4)
tree.right.left = Node(5)
tree.right.right = Node(6)

def preorder(node):
    if node is None:
        return []
    return [node.value] + preorder(node.left) + preorder(node.right)

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

def postorder(node):
    if node is None:
        return []
    return postorder(node.left) + postorder(node.right) + [node.value]

print("Preorder:", preorder(tree))
print("Inorder:", inorder(tree))
print("Postorder:", postorder(tree))

Preorder: [1, 2, 4, 3, 5, 6]
Inorder: [4, 2, 1, 5, 3, 6]
Postorder: [4, 2, 5, 6, 3, 1]

### 8. Represent a tree
# Use the TreeNode class to build this team tree, with CEO as the root:
#   CEO
#     Data
#     Operations
# Link each child to its parent with add_child(). Then build a list of the values of
# the root's children. Print exactly this line:
# # Direct reports: ['Data', 'Operations']
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)

ceo = TreeNode("CEO")
ceo.add_child(TreeNode("Data"))
ceo.add_child(TreeNode("Operations"))

direct_reports = [child.value for child in ceo.children]
print("Direct reports:", direct_reports)

Direct reports: ['Data', 'Operations']

### 9. Represent a graph
# Use a dictionary of adjacency lists. Print exactly this line:
# # DS200 neighbors: ['DS300', 'ML310']
graph = {"DS100": ["DS200"], "DS200": ["DS300", "ML310"]}

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
graph = {"DS100": ["DS200"], "DS200": ["DS300", "ML310"]}
print("DS200 neighbors:", graph["DS200"])

DS200 neighbors: ['DS300', 'ML310']

### 10. Build a binary search tree
# Write insert(root, value) and contains(root, value) for a binary search tree.
# Insert the values in order, starting from an empty tree (None).
# Then print the inorder traversal and check one present value and one absent value.
# Print exactly these three lines:
# # Inorder: [10, 25, 30, 45, 60, 70, 85]
# # Contains 30: True
# # Contains 55: False
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

values = [45, 25, 70, 10, 30, 60, 85]

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

values = [45, 25, 70, 10, 30, 60, 85]

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    elif value > root.value:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    node = root
    while node is not None:
        if value == node.value:
            return True
        if value < node.value:
            node = node.left
        else:
            node = node.right
    return False

def inorder(node):
    if node is None:
        return []
    return inorder(node.left) + [node.value] + inorder(node.right)

bst = None
for num in values:
    bst = insert(bst, num)

print("Inorder:", inorder(bst))
print("Contains 30:", contains(bst, 30))
print("Contains 55:", contains(bst, 55))

Inorder: [10, 25, 30, 45, 60, 70, 85]
Contains 30: True
Contains 55: False