Final Study
Construction
Inheritance and Polymorphism
Create an abstract shape class named Polygon. It should have a private instance variable String name. It should have an abstract method calcArea. It should have a toString method which prints the name.
Create the triangle and rectangle classes to inherit Polygon and override the toString method by first executing polygon's toString and adding the length of the other sides in the shape. Triangle's have 3 instance variables for their sides and rectangles have four. For the rectangle class, add an isSquare method.
Create an interface Colorable that just has the abstract method determineColor that takes in nothing and returns the color name. Make Triangle and Rectangle implement Colorable. If one Triangle side is more than 10 , the color is Red, and otherwise it is blue. For a rectangle, if the area is greater than 20, the color is Red, and otherwise it is blue.
Create another program that creates 3 arraylists: one of Colorable and another of Polygon and one more of Rectangle. Try to put a variable of every type inside of class you have inside the list. Then call all their methods. Guess what will happen and then see what does happen.
For answer, see the zip file of Inheritance answer.
FileProcessing:
Read in all the words in a file. Sort them alphabetically (and it is okay to use Collections.sort). Print the sorted list.
Answer:
public static void readFile( ){
ArrayList<String> arr
= new ArrayList<String>();
try
{
Scanner fReader=
new Scanner (new File ("sample.txt"));
while ( fReader.hasNext ())
{
arr.add( fReader.next());
}
Collections.sort(arr);
for
(String s : arr){
System.out.println(s);
}
}
catch (FileNotFoundException
ex){
System.out.println("Error"
+ ex.getMessage());
}
}
Queue Processing:
· Copy everything in a queue to a stack. Print out the Stack while emptying it.
Answer:
public static void
queueEx (Queue<String> q){
Stack<String> st
= new Stack<String>();
int
sz = q.size();
for (int c = 0; c < sz; c++){
String name = q.remove();
st.push(name);
q.add(name);
}
while (!st.isEmpty()){
System.out.println(st.pop());
}
}
// and to test it:
public static void
testQueueEx(){
Queue a = new LinkedList(Arrays.asList("a","b","c"));
queueEx(a);
System.out.println( a);
}
ArrayLIst processing:
Write a static method named arraySum that accepts two arrays of real numbers a1 and a2 as parameters and returns a new array a3 such that each element of a3 at each index i is the sum of the elements at that same index i in a1 and a2. For example, if a1 stores {4.5, 5.0, 6.6} and a2 stores {1.1, 3.4, 0.5}, your method should return {5.6, 8.4, 7.1}, which is obtained by adding 4.5 + 1.1, 5.0 + 3.4, and 6.6 + 0.5.
If the arrays a1 and a2 are not the same length, the result returned by your method should have as many elements as the larger of the two arrays. If a given index i is in bounds of a1 but not a2 (or vice versa), your result array's element at index i should be equal to the value of the element at index i in the longer of a1 or a2. For example, if a1 stores {1.8, 2.9, 9.4, 5.5} and a2 stores {2.4, 5.0}, your method should return {4.2, 7.9, 9.4, 5.5}.
The table below shows some additional calls to your method and the expected values returned:
|
Arrays |
Call and Value Returned |
|
ArrayList<Double> a1 = new ArrayList<Double>(Arrays.asList(4.5, 2.8, 3.4, 0.8)); ArrayList<Double> a2 = new ArrayList<Double>(Arrays.asList(1.4, 8.9, -1.0, 2.3)); |
arraySum(a1, a2) returns {5.9, 11.7, 2.4, 3.1} |
|
ArrayList<Double> ax = new ArrayList<Double>(Arrays.asList(2.4, 3.8)); ArrayList<Double> ay = new ArrayList<Double>(Arrays.asList(0.2, 9.2, 4.3, 2.8, 1.4)); |
arraySum(ax, ay) returns {2.6, 13.0, 4.3, 2.8, 1.4} |
|
ArrayList<Double> aa = new ArrayList<Double>(Arrays.asList(1.0, 2.0, 3.0)); ArrayList<Double> ab = new ArrayList<Double>(Arrays.asList(4.0, 5.0)); |
arraySum(aa, ab) returns {5.0, 7.0, 3.0} |
|
ArrayList<Double> ai = new ArrayList<Double>(); ArrayList<Double> aj = new ArrayList<Double>(Arrays.asList(42.0)); |
arraySum(ai, aj) returns {42.0} |
Answer:
public static ArrayList<Double>
arraySum(
ArrayList<Double> a, ArrayList<Double>
b){
ArrayList<Double> ans
= new ArrayList<Double>();
int c = 0;
for ( c
= 0; c < a.size() && c < b.size(); c++){
ans.add(a.get(c)
+ b.get(c));
}
for (int j = c; j
< a.size(); j++){
ans.add(a.get(j));
}
for (int j = c; j
< b.size(); j++){
ans.add(b.get(j));
}
return ans;
}
public static void testArraySum(){
ArrayList<Double> a = new ArrayList<Double>(
Arrays.asList(3.,5.,6.,7.));
ArrayList<Double> b = new ArrayList<Double>(
Arrays.asList(2., 3.,
4.,1.,4.));
System.out.println( arraySum(a,b));
}
Collections:
Write a method that takes in 1 linkedlist, one arraylist and one map return an arraylist that all the values from either the linkedlist or arraylist, but has all the keys from the map removed from the result. It also has no duplicates and is sorted.
For example:
LInkedList has 1, 3, 5,
ArrayList has 1, 2, 4, 4, 5, 7
map has the following keys: 2,5
The returned arraylist should be 1, 3, 4, 7
One Answer:
public static ArrayList
<Integer> collector(LinkedList <Integer>
a, ArrayList <Integer> b, Map <Integer,
String> c){
TreeSet <Integer> ans
= new TreeSet <Integer>(a);
ans.addAll(b);
Set <Integer> keys = c.keySet();
ans.removeAll(keys);
ArrayList <Integer> returner = new ArrayList <Integer>(ans);
return
returner;
}
Recursion:
Given base and n that are both 1 or
more, compute recursively (no loops) the value of base to the n power, so powerN(3,
2) is 9 (3 squared).
public int powerN(int base, int n) { }
powerN(3, 1) → 3
powerN(3, 2) → 9
powerN(3, 3) → 27
One Answer:
public static int powerN(int base, int n){
if (n == 1){
return
base;
}
else
{
return
base* powerN(base,n-1);
}
}
Fill out this chart for Big O Notation
|
Description |
Big
O Notation |
|
Selection Sort |
O (N ^ 2) |
|
Merge Sort |
O (N Log N) |
|
Bubble Sort |
O (N ^ 2) |
|
Linear Search |
O (N) |
|
Binary Search |
O (Log N) |
|
A single loop from 0 to the size
of the array |
O(N) |
|
A single loop from 0 to the size
of the array with a loop inside from 3 to the size of the array |
O(N^2) |
|
A single loop from 0 to the size
of the ArrayList
that gets and sets items |
O(N) – because get and set on Arraylist causes no hidden loop |
|
A single loop from 0 to the size
of the LinkedList
that gets and sets items |
O(N^2) – because get and set on LinkedList causes a hidden loop |
|
A single loop from 0 to the size
of the ArrayList
that repeatedly removes the first item |
O(N^2) – because remove from the front
on an Arraylist causes a hidden loop |
|
A single loop from 0 to the size
of the Queue that repeatedly removes
the first item |
O(N) – because remove from the
front of a LinkedList does not cause a hidden loop |
To thoroughly study for search and sort:
· Given a point class, write methods to sort and search for a y value.
· Selection, Bubble, MergeSort , Comparator
· Linear and Binary Search
Answer:
public class
Point{
private int x;
private int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
public int getX(){
return this.x;
}
public int getY(){
return this.y;
}
public String toString(){
return "x: " + x + " y: " +
y;
}
}
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;
public class SearchAndSort
{
public static void main (String[] args)
{
ArrayList<Point> arr
= new ArrayList<Point> (
Arrays.asList(new
Point(3,4), new Point(1,2), new Point(5, 9)));
System.out.println ( "Linear:
find arr, 9
at: " + linearSearch(arr,
9));
System.out.println ( "Linear:
find arr, 16
at: " + linearSearch(arr,
16));
System.out.println ( "Binary:
find arr, 9
at: " + binarySearch(arr, 9));
System.out.println
( "Binary: find arr,
4 at: " + binarySearch(arr, 4));
System.out.println ( "Binary:
find arr, 16
at: " + binarySearch(arr, 16));
selectionSort(arr);
System.out.println("selection sort leaves " + arr);
mergeSort(arr);
System.out.println("merge sort leaves " + arr);
bubbleSort(arr);
System.out.println("bubble sort leaves " + arr);
}
public static int linearSearch(ArrayList<Point>
arr, int target){
for (int i = 0; i < arr.size();
i++)
{
if (arr.get(i).getY()
== target)
{return i;}
}
return -1;
}
public static int binarySearch(ArrayList<Point>
arr, int target){
Collections.sort(arr, new YSorter());
int min = 0;
int max = arr.size() - 1;
while( min <= max) {
int mid = (max
+ min) / 2;
if (arr.get(mid).getY() == target){
return
mid;
}
else if (arr.get(mid).getY() < target)
{
min =
mid + 1;
}
else
{
max =
mid - 1;
}
}
return -1;
}
public static void selectionSort
( ArrayList<Point> arr
)
{
int i, j, smallestIndex;
for ( i = 0 ; i < arr.size() ; i ++ )
{
smallestIndex = i;
for(j =
i+1; j < arr.size(); j ++) //locate smallest element between positions
1 and i.
{
if( arr.get(j).getY() < arr.get(smallestIndex).getY() ) // compare
Y's
smallestIndex = j;
}
Point temp = arr.get( smallestIndex
); //swap smallest point found with
element in position i.
arr.set( smallestIndex
, arr.get( i ));
arr.set(i, temp);
}
}
import java.util.Comparator;
public class YSorter implements Comparator<Point>
{
public int
compare(Point o1, Point o2){
return
o1.getY() - o2.getY();
}
}
public static void bubbleSort(ArrayList<Point> arr ){
boolean switched;
int i = 0;
do {
switched =
false;
for (int j = 0; j < arr.size()-1 ; j++){
if ( arr.get(j).getY() > arr.get(j+1).getY()){
Point temp = arr.get(
j ); //swap smallest found with
element in position i.
arr.set( j , arr.get( j+1 ));
arr.set(j+1, temp);
switched
= true;
}
}
i++;
} while (i < arr.size() &&
switched);
}
public static void mergeSort(ArrayList<Point> arr ){
if (arr.size() > 1) {
// split into two halves
ArrayList<Point> left = new ArrayList<Point> (arr.subList(0,arr.size()
/ 2));
ArrayList<Point> right = new ArrayList<Point> (arr.subList(arr.size()/2 ,arr.size() ));
// sort those halves (further
splitting)
mergeSort(left);
mergeSort(right);
// merge the sorted halves into
wholes
merge(arr, left,right);
}
}
public static void merge(ArrayList<Point>
result, ArrayList<Point> left, ArrayList<Point> right){
int leftIndex = 0;
int rightIndex = 0;
for (int i = 0; i < result.size();
i++){
if (rightIndex >= right.size()
|| (leftIndex
< left.size()
&& left.get(leftIndex).getY() <= right.get(rightIndex).getY())){
// take from left
result.set(i, left.get(leftIndex));
leftIndex++;
}
else //
take from right
{
result.set(i, right.get(rightIndex));
rightIndex++;
}
}
}
}
---------------------------------------------------------