• Have your name, UF ID, and discussion session number as comments at the top of your code.
• ONLY SOFT copy is REQUIRED.
• Jar all the files directly WITHOUT the dataStructures folder.
• For coding problems, put the complexity analysis and other non-coding parts of THIS question (if it has) in comments at the beginning of your code.
• For pen-paper questions, we only accept the following format file: Plain TEXT, PDF and DOC. Plain TEXT format is preferred. Name it as Qx.txt, where x is the sequence number of this question. For example, if Question 1 is a pen-paper question, put your solution to the file "Q1.txt"
• Grading rules of coding problems are available.
• Please download and check your jar file after your submission. Make sure the submission is correct.

public static double greedyKnapsack012(double[] p, double[] w, 
					double c, int[] x )

public static double greedyKnapsack01N(double[] p, double[] w, 
					double c, int[] x )

 public static void main(String [] args)
   {
      double [] p = {0, 16, 3, 5, 4, 7};
      double [] w = {0, 2, 2, 6, 5, 4};
      int [] x = new int [6];
      int n = 5;
      double c = 10;
      System.out.print("Greedy value is "); //Should print 34.0
      System.out.println(greedyKnapsack012(p, w, c, x));
      System.out.print("x vector is ");
      for (int i = 1; i <= n; i++)
         System.out.print(x[i] + "  ");	//Should print 2 1 0 0 1
      
      x = new int [6]; 
      System.out.print("Greedy value is "); //Should print 36.533
      System.out.println(greedyKnapsack01N(p, w, c, x));
      System.out.print("x vector is ");
      for (int i = 1; i <= n; i++)
         System.out.print(x[i] + "  ");	//Should print 5 0 0 0 0
   }

package dataStructures;

public class EightPuzzle {	
	
	Node startingNode;
	Node finish = new Node(new int[] {1,2,3,4,5,6,7,8,0}, null);
	
	//DATA MEMBERS GO HERE
	
	public EightPuzzle(int[] startPosition) {
		
		startingNode = new Node(startPosition, null);
				
		//YOUR CODE HERE
	}
	
	public void solvePuzzle() {
		
		//YOUR CODE HERE

	}

	//HELPER METHODS HERE
	
	public static void main(String[] args) {
		
		EightPuzzle eightPuzzle = 
			new EightPuzzle(new int[] {1,6,3,8,5,4,0,2,7});
		eightPuzzle.solvePuzzle();
		
	}
	
}


class Node {
			
	static int NINE = 9;	
	
	private int[] state; //holds the state array, 
				//0 is top left, 1 one to the right and so on

	Node previousNode; //holds a pointer to the previous node, 
				//to recreate the solution path
	
	Node(int[] state, Node prev) {
		this.state = state;
		previousNode = prev;
	}
	
	/* returns an integer that will be used as a key for this state
	  this will be used for the Hashtable
	  or AVLtree holding the visited states
	  in effect this is a basic hash function */
	int key() {
		int key = 0;
		for (int i = 0; i < NINE; i++) {
			key += state[i] * Math.pow(10, i);
		}
		
		return key;
	}
	
	//returns the position of 0 - the empty tile
	private int emptySpot() {
		for (int i = 0; i < NINE; i++ )
			if (state[i] == 0) return i;
		return -1;
	}
	
	//swaps the two positions in the state array, 
	//and returns the resulting Node
	private Node swap(int pos1, int pos2) {
		int[] array = new int[NINE];
		for (int i = 0; i < NINE; i++) {
			if (i == pos1) array[i] = state[pos2];
			else if (i == pos2) array[i] = state[pos1];
			else array[i] = state[i];
		}
		return new Node(array, this);
	}
	
	//returns the node after moving in the given direction
	//0 is up, 1 is right, 2 is down, 3 is left
	//the directions are the movement of the empty spot, not the tiles!
	Node move(int direction) {
		int emptySpot = emptySpot();
		if (direction == 0) {
			if (emptySpot < 3) return this;
			else return swap(emptySpot, emptySpot - 3);
		}
		else if (direction == 1) {
			if (emptySpot % 3 == 2) return this;
			else return swap(emptySpot, emptySpot + 1);
		}
		else if (direction == 2) {
			if (emptySpot > 5) return this;
			else return swap(emptySpot, emptySpot + 3);
		}
		else if (direction == 3) {
			if (emptySpot % 3 == 0) return this;
			else return swap(emptySpot, emptySpot - 1);
		}
	}
	
	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("--------\n");
		sb.append("| "+ state[0] + " " + state[1] + " " 
				+ state[2] + "|\n");
		sb.append("| "+ state[3] + " " + state[4] + " " 
				+ state[5] + "|\n");
		sb.append("| "+ state[6] + " " + state[7] + " " 
				+ state[8] + "|\n");
		sb.append("--------\n");
		return sb.toString();
	}
}