15-121 SPRING 2010 [CORTINA]
HOMEWORK 9 - due Tuesday, April 20
WRITTEN PROBLEMS (10 pts)
- (2 pts) Consider the max-heap below:
96
/ \
47 61
/ \ / \
32 13 50 36
/ \
19 28
-
Using the max-heap above, add the value 74 and restore the heap using the
algorithm discussed in lecture.
-
Why are binary search trees not usually stored using arrays? Explain.
-
Using the original heap, trace the Heap Sort algorithm given in
class.
Show the contents of the array used to store the heap
after the element in index 0 (the root of the heap) is moved to its
correct position and the remaining heap is fixed. Use a vertical bar to
separate the elements that still belong to the heap from those that
don't belong to the heap (i.e. the sorted part of the array).
The first step is shown for you below:
Original heap:
96 47 61 32 13 50 36 19 28
96
/ \
47 61
/ \ / \
32 13 50 36
/ \
19 28
After first pass:
61 47 50 32 13 28 36 19 | 96
61
/ \
47 50
/ \ / \
32 13 28 36
/
19
- (1 pt)
Write the insert and remove
methods for a minheap recursively.
(You can use the code from your Heap lab to test your solution!)
- (1 pt) Consider the following 2-3-4 tree:
- Draw an equivalent red-black tree for the 2-3-4 tree above.
- Using the 2-3-4 tree above, insert the value 9 into the tree and
redraw the resulting 2-3-4 tree.
- (1.5 pts)
Consider the following alternate implementation of Merge Sort that
recursively sorts
the array table from index a to b, where
a ≤ b:
public static <T extends Comparable<T>> void sort(T[] table, int a, int b)
{
if (b - a > 0) {
sort(table, a, (a+b)/2);
sort(table, (a+b)/2 + 1, b);
merge(table, a, b);
}
}
The merge method copies the elements of table from
indices a to b (inclusive) into a new array and then
merges the two halves of the new array back into table.
- Modify the method above so that it calls the merge method
only if the array is not sorted after the two recursive calls. You should
be able to determine this in constant time.
- Based on your new implementation, determine the best case runtime
complexity of Merge Sort using Big-O notation assuming the array has n
elements in it overall.
-
Is Merge Sort stable? Explain.
- (1.5 pts)
Consider the following implementation of Quick Sort that
recursively sorts
the array table from index a to b, where
a ≤ b:
public static <T extends Comparable<T>> void sort(T[] table, int a, int b)
{
if (b - a > 0) {
T pivot = table[a];
int pivotPosition = partition(table, a, b, pivot);
sort(table, a, pivotPosition-1);
sort(table, pivotPosition+1, b);
}
}
The partition method rearranges the array so
all the elements less than the pivot come first (not necessarily sorted),
followed by the pivot, followed by the elements that are greater than or
equal to the pivot (not necessarily sorted).
-
Modify the method above so the pivot chosen is never the minimum or
maximum of the array table
in the given range from a to b assuming that there
are at least 3 elements being sorted.
You should be able to do this in constant time.
-
If we always choose table[a] as the pivot, what is the worst-case runtime
complexity of Quick Sort in big-O notation if the array has n elements
overall? Explain.
- Is Quick Sort stable? Explain.
-
(2 pts)
Consider the following sorting algorithm called Radix Sort. This sort is
sometimes used to sort information based on several keys. For example, if we
had a set of dates, we might to sort by year, then by month, then by day.
In the example below, the sort method is sorting n strings. We will assume all
strings are the same length (d).
public static void sort(String[] table) {
int n = table.length; // number of strings in table
int d = table[0].length(); // length of first (or any) string
ArrayList[] list = new ArrayList[26];
for (int i = d-1; i >= 0; i--) {
for (int k = 0; k < 26; k++) {
list[k] = new ArrayList();
}
for (int j = 0; j < n; j++) {
char ch = table[j].charAt(i);
list[ch-'A'].add(table[j]);
}
int m = 0;
for (int k = 0; k < 26; k++) {
for (int j = 0; j < list[k].size(); j++) {
table[m] = (String)list[k].get(j);
m++;
}
}
// For part a:
for (String s: table)
System.out.println(s);
System.out.println();
}
}
-
What is the output of the method above for the following array of strings?
{"WISK","COKE","TWIX","TIDE","LAYS","DOVE","RAID","ZEST","NIKE","OREO",
"RAGU","AJAX","DAWN","SURF","GAIN","CHEX","DOLE","OLAY","LUVS"}
- What is the worst-case
runtime complexity of Radix Sort as implemented above in terms
of n and d? Explain.
- Which sort is Radix Sort most like: selection sort, quick sort, merge sort
or bucket sort? Explain.
- Does Radix Sort sort in place? Explain.
- (1 pt)
16 values are being sorted using the following sorting algorithms:
Insertion Sort, Selection Sort, Quick Sort and Merge Sort. For each sort,
two snapshots are given below. Each snapshot shows the order of the
elements at a given point in the algorithm.
The first snapshot is taken before the second snapshot.
Determine which sort is being used for each algorithm.
(HINT: Each sort is shown exactly once.)
Sorting Algorithm #1:
Sorting Algorithm #2:
Sorting Algorithm #3:
Sorting Algorithm #4:
PROGRAMMING PROJECT (10 points)
An grayscale image consists of pixels with intensities between 0 and 255 (inclusive). To
store an image, we can use a compressed version using a quadtree. A quadtree is a tree where
each node is either a leaf or a nonleaf with 4 children.
Assume that the image region is square and the number of pixels across (and down) is a power
of 2, as shown below, where 0,1,2,3 are pixel intensities:
If the image does not consist of pixels of the same intensity, then the image is divided
recursively into four quadrants (which are also squares) until each square consists of a
single intensity, as shown by the sequence below:
Dividing the image into four quadrants:
Dividing two quadrants again:
Dividing three quadrants again (the final division):
The image can now be stored as a quadtree where the root represents the whole image. If the
image is split into 4, the node stores a -1 and has four children representing the image's
four quadrants (in the order NW, NE, SW, SE). If the quadrant consists of 1 color only, then
the node is a leaf and stores the intensity of the quadrant. This process is repeated for
each quadrant if necessary. Based on this information, the
image above would be stored as a quadtree as follows:
The quadtree can then be stored in a file, one integer per line, by performing a preorder
traversal of the tree:
-1
1
-1
0
3
-1
0
2
0
0
-1
3
0
0
1
0
-1
0
-1
0
0
1
0
2
0
Note that the quadtree file above requires only 25 integers whereas the original image would
have required 64 integers (since it is an 8 X 8 image).
Assignment
Download the QuadTrees.zip project file. Your assignment is to
complete a QuadTree class to implement a quadtree that represents a 256 X 256 image.
Your QuadTree class requires an inner class to represent a node of the quadtree.
Each node consists of an intensity value and references to four children. The intensity value
can be an integer between 0 and 255 (if the node is a leaf) or -1 (if the node is a nonleaf).
Your inner class should have a constructor that creates a node with no children and
an intensity value of -1. These can be changed once the node is inserted into the tree.
Complete the constructor for the QuadTree class that has one parameter, the name of
a text file containing the preorder traversal of the quadtree for an image, like the example
shown above. The file will have one integer per line, and each integer will be between
-1 and 255, inclusive. You may assume that the input file is the preorder traversal for a
valid quadtree. You should read the data from the file and build a quadtree based on the
data. (If the file cannot be opened, just output an error message and exit the program.)
Complete the method getNumNodes that returns the number of nodes in the quadtree.
Do this as efficiently as possible.
Complete the method getNumLeaves that returns the number of leaves in the quadtree.
Do this as efficiently as possible.
Complete the method getImageArray that creates an array of size 256 X 256 and then
traverses the quadtree, filling in each cell of the array with its intensity value.
Return this array when you're done. Note that
as you traverse the quadtree, whenever you hit a leaf, you may need to fill in more than one
array cell with the leaf's intensity value. (Think recursively here.)
Once you complete the QuadTree class, run the QuadTreeDisplayer
provided for you to load in
a sample quadtree file (see below) and make sure you can see the original image. This
application passes the quadtree file name to your constructor so you can create the tree,
then it calls your getImageArray method to get the image array based on your
quadtree and displays the image in a window. Keep testing until you have your
QuadTree class working correctly.
Finally, write another class named QuadTreeFileCreator
that reads in the name of a text file containing the data for an uncompressed image
of size 256 X 256 (one
integer per line), and create a new text file containing the data needed for the
quadtree representation for the image. If you write this class correctly, you can use the
generated quadtree data file with the QuadTreeDisplayer above to view the image.
Note: This can be done without creating a quadtree. Hint: Think recursively.
See below for a few sample image files that you can convert to quadtree files.
[This final step is worth 2 points of the 10 points.]
Input File Format
The quadtree files consist of one integer per line, representing the preorder traversal of a
quadtree that represents a 256 X 256 grayscale image consisting of pixel intensities between
0 and 255 (inclusive) for leaf nodes and -1 values for nonleaf nodes. You may assume that the
quadtree files are valid.
Here are four sample quadtree files you can use for testing purposes - RIGHT CLICK TO SAVE:
stopsignQT.txt
earthQT.txt
inclineQT.txt
walkingtotheskyQT.txt
The image files consist of one integer per line, representing the raw (uncompressed) data for
the image. The integers are in row major order, meaning that the image is scanned row
by row. So the first 256 integers represent the first row of the image. The next 256 integers
represent the 2nd row of the image, etc. The integers are always in the range 0 to 255
(inclusive). You may assume for this assignment that the image files are valid (although it's
easy to check for this if you wish).
Here are four sample image files you can use for testing purposes (these are 3 different
images than the ones given in the quadtree files above) - RIGHT CLICK TO SAVE:
smileyface.txt
i376.txt
mascot.txt
ghc.txt
Documentation & Style
Be sure to document all of the code that you write to explain what you are
doing. Use appropriate Java style (indentation, variable names, etc.) to make
your code as readable as possible.
Hand-In Instructions & Late Submissions
Your submitted zip file should include the complete Java program.
See the course website for instructions on how to
hand in your program and the policy for late
submissions.
Thanks to Rolf Lakaemper for the inspiration and image displayer for this assignment.