Your answers for this assignment may be handwritten or typed. They are due Thursday, July 24, at the beginning of class.
Any partial answers are acceptable and will be judged according to your background. Be sure to describe in comments exactly which parts your code is to do. If you know of problems with your code, be sure to describe those too as well (but succinctly) as you can. It is far better to know what's wrong with your work than to claim that it is correct.
Please format and adequately comment your code. What we don't understand will be graded accordingly.
In this problem you will write a program to generate the following picture, called a Sierpinski gasket.
The provided code (``Sierpinski.java'') creates the window. It also provides a function that you will find useful that draws a triangle into the window.
public static void drawTriangle(double[] x, double[] y, double[] z) {
// drawing a triangle between x, y, and z
}
This function accepts three parameters, each representing a single
point. A point is an array of two doubles, the x-coordinate
followed by the y-coordinate. Both should be between 0 and 1. (The
point (0, 0) is the upper left-hand corner of the window.)
The provided code calls a function named drawGasket. The function is described as follows.
public static void drawGasket(int depth, double[] a, double[] b,
double[] c) {
// Your code here...
}
The parameters a, b, and c give the intended
corners of the gasket, and depth tells how many sizes of
triangles the function should draw. The function should not draw the
gasket's triangular boundary.
Your job in this problem is to complete this function. It should work for any valid parameters.
Give an example on which Greedy-Set-Cover will necessarily not perform optimally, where S has at most seven elements. (A bad answer is S = { 0,1,2,3 } and C = { {0,1}, {1,2}, {0,3} }. Although it is possible that the algorithm may choose {0,1} first and so choose all of C as the cover, the algorithm is ambiguous and may choose {1,2} first and so achieve the optimal solution.)
You are a thief who has just broken into a bulk-spice shop. This spice shop carries n spices, the ith spice being worth p[i] dollars per liter on the black market. The store has only a[i] liters of spice i, and your bag holds C liters.
Devise an efficient algorithm for maximizing the worth of the spices placed in your bag, write down the pseudocode, prove it is correct, and give the running time (using big-O notation) in terms of n.