Implementing the sequential search algorithm in java

Problem:

The sequential search (also called the linear search) is the simplest search algorithm. It is also
the least efficient. It simply examines each element sequentially, starting with the first element,
until it finds the key element or it reaches the end of the array.
If you were looking for someone on a moving passenger train, you would use a sequential
search.
Here is the sequential search algorithm:
(Postcondition: either the index i is returned where si
= x, or 1 is returned.)
1. Repeat steps 2 3, for i = 0 to n 1.
2. (Invariant: none of the elements in the subsequence {s0...si–1} is equal to x.)
3. If si = x, return i.
4. Return 1.
Implement the sequential search algorithm

Output:

{22, 33, 44, 55, 66, 77, 88, 99}
search(a, 44): 2
search(a, 50): -1
search(a, 77): 5
search(a, 100): -1

Solution:

public class TestBinarySearch {
public static void main(String[] args) {
int[] a = {22, 33, 44, 55, 66, 77, 88, 99};
ch02.ex02.DuplicatingArrays.print(a);
System.out.println("search(a, 44): " + search(a, 44));
System.out.println("search(a, 50): " + search(a, 50));
System.out.println("search(a, 77): " + search(a, 77));
System.out.println("search(a, 100): " + search(a, 100));
}
public static int search(int[] a, int x) {
// POSTCONDITIONS: returns an integer i; 
// if i >= 0, then a[i] == x; otherwise x is not in a[];
for (int i=0; i<a.length; i++) { // step 1
// INVARIANT: x is not among a[0]...a[i-1] // step 2
if (a[i] == x) { // step 3
return i;
}
}
return -1; // step 4
}
}

Read More

Duplicating an array in Java

Problem:

Write a problem that duplicates arrays by invoking the Object.clone() method.

Output:

{22, 44, 66, 88}
{22, 44, 66, 88}
{AB, CD, EF}
{AB, CD, EF}
{AB, XYZ, EF}
{AB, CD, EF}

Solution:

public class DuplicatingArrays {
public static void main(String[] args) {
int[] a = {22, 44, 66, 88};
print(a);
int[] b = (int[])a.clone(); // duplicate a[] in b[]
print(b);
String[] c = {"AB", "CD", "EF"};
print(c);
String[] d = (String[])c.clone(); // duplicate c[] in d[]
print(d);
c[1] = "XYZ"; // change c[], but not d[]
print(c);
print(d);
}

public static void print(int[] a) {
System.out.printf("{%d", a[0]);
for (int i = 1; i < a.length; i++) {
System.out.printf(", %d", a[i]);
}
System.out.println("}");
}
public static void print(Object[] a) {
System.out.printf("{%s", a[0]);
for (int i = 1; i < a.length; i++) {
System.out.printf(", %s", a[i]);
}
System.out.println("}");
}
}

Read More

20 Properties of Arrays in Java

Problem:

List the 20 properties of java arrays.

Output:

Not applicable.

Solution:

Here are the main properties of arrays in Java:
1. Arrays are objects.
2. Arrays are created dynamically (at run time).
3. Arrays may be assigned to variables of type Object.
4. Any method of the Object class may be invoked on an array.
5. An array object contains a sequence of variables.
6. The variables are called the components or elements of the array.
7. If the component type is T, then the array itself has type T[].
8. An array type variable holds a reference to the array object.
9. The component type may itself be an array type.
10. An array element is a component whose type is not an array type.
11. An element’s type may be either primitive or reference.
12. The length of an array is its number of components.
13. An array’s length is set when the array is created, and it cannot be changed.
14. An array’s length can be accessed as a public final instance variable.
15. Array index values must be integers in the range 0...length 1.
16. An ArrayIndexOutOfBoundsException is thrown if Property 15 is violated.
17. Variables of type short, byte, or char can be used as indexes.
18. Arrays can be duplicated with the Object.clone() method.
19. Arrays can be tested for equality with the Arrays.equals() method.
20. Array objects implement Cloneable and java.io.Serializable.

Read More

20 Questions Every Java Developper Must Know

Problem:

How well do you understand java? Are you a master of the programming language java or are just some junkie who memeorized the rules pass an exam or a standarized test? Test yourself!

1.1 What is a requirements document?
1.2 What is the difference between the design stage and the implementation stage in the development software?
1.3 What is the difference between the state and the behavior of a class?
1.4 What is an abstract data type?
1.5 What constitutes a Java program?
1.6 What kinds of members can a class have?
1.7 What is an implicit argument?
1.8 What is the purpose of the toString() method?
1.9 What is the purpose of the equals() method?
1.10 What's the difference among public, protected, and private?
1.11 What is a package?
1.12 What is the difference between an abstract class and an abstract data type?
1.13 What is the difference between a constructor and a method?
1.14 What is the difference between a class method and an instance method?
1.15 What is the difference between equality of objects and equality of the references that refer to
them?
1.16 Explain the difference between the output from
String s;
System.out.println("s = " + s);
and the output from
String s = new String();
System.out.println("s = " + s);
1.17 What is the purpose of declaring a field private and declaring a mutator method that allows
the public to change it. Wouldn’t it be just as good to just make it public?
1.18 What is an enum type?
1.19 What is the difference between composition and aggregation?
1.20 What is polymorphism?

Output:

Not applicable.

Solution:

1.1 The requirements document of a software development project is a precise specification of what the
software should do.
1.2 In the development of software, the design stage identifies the components (classes) to be used and the
relationships among them. The implementation stage is where the computer progam code is actually
written.
1.3 The state of a class consists of the values of its fields. The behavior of a class is defined by its methods.
1.4 An abstract data type is a specification of the type’s operations: what an instance of that type can do.
1.5 A Java program is a Java class with a main() method? The main() method must have this header:
public static void main(String[] args)
1.6 A class member may be a field, a constructor, a method, a nested class, a nested interface, or an enum
type.
1.7 The implicit argument of a method is the object to which the method invocation is bound.
1.8 The toString() method returns a String object that represents the state of its implicit argument.
1.9 The equals() method returns true if and only if states (contents) of its implicit and explicit arguments
are the same.
1.10 A class member that is declared public is accessible from any other class. A class member that is
declared protected is accessible only from its own class and subclasses (extensions). A class member
that is declared private is accessible only from its own class.
1.11 A package is a namespace, that is, a name for a group of classes, interfaces, and enum types that can be
used to distinguish those from other classes, interfaces, and enum types with the same name.
1.12 An abstract class is a Java class with at least one abstract method—a method that has no body. An
abstract data type is a specification of a type’s operations that could be implemented in any object-oriented
programming language.
1.13 A constructor is a member function of a class that is used to create objects of that class. It has the same
name as the class itself, has no return type, and is invoked using the new operator. A method is an ordinary
member function of a class. It has its own name, a return type (which may be void), and is
invoked using the dot operator.
1.14 A class method is declared static and is invoked using the class name. For example,
double y = Math.abs(x);
invokes the class method abs() that is defined in the Math class. An instance method is declared without
the static modifier and is invoked using the name of the object to which it is bound. For example,
double x = random.nextDouble();
invokes the class method nextDouble() that is defined in the Random class and is bound to the object
random which is an instance of that class.
1.15 Two objects should be equal if they have the same data values (i.e., the same state). Two references are
equal if they refer to the same object. The condition (p == q) tests equality of the references p and q,
not the equality of the objects to which they refer.
1.16 The output from the code
String s;
System.out.println("s = " + s);
is
s = null
The output from the code
String s = new String();
System.out.println("s = " + s);
is
s =
In the first case, the reference s is initialized by default to be null; there is no String object. In the
second case, s is initialized to refer to the empty String object.
1.17 The advantage of forcing the public to use a mutator method to change a field is that you can control
how the field is changed.
1.18 An enum type is a type, defined with the enum keyword that lists by name each possible value for the
type.
1.19 When a type is composed of another type, the complete existence of that component type’s objects is
controlled by the composing type’s object; the components are uniquely bound to it and cannout be
changed by any outside object. With aggregation, the component elements exits outside of the collection,
can be changed by other classes, and may even be components of other aggregates.
1.20 Polymorphism describes the way an object or variable may be treated in different contexts as though it
has a different type. For example, inheritance allows an argument of type B to be passed to a parameter
of type A if B extends A.

Read More

Transforming an ADT into java interface

Problem:

Implement the ADT below:
ADT: Polynomial
degree(): int
derivative(): Polynomial
equals(Point): Boolean
sum(Polynomial): Polynomial
toString(): String
valueAt(Real): Real

Output:

Not applicable.

Solution:

public class MyPolynomial implements Polynomial {
 private double[] c; // coefficients
 public MyPolynomial(double[] a) { // a[i] = coeffficient of x^i
 int n = c.length;
 c = new double[n];
 System.arraycopy(a, 0, c, 0, n);
 }
 public int degree() {
 return c.length - 1;
 }
 public Polynomial derivative() {
 double da[] = new double[c.length-1];
 for (int i=0; i<da.length; i++) {
 da[i] = (i+1)*c[i+1];
 }
 return new MyPolynomial(da);
 }
 public boolean equals(Object object) {
 if (object==this) {
 return true;
 } else if (!(object instanceof MyPolynomial)) {
 return false;
 }
 MyPolynomial that = (MyPolynomial)object;
 return java.util.Arrays.equals(that.c, this.c);
 }
 public Polynomial sum(Polynomial p) {
 if (!(p instanceof MyPolynomial)) {
 throw new IllegalArgumentException("use a MyPolynomial object");
 }
 MyPolynomial that = (MyPolynomial)p;
 double[] pc = that.c;
 int n = Math.max(c.length, pc.length);
 MyPolynomial q = new MyPolynomial(new double[n]);
 for (int i=0; i<n; i++) {
 q.c[i] = c[i] + pc[i];
 }
 return q;
 }
 public String toString() {
 StringBuilder buf = new StringBuilder();
 int n = c.length;
 if (n > 0 && c[0] != 0.0) {
 buf.append(c[0]);
 }
 if (n > 1 && c[1] != 0.0) {
 buf.append(String.format(" + %.2f", c[1]));
 }
for (int i=2; i<n; i++) {
 if (c[i] != 0.0) {
 buf.append(String.format(" + %.2f^%d", c[i], i));
 }
 }
 return buf.toString();
 }
 public double valueAt(double x) {
 double y = 0.0;
 for (int i=0; i<c.length; i++) {
 y += c[i]*Math.pow(x, i);
 }
 return y;
 }
}

Read More

How to implement an ADT in Java

Problem:

Implement the ADT below:
ADT: Line
contains(Point): Boolean
equals(Line): Boolean
isHorizontal(): Boolean
isVertical(): Boolean
slope(): Real
toString(): String
xIntercept(): Real
yIntercept(): Real

Output:

Not applicable.

Solution:

public class MyLine implements Line {
 private double m, b; // slope, intercept
 public static Line X_AXIS = new MyLine();
 private MyLine() {
 }
 public MyLine (double m, double b) {
 this.m = m;
 this.b = b;
 }
 public boolean contains(Point point) {
 double x = point.xCoordinate();
 double y = point.yCoordinate();
 return y == m*x + b;
 }
 public boolean equals(Object object) {
 if (object==this) {
 return true;
 } else if (!(object instanceof MyLine)) {
 return false;
 }
 MyLine that = (MyLine)object;
 return (that.m == this.m && that.b == this.b);
 }
 public boolean isHorizontal() {
 return m == 0.0;
 }
 public boolean isVertical() {
 return m == Double.POSITIVE_INFINITY || m==Double.NEGATIVE_INFINITY;
 }
 public double slope() {
 return m;
 }
 public String toString() {
 return String.format("y = %.2fx + %.2f", m, b);
 }
public double xIntercept() {
 if (isHorizontal()) {
 throw new RuntimeException("this line is horizontal");
 }
 return -b/m;
 }
 public double yIntercept() {
 if (isVertical()) {
 throw new RuntimeException("this line is vertical");
 }
 return b;
 }
}

Read More

Implement the ADT with a Java Example

Problem:

Implement the ADT below:
ADT: Point
amplitude(): Real
distanceTo(Point): Real
equals(Point): Boolean
magnitude(): Real
toString(): String
xCoordinate(): Real
yCoordinate(): Real

Output:

Not applicable.

Solution:

public class MyPoint implements Point {
 private double x, y;
 public static Point ORIGIN = new MyPoint();
 private MyPoint() {
 }
 public MyPoint(double x, double y) {
 this.x = x;
 this.y = y;
 }
 public double amplitude() {
 return Math.atan(y/x);
 }
 public double distanceTo(Point point) {
 if (point.equals(this)) {
 return 0.0;
 } else if (!(point instanceof MyPoint)) {
 throw new IllegalArgumentException("use a MyPoint object");
 } else {
 MyPoint that = (MyPoint)point;
 double dx = that.x - this.x;
 double dy = that.y - this.y;
 return Math.sqrt(dx*dx + dy*dy);
 }
 }
 public boolean equals(Object object) {
 if (object==this) {
 return true;
 } else if (!(object instanceof MyPoint)) {
 return false;
 }
 MyPoint that = (MyPoint)object;
 return (that.x == this.x && that.y == this.y); 
 }
 public double magnitude() {
 return Math.sqrt(x*x + y*y);
 }
public String toString() {
 return String.format("(%.2f,%.2f)", x, y);
 }
 public double xCoordinate() {
 return x;
 }
 public double yCoordinate() {
 return y;
 }
}

Read More

Translate ADT into java interface example 4

Problem:

Translate this ADT into a Java interface:
ADT: Polynomial
degree(): int
derivative(): Polynomial
equals(Point): Boolean
sum(Polynomial): Polynomial
toString(): String
valueAt(Real): Real

Output:

None

Solution:

public interface Polynomial {
 public int degree();
 public Polynomial derivative();
 public boolean equals(Object object);
 public Polynomial sum(Polynomial polynomial);
 public String toString();
 public double valueAt(double x);
}

Read More

Translate ADT into java interface example 3

Problem:

Translate this ADT into a Java interface:
ADT: Circle
area(): Real
center(): Point
circumference(): Real
contains(Point): Boolean
equals(Circle): Boolean
radius(): Real
toString(): String

Output:

None

Solution:

public interface Circle {
 public double area();
 public Point center();
 public double circumference();
 public boolean contains(Point point);
 public boolean equals(Object object);
 public double radius();
 public String toString();
}

Read More

Translate ADT into a Java interface Example 2

Problem:

Translate this ADT into a Java interface:
ADT: Line
contains(Point): Boolean
equals(Line): Boolean
isHorizontal(): Boolean
isVertical(): Boolean
slope(): Real
toString(): String
xIntercept(): Real
yIntercept(): Real

Output:

None.

Solution:

public interface Line {
 public boolean contains(Point point);
 public boolean equals(Object object);
 public boolean isHorizontal();
 public boolean isVertical();
 public double slope();
 public String toString();
 public double xIntercept();
 public double yIntercept();
}

Read More