Basic Algorithms (CS 301, Section 1), Professor Yap – Fall 2021
HOMEWORK
October 12, 2021
Homework 4 Due: Tuesday Oct 19, 2021
INSTRUCTIONS:
• Carefully read the Class Integrity Policy in our Class Wiki.
• Go to our Homework Page for general information about Homework.
• REMEMBER: all answers must show some justification! This is even true when the
actual answer is short. E.g., in True/False questions or questions that ask for a single
number for an answer.
QUESTIONS:
Q 1. (5+10+5+10+10 Points) Priority Queues
Refer to Lecture 4 (4-pqueues.pdf) for this question. A priority queue is an ADT
(abstract data type) supporting two operations: insert(key) and deleteMin(). This
can be implemented using a binary heap data structure. The binary heap is a binary
tree of a special shape, that is represented by an array A[1...N]. If the current size
of the queue is n then we have 0 ≤ n ≤ N. Thus the variable n is part of the data
representation, and it is incremented (resp., decremented) after an insert(k) (resp.,
a deleteMin()).
(a) Please do a hand-simulation to insert the key 0 (zero) into the Binary Heap of
Figure 1. Imitate Slide 2 of Lecture 4 in its hand-simulation of insert(2). The
idea is to let the key 2 “float up” as much as possible.
Figure 1: insert(0) into this Binary Heap
HINT: Please display the arrays A[1..n] as a binary tree, not a sequence of keys!
Why? Because we humans are incredibly good with visual images; leave the sequences
to computers!
1
(b) Give the pseudo-code for insert(k) to insert key k into a binary heap. HINT:
Use the macros LeftChild(i), RightChild(i), parent(i) in Slide 4 of Lecture
4 to go up and down the binary tree from any node A[i]!
(c) In some applications, we need to maintain several priority queues, and support an
additional operation: merge(P, Q) where P,Q are two priority queues. After this
merge, the queue Q is destroyed, and P contains the merged queue. In Slide 9, it is
stated that merge(P, Q) takes time O(n) where n is size(P)+size(Q). Explain
why this is true. For instance, why isn’t it O(n log n)?
(d) Suppose we begin with the array A[1..10] whose entries are the 10 digits
1, 7, 3, 2, 0, 5, 0, 8, 0, 7. (1)
[Of course, they come from √
3.] Note that binary heaps can have duplicate keys.
Do a hand simulation to convert this array into a binary heap. You MUST use
the O(n) algorithm of Slide 5.
HINT: To show the intermediate work, it is sufficient to show what the binary
tree looks like after processing an entire level.
(e) Slide 10 of Lecture 4 gives an outline of how to implementing priority queues using
a 2-3 tree.
PLEASE MAKE SURE THAT YOU FULLY UNDERSTAND THE OUTLINE!
Give the pseudo-code for computing merge(P,Q) under the 2-3 tree representation.
What is the time complexity?
Q 2. (4+4+4 Points) Split Simulation for 2-3 Tree
Consider the 2-3 tree in Figure 2 (we only show keys in leaves, guides are implicit).
Please perform the split operation at the key 8, resulting in two 2-3 trees: one tree
Figure 2: A 2-3 tree of size 16
has all the keys ≤ 8 and the other has all the keys > 8.
(a) Draw the intermediate result of split(8), which is an ordered list of 2-3 trees
before merging.
(b) Indicate how in what order these trees must be merged in pairs.
(c) Draw the final two trees that result from these merges.
Q 3. (20 Points) Recursive Rank Method for Java class Tree23
In hw2 we gave a pseudo-code for compute the rank function rank(T, x) where T is an
2-3 tree where each internal node is augmented with a count variable. In this question,
we revisit this problem but in a Java-specific setting (no longer pseudo-code). Assume
the Java class Tree23 as in hw3, but augmented with the count variable. Please write
a Java method for the Tree23 class with this header
2
int rank(String x);
Moreover, your algorithm must be recursive and has the correct Java syntax.
HINT: make rank(x) call a recursive method which you may also call rank(...)
(using overloading). If I insert your code into my class Tree23, it should work perfectly
(why not test it yourself?).
Q 4. (30 Points) Recursive Insertion Method for Java class Tree23
Give the pseudo-code for a recursive insertion algorithm for our class Tree23. For
recursion, we use the standard trick trick of writing two (overloaded) insert methods
with these headers:
boolean insert(Item x);
//return true iff insertion succeeded
int insert(Item x, InternalNode u, int h);
//return c in [0..4] where c=0 means failed;
//else c is the new degree of u.
//You must use recursion here.
HINT: We REALLY prefer pseudo-code over Java code! Why? Because pseudocode
is better for “human consumption” and able to accomodate some ambiguity
that humans can overcome. Computer are (will never) be smart enough for this.
Nevertheless, you need enough specificity (e.g., referring to class members, etc) so that
any one familiar with Tree23 can implement it correctly. The order of assignments,
loop structure, etc, may be important details to provide.
To help you along, we provide you with the pseudo-code for the first insert method.
Useful Notation: [0..d] is the set of integers from 0 to d, and [0..d) is the set of
integers from 0 to d-1.
int insert( Item x) //method of Tree23 class
int c = insert(x, root, ht); //calls the recursive insert method!
if (c == 0) return false;
if (c == 4)
--Create two new InternalNodes, newChild and newRoot;
--Move the last 2 children of (old) root into newChild;
//Also nullify the last 2 children of the (old) root afterwards
--Make the (old) root and newChild the 2 children of newRoot
--Reset the root to be newRoot: root=newRoot
--Increment the tree height: ht++
--Update the guides of these 3 nodes
return true
Q 5. (20 Points) Implementing the augmented Tree23 class
We want to implement an augmented 2-3 tree class in which each internal node u has a
member u.count of type int, which records the number of leaves in the subtree at u.
Describe all the changes in the file Tree23.java from hw3 that are needed to achieve
this.
NOTE: Although this is Java-specific, you can describe your modifications in pseudocode
(but with enough specificity that someone can act upon your pseudo-code). E.g.,
you may refer to the members of the Java classes and some of its standard methods.
3
Q 6. (10 Points) Topological Sort
Consider the DAG in Figure 3. Please give the canonical topological sort of this
Figure 3: DAG on the vertex set A, B ,..., G, H.
DAG.
EXPLANATION: In general, topological sorts are not unique. But suppose the
nodes are totally ordered. E.g., if the nodes are integers 1,2 ,..., n or they are
alphabetic a,b,c ,..., z, then there is an obvious ordering of the nodes. Whenever
your algorithm has a choice about which node to output, you must output the one
that is the least in this node ordering. This results in a unique topological sort that
we call “canonical”.
Q 7. (25 Points) The “Full” DFS Algorithm
Consider the DFS algorithm described in Slide 7 of Lecture 6. We want you to simulate
the DFS algorithm on the graph G7 in Figure 4 (it is taken from Slide 7). The output
Figure 4: Graph G7 on vertices a,b ,..., f,g
of your simulation on any graph G should show the following information:
(i) The forest of DFS Trees T1, T2, . . ..
(ii) A Classification of all the non-tree edges of G into one of these: (a) backward
edge, (b) forward edge, (c) cross edge, and (d) forest edge.
(iii) At every node u, a pair of integers d[u]/f[u] representing discovery time and
finish time.
Such an output is illustrated in Slide 8 of Lecture 6. NOTE: Professor Shoup regards
both (c) and (d) as “cross edges”. So our classification is finer. Just as in the case
of the canonical topological sort of a graph, there is also a canonical DFS classifi-
cation determined by a total ordering of the nodes. In G7, it is obviously a