HW#3 --- last modified January 01 1970 00:00:00..
Solution set.
This homework has been extended from Oct. 25
to Oct. 28.
However, people who want to be graded based on what they had on the Oct. 25
will receive two extra bonus points after curving.
Due date: Oct 28
Files to be submitted:
problems.doc
sortmerge.java
Purpose: To gain familiarity with how DB
catalogs work, and
to gain experience with query processing techniques.
Specification:
Be aware that the current limit on submitted file size
is 1.5MB.
Do the following problems out of E&R 17.14, 18.13, 18.14, 18.22
and submit them in problems.doc. Write a java program to implement
the sort merge algorithm of Figure 18.2. Your algorithm will be tested
from the command-line with a line like:
java sortmerge num_blocks_buffer block_size_byte in_file out_file
Ex:
java sortmerge 5 2048 myfile.txt sorted.txt
To determine the number size of the file so you can figure out the number
of blocks use the length() methods in the java class File. Note the
block size above does not neccessarily correspond to the block size actually
used for the file. You can assume that the test file consists of a sequence of
strings of A's and B's, each string being up to 80 characters long with a
`\r\n' between strings. All strings (which are our records) in a given file can
be assumed to be of the same length. You can also assume the block size is
bigger than the length of these strings/records. Be forwarned,
if your code attempts to read in the whole file into memory, rather than restricting yourself to num_blocks*block_size_bytes bytes
you will receive 0 for this part of the homework.
To keep things simple I will choose test parameters to avoid spanned
records; howver, if your code handles spanned records correctly then you
can receive one bonus point to your grade after curving. Please indicate
at the start of your code if you want the grader to test on spanned inputs.
Below is some code that can be used to generate random rows:
// RandomStrings.java -- program used to generate random string data for CS157b Hw3 Problem 5.
import java.util.*;
import java.io.*;
/**
This class consists of a bunch of public static methods used to generate
random row data for the CS157B HW3 Problem 5.
Typically one would run this program from the command line with a line like:
java RandomStrings string.DAT 80 1000
Here string.DAT is the file to write the random data to, 80 is the number of characters
of each records, and 1000 is the number of rows of random data to generate.
@author Chris Pollett
@version 1.0.2002
*/
public class RandomStrings
{
/**
Creates numRows rows of random data each row of length stringLength and save it in a file named
by String fileName.
@param fileName -- filename to store random row data in
@param stringLength -- length of a row (not including end of line chars)
@param numRows -- number of rows of data to create
*/
public static void createData(String fileName, int stringLength, int numRows)
{
try
{
PrintStream out = new PrintStream(
new FileOutputStream(fileName));
for(int i = 0; i < numRows; i++)
{
StringBuffer bRow = new StringBuffer(BUFLEN);
createRow(stringLength, bRow);
out.println(bRow.toString());
}
out.close();
}
catch(IOException ie)
{
ie.printStackTrace();
}
}
/**
Creates one row of random data given the parameters supplied.
@param stringLength -- length of a row
@param buf -- presumed empty StringBuffer in which to append random row.
*/
public static void createRow (int stringLength, StringBuffer buf)
{
for(int i=0; i < stringLength; i++)
{
int preDigit = (int)(Math.random()*2)+65;
String digit = ""+(char)preDigit;
buf.append(digit);
}
}
/**
Calls createData with the command line arguments to generate the random
data
@param args - array of command line arguments
*/
public static void main (String [] args)
{
if(args.length < 3)
{
System.out.println("To use:");
System.out.println("java RandomStrings fileName stringLength numRows");
System.out.println("where fileName is the file you'd like data written to");
System.out.println("stringLength is the length of each record");
System.out.println("and numRows is how many rows you'd like generated.");
}
else
createData(args[0], Integer.parseInt(args[1]), Integer.parseInt(args[2]));
}
public static final int BUFLEN = 80; //presumed max size of a row
}
Point Breakdown
Departmental coding guidelines for Java followed | 1pt |
1.5 points for each of the book problems |
6pts |
Program uses command line parameters correctly | 1pt |
Sort phase works correctly | 1pt |
Merge phase works correctly | 1pt |
Total | 10pts |
|