#
代做SPSS|代写Python编程|代写Python程序|代写留学生 Statistics统计、回归、迭代

Identifying information will be

printed here.

University of Waterloo

Final Examination

CS 234

Term: Spring Year: 2020

Due Date: August 15, 2020, 5:00 pm

Sections: 001–002

Student Signature:

UW Student ID Number:

Number of Exam Pages 15 pages

Exam Type Online

Instructions:

• We intend for you to print the exam and complete the answers on the exam book. However, the exam can

be completed by hand on blank paper or as a pdf.

• You are responsible for submitting your exam to Crowdmark by the due date. Ensure your solutions match

the questions on Crowdmark.

• Where you are asked to provide pseudocode, you may instead choose to write Python code to describe

an algorithm. You do not need to write a design recipe for your algorithms or express their running time,

unless otherwise indicated.

• When asked to complete pseudocode, you cannot modify any of the provided pseudocode.

• Unless otherwise indicated, your solutions should only use the data structures and ADTs described on the

reference sheet. Your solutions should not use built-in Python data structures such as lists and dictionaries.

• If you believe there is an error in the exam, contact the course staff on Piazza.

• It is your responsibility to properly interpret a question.

• The amount of space allocated to a question does not necessarily reflect the length of the response required.

• If you require more space to answer a question, there are blank pages at the end you may use instead, but

you must clearly indicate in the provided answer space that you have done so. Marks for that question

will be recorded on the initial page for that question and not the additional space.

Marking Scheme

Total Mark:

CS 234 Final Examination Spring 2020 Page 2 of 15

Marks on this page: 5

1. Hashing

(a) (2 marks) List two properties of a good function for hashing.

Why is each of the following not a good hash function for h(k) = f(k) mod N where N is the

number of slots in the hash table?

(b) (1 mark) f(k) = 2 ∗ k, where k is an integer

(c) (1 mark) f(k) = sum of the digits of k, where k is an integer

(d) (1 mark) f(k) = length of k where k is a string that is one English word

CS 234 Final Examination Spring 2020 Page 3 of 15

Marks on this page: 4

Suppose we have a hash-table that is implemented well. That is, the expected runtime of each

operations is θ(1). For each of the following ADTs, would you implement the ADT with a

hash-table? If you would, briefly describe the operations for inserting and deleting? If you would not,

what is one operation it would make more complicated to implement than an implementation from

class? Why is this operation complicated?

(e) (2 marks) Set

(f) (2 marks) Stack

CS 234 Final Examination Spring 2020 Page 4 of 15

Marks on this page: 4

2. (2,3)-Tree

(a) (4 marks) Write the function find node(T, key) that consumes a (2,3)-Tree T and an

integer key and produces the leaf node in T that key can be inserted into (before a possible

split). If T is empty, return False. You may assume key is not present in T.

CS 234 Final Examination Spring 2020 Page 5 of 15

Marks on this page: 5

(b) (2 marks) Suppose we have a (2,3)-Tree that contains the keys 1 to 7. What is the minimum and

maximum height the tree can be? Draw an example of a minimum and maximum height

(2,3)-Tree.

(c) (3 marks) Given the following (2,3)-Tree, insert 70.

20 40

4 12 26 34 63 81

CS 234 Final Examination Spring 2020 Page 6 of 15

Marks on this page: 4

3. Algorithm Analysis

(a) (4 marks) The following is a graph algorithm for finding the shortest path from start (which is a

vertex) to all other vertices.

Determine the runtime of the algorithm in Big-O notation in terms of the functions and

operations used for all ADTs used (Set, Dictionary, and Graph). Assume that the graph is

connected and has n vertices and m edges. You may assume each node has at most d neighbours.

Use R(f unction) to denote the runtime for a function. For example, R(Vertices) represents the

runtime of Vertices.

short_paths(Graph, start):

V <- Vertices(Graph) // returns a Set

Distance <- Dictionary()

Prev <- Dictionary()

for i from 0 to Len(V) - 1:

v <- Access(V, i)

Add(Distance, v, Infinity)

Add(Prev, v, None)

Add(Distance, start, 0)

while not Is_Empty(Distance):

min <- Minimum(Distance)

Delete(V, Key(min))

for v in Neighbours(Graph, Key(min)):

dist <- Value(min) + Edge_Value(Graph, Key(min), v)

if dist < Lookup(Distance, v):

Add(Distance, v, dist)

Add(Prev, v, Key(min))

return Pair(Distance, Prev)

CS 234 Final Examination Spring 2020 Page 7 of 15

Marks on this page: 7

(b) (2 marks) Simplify the runtime for the previous operation given that the operations for

Dictionary and Set have the following runtimes:

Set: Access - O(1), Delete - O(1)

Dictionary: Dictionary - O(1), Add - O(logn), Delete - O(logn), Is Empty - O(1), Minimum -

O(logn)

Simplify the runtime from part b) given each implementation of the Graph ADT and the runtime of

the operations.

(c) (1 mark) Edge List: Vertices - O(m), Neighbours - Neighbours - O(m), Edge Value - O(m)

(d) (1 mark) Adjacency List: Vertices - O(n), Neighbours - O(d), Edge Value - O(d), where d is

the degree of the vertex.

(e) (1 mark) Adjacency Matrix: Vertices - O(n), Neighbours - O(n), Edge Value - O(1)

(f) (2 marks) Which implementation has the best runtime for vertices having at most 3 neighbours?

Justify your choice.

CS 234 Final Examination Spring 2020 Page 8 of 15

Marks on this page: 4

4. Heap

In class, we looked only a min heap. However, by reversing the heap order property, i.e. the values in

the children of a node must be smaller than in the node, we will have a max heap.

(a) (1 mark) A min heap is implemented to find and remove the minimum value quickly. What

were the runtimes for the following operations?

insert(Heap, Value)

find min(Heap)

remove min(Heap)

(b) (3 marks) Your friend comes to you and proposes a new ADT, a Min-Max-Heap. They suggest

that the ADT will be able to find and remove the minimum and maximum items in logarithmic

time.

They plan to implement that ADT using a Min Heap and a Max Heap. They will insert each new

added item into both heap as follows.

insert(MMHeap, item):

MMHeap.min_heap.insert(item)

MMHeap.max_heap.insert(item)

Explain why the delete min and delete max functions for this implementation will not be

in logarithmic time.

CS 234 Final Examination Spring 2020 Page 9 of 15

Marks on this page: 3

(c) (3 marks) Consider the following MinMaxNode class.

class MinMaxNode:

def __init__(self, value):

self.value = value

self.min_parent = None

self.min_left = None

self.min_right = None

self.max_parent = None

self.max_left = None

self.max_right = None

Using this class to store a value in both a Min Heap and a Max Heap would allow us to remove

the node from both heaps in logarithmic time.

We want to write the delete min function for a MinMaxHeap. Finish the function below.

delete_min(MMHeap):

# returns the MinMaxNode removed from the min_heap

node = MMHeap.min_heap.delete_min()

min_value = node.value

# write the code that removes the node from the max heap

CS 234 Final Examination Spring 2020 Page 10 of 15

Marks on this page: 6

5. AVL

(a) (3 marks) Consider the following AVL tree. Write the balances

height(right subtree)−height(left subtree)

of all nodes (in the figure itself).

(b) (3 marks) Draw the AVL tree obtained by deleting 27 from the one above. Give the balances of

all nodes.

CS 234 Final Examination Spring 2020 Page 11 of 15

Marks on this page: 7

6. Interpolation Search

(a) (3 marks) What is the running time of interpolation search on A = [1,2,...,n−1,n

1000] if we

are searching for n−1? Justify your answer.

(b) (4 marks) Suppose A is an array of size 16 and A[i] = t

√

i for 0 ≤ i ≤ 15 where t is some positive

number. If we are searching for t in A using interpolation search, in how many iterations does the

algorithm terminate? Compare the running time of this search with the average case (for evenly

spaced data) running time of interpolation search. Justify your answer and explain the difference.

CS 234 Final Examination Spring 2020 Page 12 of 15

Marks on this page: 5

7. Trie

(a) (2 marks) Draw the standard trie (with alphabet {0,1}) that is obtained after inserting the

following keys into an initially empty trie:

1011,001,1101,10010,10,11,10100,1,000,101,00

(b) (3 marks) Find the exact height, in terms of k, of the trie with keys that are binary

representations of numbers 0,1,2,3,4,...,2

k −1 without leading 0s, and inserted into the trie in

increasing order. That is, insert 0,1,10,11,100, etc.

CS 234 Final Examination Spring 2020 Page 13 of 15

Marks on this page: 3

8. Skip-List Consider the skip-list L shown below.

Show how Search(L,360) proceeds. More specifically show the order of all nodes of the skip list that

are visited (you do not need to include the positions that are looked up but not visited). You should

refer to the nodes using their keys and levels, e.g. (104,L1). The lowest/bottom level is L0.

CS 234 Final Examination Spring 2020 Page 14 of 15

Marks on this page: 4

9. Improving Implementations

When working with ADTs, we can often improve the running time of operations by augmenting the

data structure with additional information.

For example, the size of the subtree rooted at each node can be stored in the node. This enables a

logarithmic time search for the i

th largest element in the tree. However, this additional information

must be maintained by all operations.

Suppose we want to add this augmentation to the Binary Search Tree ADT. We will add the field

size in each node to store the size of the subtree rooted at the node. Add the modifications needed to

the pseudocode provided for add leaf to ensure that all nodes in the tree have the correct size after

a value is added. Recall that add leaf may replace a subtree that already exists with a single node.

You may assume that the field size is set to 1 when a Node is created and that the size field is

maintained for all Nodes prior to this operation being called.

There is a field in the Binary Search Tree ADT called root that stores the root of the tree.

add_leaf(T, Value, Parent, Side):

if Parent == None:

T.root = Node(value)

else if Side == "left":

Parent.left = Node(value)

else:

Parent.right = Node(value)

(a) (1 mark) What is the runtime of add leaf? You may assume that all other BinaryTree and

Node operations on the reference sheet have a constant runtime. No justification is required.

CS 234 Final Examination Spring 2020 Page 15 of 15