CSC 365 F I N A L E X A
M NAME:___________________
(15
Points) 1.
You are to
follow the balanced multi-way merge sort algorithm for sorting an external
input tape. Perform a 4-way merge
sort (i.e. buffer size=4). Show the
content of each tape after each pass as promoted below.
Input Tape
contains: 12 30 10 20
5 34 22 14 43
22 18 31 9 32
22 19 11 31 41
34 23 13.
The
initial pass through the input tape would grab 4 records at a time (buffer
size), sort them and store them in tapes 1 through 4 forming blocks of size 4
in our tapes. The sorted blocks from Tapes 1, 2, 3, and 4 are then merged and
form new blocks in other tapes. Final answer should end up in the Output Tape.
After
1st Pass
Tape 1:
Tape 2:
Tape 3:
Tape 4:
After
2nd Pass
Tape 5:
Tape 6:
Tape 7:
Tape 8:
After
3rd Pass
Output
Tape:
(10
Points) 2.
Write a method intended for the B-tree class that counts the
number of nodes (NOT keys) in a B-tree and returns the count. This method returns zero if the node
reference sent to is null; otherwise, it counts the node itself as one and then
recursively counts its children, returning the sum of those counts. A copy of Btree.java is attached.
(10 Pts.) 3.
Consider
the following Consider the following
Supplier table: Btree index file for Supplier:
Supplier s14/1
Rec#
Snum Sname City
1
s14 IBM BOS
2
s12 SUNW BOS
3
s23 CPQ NY
4
s24 DELL ST
s12/2 s23/3
5
s15 MSFT ST
6
s20 CSCO LA
7
s42 JNPR LA
8
s10 HWP NY s10/8 s13/9 s15/5 ??/?? ??/??
??/??
9
s13 SCTC LA
Assume
that our index file depicted on the right is an Order-3 Btree on Snum
with key/Rec# entries.
a. Replace the ??/?? entries in the
Btree Index above with the key/Rec#s that were left out.
b. Append (s45,QCOM,SF) to the end of the Supplier table and add
the appropriate entry into its index file above.
(10
Points) 4.
What layer
of the Relational Database Architecture interacts directly with the end-user
(External, Conceptual, or Internal)? How does an end-user perceive the
database, through what tools or interfaces?
(15
Points) 5.
Assume the
existence of the following tables:
Part(p#, description, color,
weight, unit price) Shipment(p#, date, qty)
a. Show
some sample values for each table:
p# description color
weight unit price p# date qty
b. What is the following SQL
statement trying to accomplish? Complete
the sentence: This query
retrieves _________ for _______ that
________________________________.
SELECT description
FROM Part,Shipment
WHERE Shipment.p# = Part.p#
AND qty > 100;
c. Based
on the sample values you entered for each table above, what will be the answer:
(20 Points) 6.
Consider
the following weighted graph, assume that the circle at the end of each edge
identifies that node as the to node.
a) What is the shortest path from A to F?
b) Lets assume the numbers on the
edges are their capacities. Solve the MAX-flow problem from node A to node
F. Draw Gf and Gr and show your work on the next
page.
(20
Points) 7.
Consider
the following findSP method from graph.java:
void findsp (Vector cp,Vector sp,int n, int
destination) {
if (!g_[n].visited_) {
g_[n].visited_=true;
Integer vecValue=new Integer(n);
cp.add(vecValue);
if (n == destination) {
if (cp.size() < sp.size() ||
sp.isEmpty()) {
sp.clear();
sp.addAll(cp);
}
}
else {
adjacent neighbor=g_[n].first_;
while (neighbor!=null) {
findsp(cp,sp,neighbor.adj_,destination);
neighbor = neighbor.next_;
}
}
g_[n].visited_=false;
cp.remove(vecValue); //remove this edge
before returning
}
}
We are
interested in finding all paths from a given source to a destination. What would you change in the above findSP
method in order to turn it into a findAllPaths method; this
method needs to store all paths from source to destination in some data
structure of your choice, for example, another Vector.