首页 >
> 详细

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

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-21:00
- 微信：codinghelp

- 代写 Lab 2: Threads 2022-05-10
- 辅导assessment 1. Present Your Client ... 2022-05-10
- 5Cce2sas辅导、Python，Java程序辅导 2022-05-10
- 代写brae Webb编程 2022-05-09
- 辅导csci 3110 Assignment 1 2022-05-09
- Mth2222 Assignment 2代写 2022-05-09
- Cse3bdc Assignment 2022辅导 2022-05-08
- 辅导cis 468、辅导java，Python编程 2022-05-08
- Comp Sci 4094/4194/7094 Assignment 3 D... 2022-05-07
- Cs 178: Machine Learning & Data Mining... 2022-05-07
- Data7703 Assignment 4 2022-05-07
- 讲解assignment 2: Databases 2022-04-25
- 辅导ait681 Static Analysis 2022-04-25
- Cse121 & Cse121l 编程辅导、辅导c++程序语言 2022-04-25
- 辅导iti1120 Bject-Oriented Programming 2022-04-25
- Cmt304语言辅导、辅导c++，Python编程 2022-04-25
- 辅导comp/Engn4528 Computer Vision 2022-04-24
- 辅导fin 2200 Bloomberg Investment Proj... 2022-04-24
- 辅导bism 7255 Uml Assignment 2022-04-23
- 讲解comp202 Programming Assignment 2022-04-23