CS 301代写、Java设计编程代写

日期：2021-10-23 08:22

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<b<· · · <

g. HOWEVER, for this exercise, we tell you a specific node to begin the DFS: please

begin DFS(G7) at the node d.

4

Q 8. (15+10 Points) Coin Gathering Problem

Refer to Lecture 7 (Slide 6). The problem is to gather the maximum number of coins

in a single path through graph G. If G is a DAG, this was treated in Lecture 5 (Slide

25).

(a) Please do a hand simulation of the Coin Gathering algorithm on the graph G8 of

Figure 5. You must show steps of your simulation. Be sure to finally state the

Figure 5: Graph G8 with number of coins at each node

maximum number of coins that can be gathered, and indicate the path through

G8.

(b) The “single path” in the coin gathering problem need not be a simple path. Explain

why we cannot insist on simple paths. Support your reasoning by giving an explicit

counter-example graph. HINT: There is a counter example with 5 nodes.

Q 9. (20+8+7 Points) Dijkstra’s Algorithm

Please simulate Dijkstra’s algorithm on the graph in Figure 6. By our usual convention,

Figure 6: Graph on vertices 1,2,..,7 for Dijkstra simulation

the source is the smallest numbered node, i.e., node 1. Whenever you have a choice

to pick the number minimum node, pick the smallest numbered node. The algorithm

will compute two arrays: d[1..7] and π[1..7]. Answer these questions:

(a) Show the simulation to compute d[1..7] and π[1..7]. At each step, these two

arrays get updated.

(b) Show the final arrays d[1..7] and π[1..7].

(c) Illustrate how you find the shortest path from node 1 to node 6 using these arrays.

(d) Use π-array to draw shortest path tree (rooted at node 1)

5