CS 234辅导、辅导programming component、讲解Python、Python编程调试
- 首页 >> 其他 CS 234 Spring 2019 — Assignment 4
This assignment consists of a programming component and a written component. Please read the course website
carefully to ensure that you submit each component correctly. This assignment contains 80 marks but it will be
marked out of 75 so it is possible to get over 100% on this assignment.
1 Programming Component
P1. (25 marks) In this question you will implement the Priority Queue ADT using a (min-)heap data structure.
PriorityQueue will store key-element pairs, where keys and elements can be of any type, as long as keys
are orderable (they do not need to be distinct). Submit your solution in the files priority queue.py and
binary tree.py. Working implementations that do not use the required data structure will NOT receive
correctness marks. Starting files are provided for your convenience.
PriorityQueue Interface
Pre-conditions: For lookup min and delete min, self is not empty.
Name Returns Mutates
PriorityQueue() An empty PriorityQueue.
is empty(self) True if self is empty, false otherwise.
add(self, key, element) A (key, element) pair is added to
self. See the interface for ADT
Pair.
delete min(self) The pair with minimum key in
self
Removes the pair with minimum
key from self.
lookup min(self) The pair with minimum key in
self.
Pair Interface
Name Returns Mutates
Pair(key, element) A new key-element Pair.
get key(self) Returns self’s key.
get element(self) Returns self’s element.
str(self) Returns a string representation of
self, e.g. ”(5, True)” if the key is
5, and the element is True
1BinaryTree Interface For all functions that take node/node1/node2 as one of parameters, they represent a
valid node in self. For all operations, self is a complete Binary Tree.
Name Returns Mutates
BinaryTree() An empty Binary Tree
is empty(self) True if selfis empty, false otherwise
get root(self) The root node of self.
get key(self, node) The key of node in self.
get element(self, node) The element of node in self.
get parent(self, node) Returns the parent node of node,
if one exists, and False otherwise.
get left(self, node) Returns the left child node of node,
if one exists, and False otherwise.
get right(self, node) Returns the right child node of
node, if one exists, and False otherwise.
get last(self) Returns the location of the last leaf
in self.
previous leaf(self) Returns the location of what would
be the last leaf in self if the last
leaf was removed.
next leaf(self) Returns the location of the last leaf
in self if a new leaf was added.
swap node values(self, node1,
node2)
Swaps the key-element pairs stored
in node1 and node2 in self.
add last(self, key, element) Adds a key-element pair in self at
the next leaf position.
delete last(self) Deletes the last leaf in self.
traverse(self) Prints nodes in a level-order traversal.
Details for printing below.
When traversing a Binary Tree, the key-element pair will be printed on their own line as follows:
(key, element)
For example, this program:
tree = Binary_Tree()
tree.add_last(25, "hi")
tree.add_last(10, "hello")
tree.add_last(50, "heap")
tree.add_last(5, "cs234")
tree.traverse()
prints the following:
(25, hi)
(10, hello)
(50, heap)
(5, cs234)
2P2. (15 marks) Storing sorted values in contiguous memory allows for constant time access of elements based on
their position in an array. You will implement an ADT Sorted Array that stores the inserted integers from
smallest to largest. Implement the following operations in sortedArray.py.
Sorted Array Interface
Your implementation of the sorted array ADT may store multiple instances of the same element. Order of
elements with the same value does not matter. Your implementation must use the built-in Python list to store
data, however, the only Python list operations you can use are accessing an index using square brackets, e.g.
A[i], and the length function. Any solution that uses other Python list functions will receive no marks.
You may assume that there is always space to insert a new element for testing purposes. You cannot assume
that an item is not present in the array before addition (we allow duplicates), nor can you assume an item is
present in the array before deleting it.
When performing interpolation search, use the formula b((search low)/(high low) length)c to determine
the next item to compare. When updating the low and high values from a search, set low to mid + 1 and high
to mid 1.
Name Returns Mutates
SortedArray(capacity) An empty Sorted Array that has
space for capacity elements.
is empty(self) True if self is empty, false otherwise.
item in self True if item is storted in self,
false otherwise.
access(self, index) Returns the value stored at index.
add(self, item) Stores one instance of item in
self.
delete(self, item) Removes one instance of item in
self.
linear search(self, item) A pair; its key is an index where
item may be stored, and its element
is the number of items
checked using a linear search.
binary search(self, item) A pair; its key is an index where
item may be stored, and its element
is the number of items
checked using a binary search.
interpolation search(self, item) A pair; its key is an index where
item may be stored, and its element
is the number of items
checked using an interpolation
search.
2 Written Component
W1. (10 marks)
Suppose the Binary Node N was just added to an AVL Tree. The tree must be modified to ensure that the tree
is still an AVL. Write the pseudocode for each of the following steps of modifying an AVL after an insert. You
do not need to insert N into into the Tree, nor justify the running time. However, you will be marked based
on whether your operations meet the required running times.
(a) (5 marks) Write the pseudocode for the function find pivot(Tree, N), where N is a Binary Node that
was inserted into Tree. The function returns the pivot node in Tree, or False, if no rotation is required
3after adding N into Tree. This function also updates the heights of all nodes up to and including the
pivot, if one exists. If no rotation is required, update the heights of all nodes that need to be updated.
This operation’s running time should be Θ(log n).
(b) (5 marks) Write the pseudocode for the function rebalance(Tree, N), where N is the Binary Node that
was just inserted into Tree. The function updates the heights of all affected nodes and rebalances the tree
T ree if necessary.
You must determine which rotation case must be performed to correctly pivot the nodes to make a balanced
AVL. You can call algorithms from class using the methods rotation case i(Tree, P), where P is the
pivot node and i represents the rotation cases described in class. This operation’s running time should be
Θ(log n).
W2. (5 marks) This problem will concern operations on the following AVL tree T:
(a) (1 marks) Show that T is an AVL tree by writing in the balance at each node.
(b) (2 marks) Show the process of inserting key 29 into T. Specifically, draw the tree, with balance factors,
immediately before a rotation needs to be performed. Identify the pivot node and the rotation case . Then
draw the final tree, with balance factors at each node.
(c) (2 marks) Show a similar process of deleting key 49 from the original tree T above.
W3. (5 marks) Insert 1, 2, 3, . . . 9 into an initially empty 2-3 tree. Only draw the tree after every height change and
the tree after inserting 9; the first tree you should draw is the tree on one node containing the single key 1.
W4. (10 marks)
(a) (5 marks) Let the array A contain the following keys: [3, 1, 4, 1, 17, 26, 6, 5, 9, 5, 98, 2, 6, 10]. Show the
array after each Bubble-Down call during the Heapify operation (there will be 7 such arrays). Specifically,
use the algorithm that processes the array from right to left (applying Bubble-Down procedure for each
index in the array that corresponds to an internal node of the heap), until the entire array forms a
(min-)heap, using the procedure showed in class and in slides.
(b) (5 marks) If we modify the Heapify operation to fix up the heap from left to right (rather than right to
left), while still applying the Bubble-Down procedure at each step (i.e. for each internal node of the heap),
would the resulting array produce a heap? If not, give an example of an array A (or a corresponding
binary tree) that would not generate a heap after applying this version of Heapify.
W5. (5 marks) Consider a self-organizing heuristic which alternates between Move-To-Front and Transpose. Precisely,
to organize the list after the i’th access, the accessed item is moved to front if i is odd and is swapped
with its previous item if i is even. For example, for a sequence initially ordered as [A,B,C,D], if D is searched
first and C is search second, the algorithm proceeds by moving D to the front and then swapping C with B,
resulting in [D,A,C,B].
Consider a sequence of n keys, k1, k2, . . . , kn, where n is an odd integer. Describe the sequence of n searches
that results in the maximum cost and compute the cost of performing these n searches.
W6. (5 marks) Assume that we have a hash table of size N = 5, we use the hash function f(x) = x mod 5, and
we use separate chaining for collision resolution. Demonstrate the insertion of the keys 0, 1, 2, . . . , 12 into the
(initially empty) hash table (in that order). You just need to draw the state of the hash table after all insertions
are done.
4
This assignment consists of a programming component and a written component. Please read the course website
carefully to ensure that you submit each component correctly. This assignment contains 80 marks but it will be
marked out of 75 so it is possible to get over 100% on this assignment.
1 Programming Component
P1. (25 marks) In this question you will implement the Priority Queue ADT using a (min-)heap data structure.
PriorityQueue will store key-element pairs, where keys and elements can be of any type, as long as keys
are orderable (they do not need to be distinct). Submit your solution in the files priority queue.py and
binary tree.py. Working implementations that do not use the required data structure will NOT receive
correctness marks. Starting files are provided for your convenience.
PriorityQueue Interface
Pre-conditions: For lookup min and delete min, self is not empty.
Name Returns Mutates
PriorityQueue() An empty PriorityQueue.
is empty(self) True if self is empty, false otherwise.
add(self, key, element) A (key, element) pair is added to
self. See the interface for ADT
Pair.
delete min(self) The pair with minimum key in
self
Removes the pair with minimum
key from self.
lookup min(self) The pair with minimum key in
self.
Pair Interface
Name Returns Mutates
Pair(key, element) A new key-element Pair.
get key(self) Returns self’s key.
get element(self) Returns self’s element.
str(self) Returns a string representation of
self, e.g. ”(5, True)” if the key is
5, and the element is True
1BinaryTree Interface For all functions that take node/node1/node2 as one of parameters, they represent a
valid node in self. For all operations, self is a complete Binary Tree.
Name Returns Mutates
BinaryTree() An empty Binary Tree
is empty(self) True if selfis empty, false otherwise
get root(self) The root node of self.
get key(self, node) The key of node in self.
get element(self, node) The element of node in self.
get parent(self, node) Returns the parent node of node,
if one exists, and False otherwise.
get left(self, node) Returns the left child node of node,
if one exists, and False otherwise.
get right(self, node) Returns the right child node of
node, if one exists, and False otherwise.
get last(self) Returns the location of the last leaf
in self.
previous leaf(self) Returns the location of what would
be the last leaf in self if the last
leaf was removed.
next leaf(self) Returns the location of the last leaf
in self if a new leaf was added.
swap node values(self, node1,
node2)
Swaps the key-element pairs stored
in node1 and node2 in self.
add last(self, key, element) Adds a key-element pair in self at
the next leaf position.
delete last(self) Deletes the last leaf in self.
traverse(self) Prints nodes in a level-order traversal.
Details for printing below.
When traversing a Binary Tree, the key-element pair will be printed on their own line as follows:
(key, element)
For example, this program:
tree = Binary_Tree()
tree.add_last(25, "hi")
tree.add_last(10, "hello")
tree.add_last(50, "heap")
tree.add_last(5, "cs234")
tree.traverse()
prints the following:
(25, hi)
(10, hello)
(50, heap)
(5, cs234)
2P2. (15 marks) Storing sorted values in contiguous memory allows for constant time access of elements based on
their position in an array. You will implement an ADT Sorted Array that stores the inserted integers from
smallest to largest. Implement the following operations in sortedArray.py.
Sorted Array Interface
Your implementation of the sorted array ADT may store multiple instances of the same element. Order of
elements with the same value does not matter. Your implementation must use the built-in Python list to store
data, however, the only Python list operations you can use are accessing an index using square brackets, e.g.
A[i], and the length function. Any solution that uses other Python list functions will receive no marks.
You may assume that there is always space to insert a new element for testing purposes. You cannot assume
that an item is not present in the array before addition (we allow duplicates), nor can you assume an item is
present in the array before deleting it.
When performing interpolation search, use the formula b((search low)/(high low) length)c to determine
the next item to compare. When updating the low and high values from a search, set low to mid + 1 and high
to mid 1.
Name Returns Mutates
SortedArray(capacity) An empty Sorted Array that has
space for capacity elements.
is empty(self) True if self is empty, false otherwise.
item in self True if item is storted in self,
false otherwise.
access(self, index) Returns the value stored at index.
add(self, item) Stores one instance of item in
self.
delete(self, item) Removes one instance of item in
self.
linear search(self, item) A pair; its key is an index where
item may be stored, and its element
is the number of items
checked using a linear search.
binary search(self, item) A pair; its key is an index where
item may be stored, and its element
is the number of items
checked using a binary search.
interpolation search(self, item) A pair; its key is an index where
item may be stored, and its element
is the number of items
checked using an interpolation
search.
2 Written Component
W1. (10 marks)
Suppose the Binary Node N was just added to an AVL Tree. The tree must be modified to ensure that the tree
is still an AVL. Write the pseudocode for each of the following steps of modifying an AVL after an insert. You
do not need to insert N into into the Tree, nor justify the running time. However, you will be marked based
on whether your operations meet the required running times.
(a) (5 marks) Write the pseudocode for the function find pivot(Tree, N), where N is a Binary Node that
was inserted into Tree. The function returns the pivot node in Tree, or False, if no rotation is required
3after adding N into Tree. This function also updates the heights of all nodes up to and including the
pivot, if one exists. If no rotation is required, update the heights of all nodes that need to be updated.
This operation’s running time should be Θ(log n).
(b) (5 marks) Write the pseudocode for the function rebalance(Tree, N), where N is the Binary Node that
was just inserted into Tree. The function updates the heights of all affected nodes and rebalances the tree
T ree if necessary.
You must determine which rotation case must be performed to correctly pivot the nodes to make a balanced
AVL. You can call algorithms from class using the methods rotation case i(Tree, P), where P is the
pivot node and i represents the rotation cases described in class. This operation’s running time should be
Θ(log n).
W2. (5 marks) This problem will concern operations on the following AVL tree T:
(a) (1 marks) Show that T is an AVL tree by writing in the balance at each node.
(b) (2 marks) Show the process of inserting key 29 into T. Specifically, draw the tree, with balance factors,
immediately before a rotation needs to be performed. Identify the pivot node and the rotation case . Then
draw the final tree, with balance factors at each node.
(c) (2 marks) Show a similar process of deleting key 49 from the original tree T above.
W3. (5 marks) Insert 1, 2, 3, . . . 9 into an initially empty 2-3 tree. Only draw the tree after every height change and
the tree after inserting 9; the first tree you should draw is the tree on one node containing the single key 1.
W4. (10 marks)
(a) (5 marks) Let the array A contain the following keys: [3, 1, 4, 1, 17, 26, 6, 5, 9, 5, 98, 2, 6, 10]. Show the
array after each Bubble-Down call during the Heapify operation (there will be 7 such arrays). Specifically,
use the algorithm that processes the array from right to left (applying Bubble-Down procedure for each
index in the array that corresponds to an internal node of the heap), until the entire array forms a
(min-)heap, using the procedure showed in class and in slides.
(b) (5 marks) If we modify the Heapify operation to fix up the heap from left to right (rather than right to
left), while still applying the Bubble-Down procedure at each step (i.e. for each internal node of the heap),
would the resulting array produce a heap? If not, give an example of an array A (or a corresponding
binary tree) that would not generate a heap after applying this version of Heapify.
W5. (5 marks) Consider a self-organizing heuristic which alternates between Move-To-Front and Transpose. Precisely,
to organize the list after the i’th access, the accessed item is moved to front if i is odd and is swapped
with its previous item if i is even. For example, for a sequence initially ordered as [A,B,C,D], if D is searched
first and C is search second, the algorithm proceeds by moving D to the front and then swapping C with B,
resulting in [D,A,C,B].
Consider a sequence of n keys, k1, k2, . . . , kn, where n is an odd integer. Describe the sequence of n searches
that results in the maximum cost and compute the cost of performing these n searches.
W6. (5 marks) Assume that we have a hash table of size N = 5, we use the hash function f(x) = x mod 5, and
we use separate chaining for collision resolution. Demonstrate the insertion of the keys 0, 1, 2, . . . , 12 into the
(initially empty) hash table (in that order). You just need to draw the state of the hash table after all insertions
are done.
4