----------------------- Section I : Definitions ----------------------- * OO Programming * Encapsulation * Polymorphism * Iteration * Recursion * Array * Method * Accessor * Modifier * Modularity * equals() Method * toString() Method * Scope * Variable shadowing * Class * Object * Inheritance * Dynamic Binding * Polymorphism * Method Overloading * Method Overriding * Dynamic Data Structure * Static Data structure * Static Variable * Instance Variable * Instantiation * Reference * Pass by value * Superclass * Constructor * Constructor Chaining * Exception * Node * Linked List * Stack * Queue * Binary Tree * Binary Search Tree * Preorder Traversal * Postorder Traversal * Inorder Traversal * Complete Binary Tree * Full Binary Tree * Balanced Binary Tree * Heap * Priority Queue * Hashtable * External Chaining * Open Addressing (linear or quadratic probing) * Coalesced Chaining * File IO * GUI * Component * Container * Layout Manager * Event * Event Listener * Event Registration * Semantic Event * Low-level Event * MVC * UIDelegate * Graph * Vertex * Edge * Degree * Order * Adjacency List * Adjacenct Matrix * DFS * BFS ------------------------------- Section II: Concept application ------------------------------- - Data Types For all of the following, determine a) if the code fragement is legal, and b) the output if it is legal * System.out.println("hello"+2+3); * System.out.println(4+5+"world"); * int x = 2.5 / 0.5; System.out.println(x); * char c= (char)('2' + 5); System.out.println(c); * int x = '4' / '5'; System.out.println(x); * double q = 99 / 42; System.out.println(q); - Polymorphism Assume that you have the following inhertiance structure: o the interface UnderwaterType has the method submerge() o Animal is an abstract class o Cat extends Animal o Dog extends Animal o Fish extends Animal and implements UnderwaterType o Flounder extends Fish Which of the following are legal? -> Animal a; -> UnderWaterType uwt; -> Cat c; -> Dog d; -> Animal a=new Animal(); -> Animal a=new Cat(); -> Dog d=new Fish(); -> Flounder f=new Flounder(); -> Fish f=new Flounder(); -> UnderwaterType uwt=new Flounder(); -> Animal a=new Flounder(); -> Flounder f=new Flounder(); f.submerge(); -> Cat c=new Cat(); c.submerge(); -> Animal a=new Fish(); a.submerge(); -> Flounder f=new UnderwaterType(); -> UnderwaterType uwt=new UnderWaterType(); - BSTs Given this BST, perform each of the following operations ON THE ORIGINAL TREE: 18 / \ 13 89 / / \ 10 80 91 / \ \ \ 1 11 85 93 -> add 0 to the ORIGINAL TREE -> add 2 to the ORIGINAL TREE -> add 79 " " " " -> add 14 " " " " (For the balance of the problems, we'll assume you've read the instruction 'ON THE ORIGINAL TREE', noted above) -> add 90 -> add 94 -> remove 18, choosing the left-most right child -> remove 18, choosing the right-most left child -> remove 10 -> remove 1 -> remove 13 -> remove 89 -> do a preorder traversal -> do an inorder traversal -> do a postorder traversal -> do a reverse order traversal -> do a level order traversal -> list what nodes would be visited (in the right order) while looking for 85 -> list what nodes would be visited (in the right order) while looking for 95 -> list what nodes would be visited (in the right order) while looking for 1 - Heaps Given this min-heap: 3 / \ 19 10 / \ / 24 21 11 Do each of these operations ON THE ORIGINAL HEAP: SHOW ALL STEPS (for add and remove), as well as the result -> add 19 -> add 7 -> add 1 -> remove min 3 times -> write the heap in array format given the array {3,6,7,9,12,34,56,3,2} perform the BuildHeap operation on the array. Show all steps. - Hashtables Given the following key, value pairs (hashcode of the key is in parens): <"spork" (17), "PII"> <"twinkie" (76), "Celeron"> <"freezer" (93), "PIII"> <"phear" (11), "dual PIIIs"> <"segfault" (13), "AMD"> <"crumb" (25), "AMD"> <"toaster" (37), "PIII"> <"plate" (94), "PIII"> <"acme" (7), "4 Sun SPARCS"> -> add these key/value pairs to a hashtable of size 7 that uses external chaining -> add these key/value pairs to a hashtable of size 11 that uses linear probing -> what is the load factor in the last question? (the one with linear probing) -> add these key/value pairs to a hashtable of size 7 that has a cellar of size 5 - Graphs Given this graph: S----A------B------C---D-----T----U----V----W----X---Y----Z / \ / \ / \ \ E F H I J K L \ / \ / \ / / M------N------O---P-----G If you knew the entire layout of this graph, and had a program that would resolve which adjacency of a node to go to first by going to the one that comes earlier in the alphabet- which would you pick, a DFS or a BFS- if you were searching from S to G, and the search to complete quickly? Why? What path would your choice of search return? What path would the other search return? Now lets assume that we took the same graph, but changed the letters like this S----Q------H------J---P-----T----U----V----W----X---Y----Z / \ / \ / \ \ B D F I K M A \ / \ / \ / / C------E------L---N-----G What is the path for a DFS? How about for a BFS? Would changing these letters make you pick a different search to use for the fastest results? ----------------------- Section III: Debugging ----------------------- 1) A misguided Java programmer wrote the following code: public void DFTraversal(BinaryTreeNode btn) { Queue nodes = new Queue(); nodes.enqueu(btn); while(!nodes.empty()) { BinaryTreeNode current = (BinaryTreeNode) nodes.dequeue(); System.out.println(current); nodes.enqueue(current.getLeft()); nodes.enqueue(current.getRight()); } }//end of method The above code was supposed to print out a Depth First traversal of a binary tree. It doesn't. A) Explain why it doesn't work B) HOW would you correct the error? 2) A misguided Java Programmer wrote the following code. public class Node { public Object data = null; public SuperNode sNode = new SuperNode(); public Node() {} public Node(SuperNode sNode) { this.sNode = sNode; } } public class SuperNode extends Node { static int numNodes = 0; public SuperNode() {} public SuperNode(Object data) { this.data = data; numNodes++; } public static int getNumNodes() { return numNodes; } public Object getData() { return data; } } When ever the programmer tries to instantiate either class, the program crashes. A) Why does the program crash? B) Fix the problem 3) A misguided Java programmer wrote the following code: public void insert(Comparable data) { Node toAdd = new Node(data); Node temp = head; if((temp == null) || (temp.getData().compareTo(data) < 0)) { toAdd.setNext(temp); head = toAdd; } else { do { temp = temp.getNext(); }while((temp.getNext() != null) && (temp.getNext().compareTo(toAdd) >= 0)); temp.setNext(toAdd); } } The programmer expected the method to insert a node into an ordered linked list. A) Under what conditions does this fail? B) How can it be corrected? 4) Examine the following program: public class Node { // Assume this class is implemented correctly. } // Node public class Tree { private Node head; // Assume that the methods filled with "..." are implemented // correctly and free of errors. public void printTree() { ... } public void printTree (Node curr) { ... } public void insert (Node n) { ... } public void insert (Node curr, Node n) { ... } public static void main (String[] arg) { for (int i = 0; i < 100; i++) { int k = (int) (Math.random()*100) + 1; Node n = new Node (new Integer(k)); insert(n); } // endfor printTree(); } // main } // class When the program is compiled, the following error messages appear: Tree.java:54: Can't make static reference to method void insert(Node) in class Tree. insert(n); ^ Tree.java:56: Can't make static reference to method void printTree() in class Tree. printTree(); ^ 2 errors The line numbers point to the statements in the debug main. Describe, in detail, what the error messages mean. Furthermore, fix the code in the "main" method. ------------------- Section IV: Tracing ------------------- 1) Given the following code: public class Pastry { public Pastry() { System.out.println("I'm rolling in the dough"); } public void consumed() { System.out.println("I'm eight!"); } public String toString() { return "I'm so pale."; } public static void main(String[] args) { Pastry one = new Pastry(); Pastry two = new Doughnut(); Pastry three = new Muffin(); one.consumed(); two.consumed(); three.consumed(); } } public class Doughnut extends Pastry { public void Doughnut() { System.out.println("Doughnut go there!"); } public void consumed() { super.consumed(); System.out.println("Dough boy Dough boy!"); } } public class Muffin extends Pastry { public Muffin() { System.out.println("I'm such a cream puff."); System.out.println(toString()); } public void consumed() { System.out.println(super.toString()); System.out.println("I'm too sweet!"); } public String toString() { return "Yummie!"; } } What is the output when the main method in Pastry is run? 2) What is the output when the main method in the Driver class is called? public class Animal { String name = null; public Animal() { name = "Charlie"; } public void speak() { System.out.println(name.toString() + " speaks!"); } public void move(boolean fast) { if(fast) { System.out.println("zoomin."); } else { System.out.println("getting there."); } } } public class Reptile extends Animal { public Reptile(){} public Reptile(String name) { this.name = name; } public void move(double fast) { if(fast > 0) { System.out.println("racin"); } else { System.out.println("wandering."); } } public void molt() { System.out.println("eww!"); } } public class Snake extends Reptile { public Snake() { name = "Sir Hiss"; } public void speak() { System.out.println("Hiss"); super.speak(); } public void move(boolean fast) { if(fast) { System.out.println("slither"); } else { System.out.println("meander"); } } public void molt() { System.out.println("Gross!"); } } public class Driver { public static void main(String[] Args) { Animal[] a = {new Animal(), new Snake(), new Reptile()}; a[1].move(true); a[2].speak(); ((Reptile)a[2]).molt(); a[0].speak(); ((Animal) a[1]).speak(); ((Snake) a[1]).move(10d); ((Reptile) a[2]).speak(); ((Reptile) a[1]).move(false); ((Reptile)a[1]).molt(); } } 3) What is the output when the "main" method of the WidgetPlus class is executed? // ********************************** // ********** Widget class ********** // ********************************** public class Widget { private String strName = "Default Name"; private int iSize = 0; // ********** constructor ********** public Widget() { System.out.println ("A widget is created..."); } // constructor public Widget (String strName, int iSize) { this(); System.out.println ("I am great!"); this.strName = strName; this.iSize = iSize; } // constructor // ********** accessor methods ********** public String getName() { return (strName); } // getName public int getSize() { return (iSize); } // getSize // ********** toString method ********** public String toString() { return ("Name: " + strName + " Size: " + iSize); } // toString } // class // ************************************** // ********** WidgetPlus class ********** // ************************************** public class WidgetPlus extends Widget { private String strOwner = "Default Owner"; // ********** constructor ********** public WidgetPlus() { System.out.println ("Good Stuff!"); strOwner = "WidgetPlus Owner"; } // constructor public WidgetPlus (String strOwner, int iSize) { super (strOwner, iSize); System.out.println ("Cool Thing!"); } // constructor // ********** getName method ********** public String getName() { return ("Stars everywhere!"); } // getName // ********** toString method ********** public String toString() { return (super.toString() + "Owner: " + strOwner); } // toString // ********** main ********** public static void main (String[] args) { Widget w1 = new Widget(); Widget w2 = new Widget ("Joe Cool",20); WidgetPlus wp1 = new WidgetPlus(); WidgetPlus wp2 = new WidgetPlus ("Master",30); System.out.println (w2.getName()); System.out.println (wp2.getName()); } // main } // class 4) What is the output when the "main" method of the ExceptionTraceT class is executed? import java.io.*; public class ExceptionTraceT { private Integer[] myArray = new Integer[5]; public ExceptionTraceT() { int i = 0; try { System.out.println ("Where are you?"); for (i=0; i<= 5; i++) { myArray[i] = new Integer (i * 10); } // endfor System.out.println ("I am here..."); } catch (NullPointerException e1) { System.out.println ("OOPS! at " + i); myArray[3] = null; } catch (Exception e2) { System.out.println ("All is fair..."); } // endtrycatch System.out.println ("This line should not print!"); } // constructor public void start() { for (int i=0; i<= 5; i++) { try { int x = myArray[i].intValue() / (i % 3); System.out.println ("Still Tracing?"); if (i == 4) throw (new IOException()); } catch (ArithmeticException e1) { System.out.println ("AE is caught!"); } catch (ArrayIndexOutOfBoundsException e2) { System.out.println ("AIOOBE is caught!"); } catch (Exception e3) { System.out.println ("I am very useful!"); } // endtrycatch } // endfor } // start public static void main (String[] args) { ExceptionTraceT myETT = new ExceptionTraceT(); myETT.start(); } // main } // class 5) import java.io.*; public class Review5 { int times = 0; Object partner = null; public void You (int top, int bottom) { try { if (top > 0) top = (top / bottom); } catch(Exception e) { if(bottom == 0) { System.out.println("all"); } else { System.out.println("my"); } } finally { System.out.println("your"); } } public void Just () { int [] space = new int[4]; try { for (int i=0;i<=space.length;i++) space[i] = i; pizza(); } catch (IOException e) { System.out.println ("I like kangaroos"); } catch (ArrayIndexOutOfBoundsException e2) { System.out.println ("base"); } } public void dancer () { if (partner.equals(this)) System.out.println ("woot"); } public boolean Love () { try { times++; if (times == 1) { dancer(); times++; } else if (times == 2) { throw new Exception(); } } catch (NullPointerException e) { System.out.println ("are"); } catch (Exception e2) { System.out.println ("belong"); } return (true); } public void pizza () throws FileNotFoundException { throw new FileNotFoundException(); } public void CS1322() { try { pizza(); } catch (IOException e) { System.out.println ("to"); } catch (Exception e2) { System.out.println ("I like ice!"); } finally { System.out.println ("us"); } } public static void main(String Args[]) { Review5 me = new Review5(); me.You(10,0); me.Just(); me.Love(); me.Love(); me.CS1322(); } } 6) What is the result of running the main method of the class Review6? (You will be drawing a picture, as well as listing console output) import javax.swing.*; import java.awt.*; public class AlliAlliAppleseed extends JPanel { public AlliAlliAppleseed () { setLayout(new GridLayout(3,1)); add(new JButton ("Go On Date")); add(new JButton ("Stay Home")); add(new JButton ("Go Out with Friends")); talk(1); }//Allison public void talk(int WhatToSay) { switch (WhatToSay) { case 0: System.out.println ("Bye Bye Chris"); case 1: System.out.println ("Chris M is a stud"); case 2: System.out.println ("Chris is fun!"); default: System.out.println ("Head TAs are GREAT!"); }//switch }//talk }//AlliAlliAppleseed import javax.swing.*; import java.awt.*; public class Review6 { JFrame myFrame; Container cp; public Review6 () { myFrame = new JFrame("Extra Credit Test"); myFrame.setSize(500,500); cp = myFrame.getContentPane(); cp.setLayout (new BorderLayout ()); cp.add(new AlliAlliAppleseed(),BorderLayout.CENTER); }//Review6 () public static void main (String argv[]) { Review6 me = new Review6(); }//main }//class Review6 7) Draw the GUI Output of the code when the main method of Review7 is run: import javax.swing.*; import java.awt.*; public class Review7 { JFrame myFrame; public Review7() { myFrame = new JFrame ("Review Questions"); myFrame.setContentPane(makeMainPanel()); myFrame.setSize(500,500); myFrame.setVisible(true); }//Review7 public JPanel makeMainPanel () { JPanel toReturn = new JPanel(); toReturn.setLayout(new BorderLayout()); JButton But1 = new JButton ("I like Java"); But1.addActionListener (new ReviewListener()); JLabel Lab2 = new JLabel ("I like CS1322:"); JButton But3 = new JButton ("Stop the Lies"); But3.addActionListener(new ReviewListener()); toReturn.add(But1, BorderLayout.NORTH); toReturn.add(Lab2, BorderLayout.CENTER); toReturn.add(But3, BorderLayout.WEST); toReturn.add(eastSide(), BorderLayout.EAST); return (toReturn); }//makeMainPanel() public JPanel eastSide () { JPanel toReturn = new JPanel(); toReturn.setLayout(new FlowLayout()); JLabel lab = new JLabel("word it up"); JButton but = new JButton ("oh yeah!"); but.addActionListener(new ReviewListener()); toReturn.add(lab); toReturn.add(but); return (toReturn); }//eastSide public static void main (String argv[]) { Review7 me = new Review7(); }//main }//Review7 import java.awt.event.*; public class ReviewListener implements ActionListener { public void actionPerformed (ActionEvent e) { System.out.println ("In actionPerformed"); String ec = e.getActionCommand(); if (ec.equals("I like Java")) System.out.println ("It is true"); if (ec.equals("I like CS1322")) System.out.println ("It is not so true"); System.out.println ("I own CS1322"); }//actionPerformed }//ReviewListener Write the command line output when the buttons are clicked in the following order: Oh yeah!, Stop the Lies, I like Java ----------------- Section V: Coding ----------------- - Basics o Code fibonacci(int n) which returns the nth fibonacci number o Code boolean isPrime(int x) which returns true if x is prime, false otherwise. o Code int countPrimesBetween(int a, int b) which counts the number of primes between a and b (inclusive) [You may assume isPrime works from above] o Code int termOfGeometricSeries(int a, int r, int n) which returns the nth term of the geometric series which has a first term of a, a ratio of r . You must use ITERATION (no recursion) for this method. You may not solve it with a direct formula. (Recall that the next term of a geometric series is found by multiplying the previous term by the ratio r). o Code termOfGeometricSeries(int a, int r, int n) [as above] but this time you must use RECURSION (only, no iteration). o Code pascalsTriangle(int row, int col) which returns the corresponding number from pascal's triangle. Recall that the triangle looks like 1 1 1 1 2 1 (each entry is the sum of the on up-left of it, 1 3 3 1 and right above it) 1 4 6 4 1 ......... You must use RECURSION to solve this problem. You may not use any iteration. o Write the method int gcd(int a, int b) which returns the gcd of a and b. (Recall that the gcd of a and b is the largest int which divides both a and b). o Write the method int lcm(int a, int b) which returns the lcm of a and b. (Recall that the lcm of a and b is the smallest positive int which is a multiple of both a and b). o Write pow(int x, int y) which computes x raised to the y. o Write multiply(int x, int y) which returns x*y. YOU MAY NOT USE THE * OPERATOR FOR THIS. o Write int backwards(int x) which returns the number reversed. So backwards(123) would result in 321. YOU MAY NOT CONVERT THE NUMBER TO A STRING. o Write long smallestPowOf2Over(long x) which returns the smallest power of 2 greater or equal to than x. o Write the method String reverseString(String s) which returns the string reversed. For example reverse("abc") would return "cba" o Write int countWaysToMakeChange(int ammountOfMoney) which takes an integer number of cents and returns the number of ways that that ammount of money can be made with pennies, nickels, dimes and quarters. Hint: to make change for ammount A out of the set of coins S, The number of ways to make change for A is number of ways to make change for (A- biggest coin in S) with S + number of ways to make change for A with (S without the biggest coin) To help you check yourself: o There is 1 way to make 4 cents o There are 2 ways to make 7 cents o There are 4 ways to make 11 cents o There are 49 ways to make 50 cents o There are 242 ways to make 100 cents For your reference, here's a Scheme solution you may have worked with in CS1: (define (count-change amount) (count amount 4)) ; there are four coins types (define (count amount types-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= types-of-coins 0)) 0) (else (+ (count amount (- types-of-coins 1)) (count (- amount (first-denomination types-of-coins)) types-of-coins))))) (define (first-denomination types-of-coins) (cond ((= types-of-coins 1) 1) ((= types-of-coins 2) 5) ((= types-of-coins 3) 10) ((= types-of-coins 4) 25))) - Arrays o Write the method int sum(int[] numbers) which returns the sum of all items in the array. o Write int min(int[] data) o Write int max(int[] data) o Write int average(int[] data) o Write int median(int[] data) o Write int countLess(int[] data, int x) o Write int countEven(int[] data, int x) o Write int[] addTogether(int[] a, int[] b) //makes an array such that each element in the answer is // the sum of the corresponding elements in a and b. NOTE: do not assume that both are the same length. The answer array should be the lenght of the longer of the two arrays. If one is longer, put the extra items into the answer array unchanged. o Write the method public boolean [] knapsack(int[] a, int b) //This method figures out which values from a would be used //to sum to b. true if the value is used, false otherwise. // ie. knapsack({1,4,5,8}, 12) would return {false, true, false, true} // since you get 12 from 4+8. // if no combination of the values would work, your method should // return null o Write Comparable[] bubbleSort(Comparable[] arrayToSort) which sorts the array in ascending order. YOU MUST USE BUBBLE SORT. o Write Comparable[] heapSort(Comparable[] arrayToSort) which sorts the array in ascending order. YOU MUST USE HEAP SORT. o Write Comparable[] quickSort(Comparable[] arrayToSort) which sorts the array in ascending order using. YOU MUST USE QUICK SORT. o Write Comparable[] insSort(Comparable[] arrayToSort) which sorts the array in ascending order. YOU MUST USE INSERTION SORT. o Write Comparable[] mergeSort(Comparable[] arrayToSort) which sorts the array in ascending order. YOU MUST USE MERGE SORT. o Write String[] uniqueSplit(String inputString, String delimiters) This method should tokenize the input String based on the delimiters, collect the tokens into an array, and eliminate duplicates. For example, uniqueSplit("a word and another word and a third word", " ") would return an array of size 5 containing {"a","word","and","another","third"} Note that the elements in the array should appear in the same order as their first occurrence in the original string and that the there should not be an element holding the delimiter. (Hint: the delimiters can be passed to a StringTokenizer) - Multi-dim Arrays o Write determinant(int[][] matrix) which returns the determinant of the matrix passed in. You will probably need to use both iteration AND recursion for this method. Recall that the determinant is defined as follows: - for a 1x1 matrix (a single number), it is the value in that matrix. - for any larger matrix, for each column, take the number in the top row (call it a) and take all numbers not in that column and not in that row as a matrix- compute their determinant (recursively) and multiply that by a. if the column number is even, add it to a total. if it is odd, subtract it from that total (counting from 0). the determinant is that total. o Write boolean isSquare(int[][] x) which returns true if x is square array, false if x is not square array. Note that for an array to be square, all of the second dimensions must be equal to the first. o Write boolean isCube(int[][] x) which returns true if x is a cube array, false if x is not a cube array. o Write double[][][] addArrays(double[][][] a, double[][][] b) o Write int[][] multiplyMatricies(int[][] a, int[][] b) which does matrix multiplication. (remember that matrix multiplication is NOT done by simply multiplying each element). o Write int sum(int[][][] data) which returns the sum of all the items in the array. o Write boolean hasPairThatSumsTo(int[][] x, int val) which returns true if any two items in x sum to val, false otherwise. o Write byte[][] shiftRows(byte[][] data) which shifts each row one to the left- ie. { {a1, b1, c1, d1}, {a2, b2. c2, d2, e2} } becomes { {b1, c1, d1, a1}, {b2. c2, d2, e2, a2} } NOTE: do not modify the contents of the original array. You must return a new array. o Write Object[][] matrixTranspose(Object[][] matrix) This method should return a new matrix which is the transpose of the matrix passed in. The transpose of a matrix is the matrix written "sideways". For example, matrixTranspose( {{"a","b","c"},{"d","e","f"}, {"g","h","i"}}) would return the matrix {{"a","d","g"},{"b","e","h"},{"c","f","i"}} You may not make any assumptions about the dimensions, or contents of the matrix passed in, other than that the array itself will not be null. You may not modify the original array- you must create a new one to return. o Write the method char ticTacToeWinner(char[][] board) This method takes a tic-tac-toe board of any square size and looks to see who has won. The tic-tac-toe board is an nXn char[][] which contains one of three characters in each entry 'X','O', or ' '. An 'X' indicates that the space is occupied by player X. An 'O' indicates that the space is occupied by player O. A ' ' indicates that the space is unoccupied. Your method should analyze the board and determine which (if either) player has won the game. If player X has won the game, your method should return 'X'. If player O has won the game, your method should return 'O'. If nobody has won the game yet, your method should return ' '. Note that a win on an nXn board is a sequence of n consecutive X's or n consecutive O's on any column, row, or main diagonal. Note that the main diagonals are the ones that run from the top-left corner to the lower-right corner and the one that runs from the lower-left to the top-right corner. - LinkedLists o int size() //returns a count of how many items are in the list o void addToBack(Object data) o void addToFront(Object data) o void addAllInVector(Vector v) //adds all items in the Vector. // you may not use any other add method. o Object removeFromBack() //return the data from the node deleted o Object removeFromFront() o Object removeIndex(int n) //removes the nth element (counting from 0) // from the LinkedList, if there are more than n elements in the list. // returns the data if such an element was removed. // returns null if there were not enough elements in the list o int countEqualTo(Object data) //this method counts how many //objects in the list are equivalent to the data passed in, //and returns that count. o LinkedList copyList() //this method makes a new LinkedList //which is a copy of the current list. //the new list should reference the exact same objects //but changes (adds,deletes) to the copy should not //affect the original, and vice versa o void filterOut(Object data) //finds all occurences of data, // and removes them from the list o void addAfter(Object data, Object after) //adds data to the list so it is immediately after the //first occurence of an Object equivalent to 'after' in the list. //if no Objects equivalent to 'after' appear in the list, //data should be added at the FRONT of the list. o void addBefore(Object data, Object before) //adds data to the list so it is immediately before //the first occurrnec of an Object equivalent to 'before' in the list. //if no Object equivalent to 'before' appear in the list, //data should be added to the END of the list. o void merge(LinkedList l) //adds all of the data from l to // this list. l should be unaffected by the call to merge o void backwards() //makes this list backwards of what it was. o Object[] toArray() //returns an array holding the data //that is in the list. the list should not be modified o Vector toVector() // builds a Vector with all of the // data from this LinkedList o Enumeration allElements() // returns an Enumeration of all // the elements in this list. o LinkedList buildList(Object[] data) //makes a LinkedList holding //all of the data in the array. You may assume that LinkedList // has the following methods (ONLY): // the constructor LinkedList() //makes an empty list // void addToFront(Object data) // void addToBack(Object data) o String toString() //this should return a String representation of the list, // in the same format as in lab, ie.. // FRONT-->data1-->data2-->data3-->END - IO o Write the method void fileBackwardsCopy(String readFrom, String writeTo) This method should read the contents of the file whose name is passed in as the readFrom parameter, reverse its contents, and write it back out to the file whose name is passed in as writeTo. If for example, the input file contained Here is an example of what my extra credit programs fileBackwardsCopy should do. Then the output file should have .od dluohs ypoCsdrawkcaBelif smargop tiderc artxe ym tahw fo elpmaxe na si ereH (Hint: you may want to use your reverseString from above) o Write the method void fileReplaceCopy(String readFrom, String writeTo, char toReplace, char replaceWith) This method should read the contents of the file whose name is passed in as the readFrom parameter, replace each occurent of the toReplace parameter with the replaceWith parameter, and write the modified contents back out to the file whose name is passed in as writeTo. The file should not make any attempt to modify the original file (the one whose name was passed in as readFrom) on disk. If for example, the input file contained Here is an example of what my extra credit programs fileReplaceCopy should do. And the toReplace parameter was 'h' and the replaceWith parameter was 'Q', then the output file should have Here is an example of wQat my extra credit programs fileReplaceCopy sQould do. o Write the method void rotXFile(String inputFilename, String outputFilename, int x) This method takes the names of two files: one which it will read input from, the other that the output will be written to. Your method will read the contents of the input file, and for each character which is alphabetic (a-z or A-Z) it will "rot X" (see below) that value before writing it to the output file. For any characters that are not alphabetic (numbers, punctuation, etc), they should be written to the file as is. "rot X" on a letter is defined by adding the number X to the letter, and "wrapping around"- ie rot 13 of a is n (n is 13 letters later than a) rot 13 of w is j (you can only go 3 letters till 'z', then you have to wrap around for the other 10 letter to get to 'j') rot 0 of any letter is itself rot -1 of c is b etc. - BSTs o Write the method void insert(Comparable c) o Write the method Comparable find(Comparable c) o Write the method void delete(Comparable c) o Write the method void removeAllGreaterThan(Comparable c) o Write the method void inOrderTraverse() o Write the method void preOrderTraverse() o Write the method void postOrderTraverse() o Write the method void levelOrderTraverse() o Write the method void reverseOrderTraverse() o Write the method Vector gatherAllNodesBetween(Comparable low, Comparable hi) The method should use <, > and not <=, >=. An empty Vector, and not null, should be returned if no nodes are identified in range. o Write the method int findLargestNotLargerThan(Comparable c) o Write the method int countSmallerThan(Comparable c) o Write the method int countEqualTo(Comparable c) o Write the method int countNodesWithOneChild() o Write the method Comparable findMedianInCompleteTree() //this method returns the median value from the tree- //which this method assumes is complete- i.e. it is full // and balanced, with 2^k-1 nodes (for some value of k) o Write the method Enumeration elementsInOrder() o Write the method int countEdges() // returns a count of // how many "edges" there are in the tree. // for example, // 5 // / \ // 2 6 // / // 1 // has 3 edges (one goes 5-2, one goes 5-6, one goes 2-1). - Heaps o Write the constructor for a Heap o Write the method void insert(Comparable data) o Write the method Comparable getMin() o Write the method Comparable removeMin() o Write the method void heapify(int ind) o Write the method int buildHeap(Comparable [] cArray) This method takes an array of comparables and rearranges them (in the same array) so that they are in a valid heap ordering with the largest in element 0. You must perform this by properly heapifying. Your method should return the number of swaps that it had to perform to obtain that ordering. o Write a PriorityQueue class, assuming that you have a working Heap. - Hashtables o Write the constructor for a HashTable that takes in an int for size. o Write the method void add(Object key, Object data) o Write the method Object find(Object key) o Write the method boolean contains(Object key) o Write the method Object remove(Object key) o Write the method Enumeration allElements() o Write the method void rehash(int newSize) - Graphs o Write Path DFS(Node start, Node goal) o Write Path BFS(Node start, Node goal) o Write Vector allPathsInVectorDFS(Node start, Node goal) o Write Vector allPathsInVectorBFS(Node start, Node goal) o Write Path[] allPathsInArrayDFS(Node start, Node goal) o Write Path[] allPathsInArrayDFS(Node start, Node goal) o Write Vector vectOfAllNodesReachableDFS(Node start) // returns a Vector containing all nodes that can be reached from // start, using a DFS o Write Vector vectOfAllNodesReachableBFS(Node start) // returns a Vector containing all nodes that can be reached from // start, using a BFS - GUIs o Write code to create a GUI with 5 buttons (that do nothing) so that it has them arranged like this: (dont forget to set the title) +--------------------------------------------+ | Practice GUI _ [] X | +--------------------------------------------+ | button 1 | |--------------------------------------------| | | | | | | | | | | | | | b2 | hello world | b3 | | | | | | | | | | | | | | | | | |--------------------------------------------| | button 3 | +--------------------------------------------+ o assuming that you have JButton jb1=new JButton("Click Me!"); Write the code to make it so that when you click that button, it will print "I've been clicked" to the console.