Author Archives: Mr. M

Sorting Algorithm Assignment

Sorting Algorithm

 

Good Links

 

You will be given a sorting algorithm to research and to present to the class in a powerpoint. Your powerpoint should

  1. in general terms explain how the algo works
  2. show Java code for the algorithm
  3. have an animation demonstrating how the algorithm works (step by step)
  4.  clearly explain how the code (in each line) relates to the code (most important and easy to forget step)
  5. It’s important that you can explain each line of the code
  6. state best,worst, average case for the data and, in particular, state how the original state of data affects run time performance
    1. in order
    2. random
    3. in reverse order

Grading Rubric Algorithm Project

 

 

 

4

3

2

1
  Big Oh

(double weight)

 Addresses best/worst/ave cases with clear connection to all aspects of code

 

 Addresses best/worst/ave cases  but does not relate to all relevant code Addresses best/worst/ave cases  but does not connect to code/is too general Does not address all 3 cases Big Oh or does not connect to code in meaningful way
 Animation of algorithm(double weight)

 

 

 

 Animation is clearly connected to all aspects of code Animation is connected to critical areas of code Animation is not clearly connected to actual code Animation and code are not related to one another
 Overview(double weight)

 

 Gives a clear and enlightening overview of how the algo works in general. Overview of algorithm is technically correct and discusses most of the relevant features. Algorithm is vaguely summarized or is not well explicated. Algorithm is not explained in a meaningful way.

 
  

 

 

 

While loop with if test

Let’s write a program that solves the map below (which you should create yourself) using only 1 while loop

jeroo maps loops 24 jeroo maps loops 25

 

What is an “If Test”?

If you just want to do a single test, use an ‘if’ test, instead of a while loop

goroundwater

 

…Now we can continue hopping till we get to the end of the map

jeroo maps loops 25

 

 

Your Assignment: Create the map above and complete the program . All that you have to do use is the code at the top and then write the custom method goRoundWater()

 

 

 

 

 

 

 

 

 

 

 

Class Relationships involving interfaces and Abstract Classes

Two Caveats

  1. all instance variables must be explicitly written as “private”
  2. Declare ArrayList’s as type “list”:
    1.  List<Integer> blahBlah = new ArrayList<Integer>()
    2. list-arraylist

 

The classes below represent different ways of representing mathematical  concepts like MathExpressions, Fractions etc. and they all implement the Mathable interface. 

 

graphical_math_object

 

public abstract class GraphicalMathObject

methods

  • public abstract void displayGraphicalRepresentation() ;

public class Fraction extends GraphicalMathObject

This class is used to represent Fractions

Instance Variables

  • private int numerator
  • private int denominator

Constructor : The constructor should initialize both instance variables

  • public Fraction(int num, int denom)

Methods

  • public void displayGraphicalRepresentation() ; (just print out ” I’m a fraction -displayGraphicalRepresentation()”. This is the method that renders a graphical representation of the fraction .
  • fraction-matching
  • private int getGCF() //returns the GCF of numerator and denominator
  • public void simplify()//simplifies the fraction. Note: you must call getGCF()
  • public Fraction clone() //return a clone of the current object (** Extra credit…research this) ( link )
  • plus all of the methods in Mathable (Described at bottom)

public class MathExpression extends GraphicalMathObject

This is a class that is used to represent mathematical expressions like 3x2or 5x2y2 . It contains the methods and variables described below and it must implement Mathable

Instance Variables

  • private int coefficient
  • private List<String> variables
  • private List<Integer> powers

NOTE: you should use the following sytnax

Declare ArrayList’s as type “list”:

  1.  List<Integer> blahBlah = new ArrayList<Integer>()
  2. list-arraylist

Constructor : You can decide how to write the constructor.

  • Just be sure to initialize the instance variables

methods implement all methods of the Mathable Interface in ways that make sense for this class. The idea with Mathable is that you should be able to tell if the objects are either equivalent, exactly the same and that you should be able to return a String representation (data) that uniquely identifies the given mathematical expression.

  • public void addTerm( String term , int power) ) // This is used to represent multiplication, actually and this method adds a term with a power to the object’s list of variables and power to the list of powers. You can not assume that the term does not yet exist in the expression .
    For instance, if the original term were 3x5 and the object called addTerm(“y”, 6)  the object would then be 3x5y6. Or for another example, if the original term is 2x3z6 , and addTerm(“z”, 5)  the object would be 2x3z11 .
  • public void displayGraphicalRepresentation()  ; (just print out “I”m a MathExpression.: displayGraphicalRepresentation()”). This is the method that draws the MathExpression on the screen like:
  • plus all of the methods in Mathable

Examples

3x2y5

coefficient: 3

variables : [ “x”, “y”]

powers : [ 2, 5]
x1y11

coefficient: 1

variables : [ “x”, “y”]

powers : [ 1, 11]
3y2x5

coefficient: 3

variables : [ “y”, “x”]

powers : [ 5 , 2]

 


Interface : Mathable

  • public String getData( ) ;   represents core mathematical information that defines current object.
  • public boolean exactlyEquals(Mathable other) ;
  • public boolean isEquivalent(Mathable other) ;

Walk the Lake (custom Method)

 

method main(){
Jeroo Russell  = new Jeroo(10,3, EAST );

Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
Russell.pickTossAndHop();
}
 
def pickTossAndHop( self ):
	pick();
	toss();
	hop();

 

The Betrothal

The Betrothal

Tom and Tammy are in love, and today’s the day that Tom is going to propose. According to custom, Tom must present Tammy with a flower as an official sign of his intentions. Tom lives in the extreme northwest corner of the island, and Tammy lives in the extreme northeast corner. The dividing river runs north and south, dividing the island roughly in the middle; the river is at least 5 cells away from the western and eastern edges of the island. The river, itself, is exactly two cells wide. Fortunately, for the lovers, there is a bridge somewhere to the south of their homes. Tom has asked Tammy to meet him at the middle of the bridge. While she suspects his motives, she doesn’t want to appear too anxious. The purpose of this program is to have Tom and Tammy find the bridge and meet in the middle where Tom will give an engagement flower to Tammy. After he has given her the flower, each returns to its home and faces the home of its betrothed. Each Jeroo starts at its home, Tom at (0,0) and Tammy at (0,23). Each can start facing any direction. Tom starts with one special flower in his pouch. A representative starting layout is shown in figure 1
Download the Island Files