Answer is C: O(n) Note: you will not get this type of question tomorrow.
Solutions for the previous review:
2. D
3. C
4. B
5. C
6. E
7. C
8. A
9. C
10. B
11. D
Topics:
Arrays – Concepts and applications
ArrayLists
Searches: linear and binary – Concepts and tracing, Big-O, average, best and worse cases.
Sorts: Insertion and Selection – Concepts and tracing, Big-O, average, best and worse cases.
Study Guide:
Self-Review problems, T/F questions, MC questions and SA exercises.
Homework assignment from last Friday
ArrayLists, type parameter, and for-each loop example
import java.util.ArrayList;
/**
This bank contains a collection of bank accounts.
*/
public class Bank
{
/**
Constructs a bank with no bank accounts.
*/
public Bank()
{
accounts = new ArrayList();
}
/**
Adds an account to this bank.
@param a the account to add
*/
public void addAccount(BankAccount a)
{
accounts.add(a);
}
/**
Gets the sum of the balances of all accounts in this bank.
@return the sum of the balances
*/
public double getTotalBalance()
{
double total = 0;
for (BankAccount a : accounts)
{
total = total + a.getBalance();
}
return total;
}
/**
Counts the number of bank accounts whose balance is at
least a given value.
@param atLeast the balance required to count an account
@return the number of accounts having least the given balance
*/
public int count(double atLeast)
{
int matches = 0;
for (BankAccount a : accounts)
{
if (a.getBalance() >= atLeast) matches++; // Found a match
}
return matches;
}
/**
Finds a bank account with a given number.
@param accountNumber the number to find
@return the account with the given number, or null if there
is no such account
*/
public BankAccount find(int accountNumber)
{
for (BankAccount a : accounts)
{
if (a.getAccountNumber() == accountNumber) // Found a match
return a;
}
return null; // No match in the entire array list
}
/**
Gets the bank account with the largest balance.
@return the account with the largest balance, or null if the
bank has no accounts
*/
public BankAccount getMaximum()
{
if (accounts.size() == 0) return null;
BankAccount largestYet = accounts.get(0);
for (int i = 1; i < accounts.size(); i++)
{
BankAccount a = accounts.get(i);
if (a.getBalance() > largestYet.getBalance())
largestYet = a;
}
return largestYet;
}
private ArrayList accounts;
}
ArrayLists, type parameter, for-each loop and Iterator another example
/**
* mrs.e
* 12/14/2018
*
* ArrayLists
* for-each loop
* Iterator
*
* */
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListIterator
{
public static void main( String[] args )
{
// add elements to an ArrayList
String[] pets = { "Puppy", "Kitten", "Gerbil", "Bunny", "Ferret" };
ArrayList< String > aList = new ArrayList< String >();
for ( String pet : pets )
aList.add( pet ); // for each loop - don't change the ArrayList
// add elements in removePets array to removeList
String[] removePets = { "Gerbil", "Bunny" };
ArrayList< String > removeList = new ArrayList< String >();
for ( String pet : removePets )
removeList.add( pet );
// print items of the list
System.out.println( "ArrayList: " );
for ( int count = 0; count < aList.size(); count++ )
System.out.printf( "%s ", aList.get( count ) );
// remove from list the pets contained in removeList
removePets( aList, removeList );
// print itmes of the list
System.out.println( "\n\nArrayList after calling removePets: " );
for ( String pet : aList )
System.out.printf( "%s ", pet );
} // end main
// remove pets in collection2 found in collection1
private static void removePets( ArrayList< String > collection1,
ArrayList< String > collection2 )
{
// get iterator
Iterator< String > iterator = collection1.iterator();
// loop while collection has items
while ( iterator.hasNext() )
{
if ( collection2.contains( iterator.next() ) )
iterator.remove(); // remove current pet
} // end while
} // end method removePets
} // end class ArrayListIterator
import java.util.ArrayList;
public class Program {
public static void main(String[] args) {
ArrayList list = new ArrayList<>();
list.add(101);
list.add(100);
list.add(99);
list.add(100);
list.add(99);
// Search for values.
int index = list.indexOf(100);
int lastIndex = list.lastIndexOf(100);
int notFound = list.indexOf(200);
// Display results.
System.out.println(index); // 1
System.out.println(lastIndex); // 3
System.out.println(notFound); // -1
}
}
Output
1
3
-1
§ § § § § §
More advanced topics in this link. (Optional)
ListIterator, indexOf, Iterator, List Interface
[collapse]
ArrayList<E>()
Constructs an empty list with an initial capacity of ten.
boolean add(E obj)
Appends the specified element to the end of this list.
void add(int index, E obj)
Inserts the specified element at the specified position in this list.
E get(int index)
Returns the element at the specified position in this list.
int indexOf(Object obj)
Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
boolean isEmpty()
Returns true if this list contains no elements.
int size()
Returns the number of elements in this list.
ListIterator<E> listIterator()
Returns a list iterator over the elements in this list (in proper sequence).
E remove(int index)
Removes the element at the specified position in this list.
boolean remove(Object o)
Removes the first occurrence of the specified element from this list, if it is present.
//********************************************************************
// DestinysChild.java Author: Lewis/Loftus/Cocking
//
// Demonstrates the use of a ArrayList object.
//********************************************************************
import java.util.ArrayList;
public class DestinysChild
{
//-----------------------------------------------------------------
// Stores and modifies a list of band members.
//-----------------------------------------------------------------
public static void main (String[] args)
{
ArrayList band = new ArrayList();
band.add ("Michelle");
band.add ("Kelly");
band.add ("Beyonce");
band.add ("Farrah");
System.out.println (band);
int location = band.indexOf ("Farrah");
band.remove (location);
System.out.println (band);
System.out.println ("At index 1: " + band.get(1));
System.out.println (band);
System.out.println ("Size of the band: " + band.size());
}
}
[Michelle, Kelly, Beyonce, Farrah]
[Michelle, Kelly, Beyonce]
At index 1: Kelly
[Michelle, Kelly, Beyonce]
Size of the band: 3
Two ways to iterate through the elements of a collection in java:
By Iterator interface.
By for-each loop.
//********************************************************************
// Recipe.java Author: Lewis/Loftus/Cocking
//
// Demonstrates the use of a ListIterator to iterate through the
// elements of an ArrayList.
//********************************************************************
import java.util.ArrayList;
import java.util.ListIterator;
public class Recipe
{
//-----------------------------------------------------------------
// Stores and then prints a list of ingredients for a recipe.
//-----------------------------------------------------------------
public static void main (String[] args)
{
ArrayList ingredients = new ArrayList();
ingredients.add ("flour");
ingredients.add ("sugar");
ingredients.add ("cocoa");
ingredients.add ("oil");
ingredients.add ("butter");
ingredients.add ("eggs");
ingredients.add ("baking soda");
System.out.println ("To make a chocolate cake, use the following " +
ingredients.size() + " ingredients:");
// traversing ArrayList by Iterator
ListIterator iterator = ingredients.listIterator();
while (iterator.hasNext())
System.out.println(iterator.next());
// traversing ArrayList using the "for-each" loop
for(String obj:ingredients)
System.out.println(obj);
}
}
To make a chocolate cake, use the following 7 ingredients:
flour
sugar
cocoa
oil
butter
eggs
baking soda
Classwork/Homework:
1. Create a class DataSet of BankAccounts. The constructor creates an ArrayList of BankAccount(s). Write the test class to add, delete and print (use the for-each loop) bank accounts. Your driver should have at least 3 BankAccount objects. Make any changes necessary to have the DataSet ADT implemented with an ArrayList. Also, change the comments to fit the modifications to the it.
DataSet with ArrayList
/**
Computes the average of a set of data values.
*/
public class DataSet
{
/**
Constructs an empty data set with no BankAccount objects.
*/
public DataSet()
{
sum = 0;
count = 0; // Warning: Is "count" necessary?
maximum = 0; // Warning: this should not be a numeric type!!
// create an object of the ArrayList dataSet
}
/**
Adds a BankAccount object to the data set
@param x a BankAccount object
*/
public void add(BankAccount bank)
{
// add object to ArrayList
sum = sum + bank.getBalance();
if (count == 0 || maximum.getBalance() < x.getBalance()) maximum = x;
count++;
}
/**
Gets the average of the added BankAccount balances.
@return the average or 0 if no data has been added
*/
public double getAverage()
{
if (count == 0) return 0;
else return sum / count; // Warning
}
/**
Gets the largest of the added data. // changes must be made here
@return the maximum or 0 if no data has been added
*/
public BankAccount getMaximum()
{
return maximum;
}
/**
Prints the balance for each element of the added data in the ArrayList.// Warning
@return the average or 0 if no data has been added
*/
public void printDataSet()
{
// implement the code to print the elements of the ArrayList datSet. Add more specific comments
// use the for-each loop
}
private double sum;
private BankAccount maximum;
private int count;
private ArrayList dataSet;
}
[collapse]
Create a class Purse (see below) that contains an ArrayList of Coin(s). Write the test class to add, delete, and print coins. Make any changes necessary to have the Purse class implemented with an ArrayList. Also, change the comments to fit the modifications to the ADT.
/**
A coin with a monetary value.
*/
public class Coin
{
/**
Constructs a coin.
@param aValue the monetary value of the coin.
@param aName the name of the coin
*/
public Coin(double aValue, String aName)
{
value = aValue;
name = aName;
}
/**
Gets the coin value.
@return the value
*/
public double getValue()
{
return value;
}
/**
Gets the coin name.
@return the name
*/
public String getName()
{
return name;
}
public boolean equals(Object otherObject)
{
Coin other = (Coin)otherObject;
return name.equals(other.name)
&& value == other.value;
}
private double value;
private String name;
}
Modify the Purse class to be implemented with ArrayList<Coin> and to use a for-each loop.
Implement the following methods in the Purse class:
/**
Counts the number of coins in the purse
@return the number of coins
*/
public int count()
{
}
/**
Tests if the purse has a coin that matches
a given coin.
@param aCoin the coin to match
@return true if there is a coin equal to aCoin
*/
public boolean find(Coin aCoin)
{
}
/**
Counts the number of coins in the purse that match
a given coin.
@param aCoin the coin to match
@return the number of coins equal to aCoin
*/
public int count(Coin aCoin)
{
}
/**
Finds the coin with the largest value.
(Precondition: The purse is not empty)
@return a coin with maximum value in this purse
*/
pulic Coin getMaximum()
{
}
NOTE: Use the “for-each” loop in the implementation.
Classwork:
Write a telephone lookup program, TelephoneDirectory_YI.java. Create a class Telephone with two instance fields, number and name. You have the choice of creating your own data or using the data below to create an array of 100 Telephone objects in random order. TelephoneDirectory handles lookups by name and also reverse lookups by phone number. Use a binary search for both lookups. Make sure you include the test/driver class with enough activity to show your work.
NOTE: create a text file with random data in the following format:
Last name, First name, area code "-" exchange "-" extension
The following java program might help you with “some” of the code you need to create the text data file.
PhoneNumber
/******************************************************************************
* Compilation: javac PhoneNumber.java
* Execution: java PhoneNumber
* Dependencies:
*
* Immutable data type for US phone numbers.
*
******************************************************************************/
import java.util.HashSet;
/**
* The {@code PhoneNumber} class is an immutable data type to encapsulate a
* U.S. phone number with an area @code (3 digits), exchange (3 digits),
* and extension (4 digits).
*
* For additional documentation,
* see Section 1.2 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public final class PhoneNumber {
private final int area; // area @code (3 digits)
private final int exch; // exchange (3 digits)
private final int ext; // extension (4 digits)
/**
* Initializes a new phone number.
*
* @param area the area @code (3 digits)
* @param exch the exchange (3 digits)
* @param ext the extension (4 digits)
*/
public PhoneNumber(int area, int exch, int ext) {
this.area = area;
this.exch = exch;
this.ext = ext;
}
/**
* Compares this phone number to the specified phone number.
*
* @param other the other phone number
* @return {@code true} if this phone number equals {@code other};
* {@code false} otherwise
*/
@Override
public boolean equals(Object other) {
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
PhoneNumber that = (PhoneNumber) other;
return (this.area == that.area) && (this.exch == that.exch) && (this.ext == that.ext);
}
/**
* Returns a string representation of this phone number.
*
* @return a string representation of this phone number
*/
@Override
public String toString() {
// 0 for padding with digits with leading 0s
return String.format(“(%03d) %03d-%04d”, area, exch, ext);
}
/**
* Returns an integer hash code for this phone number.
*
* @return an integer hash code for this phone number
*/
@Override
public int hashCode() {
return 31 * (area + 31 * exch) + ext;
}
/**
* Unit tests the {@code PhoneNumber} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
PhoneNumber a = new PhoneNumber(609, 258, 4455);
PhoneNumber b = new PhoneNumber(609, 876, 5309);
PhoneNumber c = new PhoneNumber(609, 555, 5309);
PhoneNumber d = new PhoneNumber(215, 876, 5309);
PhoneNumber e = new PhoneNumber(609, 876, 5309);
StdOut.println(“a = ” + a);
StdOut.println(“b = ” + b);
StdOut.println(“c = ” + c);
StdOut.println(“d = ” + d);
StdOut.println(“e = ” + e);
import java.util.ArrayList;
/**
This class computes the average of a set of data values.
*/
public class DataSet
{
/**
Constructs an empty data set.
*/
public DataSet()
{
create ArrayList
/* write your code here */
}
/**
Adds a data value to the data set
@param x a data value
*/
public void add(double x)
{
/* write your code here */
}
/**
Gets the average of the added data.
@return the average or 0 if no data has been added
*/
public double getAverage()
{
/* write your code here */
}
private ArrayList data;
}
ArrayLists with Generic Types
The type ArraList identifies an array list of bank accounts.
The angle brackets around the BankAccount type tell you that BankAccount is a type parameter.
Use an ArrayList whenever you want to collect objects of type T.
However, you cannot use primitive types as type parameters — there is no ArrayList or ArrayList.
Wrapper objects can be used anywhere that objects are required instead of primitive type values. For example, you can collect a sequence of floating-point numbers in an ArrayList.
Conversion between primitive types and the corresponding wrapper classes is automatic. This process is called auto-boxing (even though auto-wrapping would have been more consistent).
For example, if you assign a number to a Double object, the number is automatically “put into a box”, namely a wrapper object.
Double d = 29.95; // auto-boxing; same as Double d = new Double(29.95);
Wrapper objects are automatically “unboxed” to primitive types.
double x = d; // auto-unboxing; same as double x = d.doubleValue();
ArrayList data = new ArrayList();
data.add(29.95);
double x = data.get(0);
Classwork:
1. Change DestinysChild and Recipe classes to use parameter types.
2. Create a class DataSet of BankAccounts. The constructor creates an ArrayList. Write the test class to add, delete and print bank accounts.
3. Create a class Purse that contains an ArrayList of Coin(s). Write the test class to add, delete, and print coins.
The ArrayList class is part of the java.util package of the Java standard class library.
It provides a service similar to an array in that it can store a list of values and reference them by an index. However, whereas an array remains a fixed size throughout its existence, an ArrayList object dynamically grows and shrinks as needed.
A data element can be inserted into or removed from any location (index) of an ArrayList object with a single method invocation.
The ArrayList class is part of the Collections API, a group of classes that serve to organize and manage other objects.
Unlike an array, an ArrayList is not declared to store a particular type.
An ArrayList object stores a list of references to the Object class.
A reference to any type of object can be added to an ArrayList object.
Because an ArrayList stores references, a primitive value must be stored in an appropriate wrapper class in order to be stored in an ArrayList. Figure 6.8 lists several methods of the ArrayList class.
Look in edmodo.com for the project due: (No partners)
Design and implement a class called Card that represents a standard playing card. Each card has a suit and a face value. A Card ADT represents a standard playing card.
Create a class called DeckOfCards that stores 52 objects of the Card class using ArrayList. Include methods to
Shuffle the deck. The shuffle method should assume a full deck.
Deal a card
Report the number of cards left in the deck
In addition:
Write the method “printForEach” to print all the cards in the deck using the “for-each” loop.
Write the method “printIterator” to print all the cards in the deck using the “ListIterator“.
Create a driver class with a main method that deals each card from a shuffled deck, printing each card as it is dealt.
/**
A coin with a monetary value.
*/
public class Coin
{
/**
Constructs a coin.
@param aValue the monetary value of the coin.
@param aName the name of the coin
*/
public Coin(double aValue, String aName)
{
value = aValue;
name = aName;
}
/**
Gets the coin value.
@return the value
*/
public double getValue()
{
return value;
}
/**
Gets the coin name.
@return the name
*/
public String getName()
{
return name;
}
public boolean equals(Object otherObject)
{
Coin other = (Coin)otherObject;
return name.equals(other.name)
(and) value == other.value;
}
private double value;
private String name;
}
import java.util.ArrayList;
/**
A purse holds a collection of coins.
*/
public class Purse
{
/**
Constructs an empty purse.
*/
public Purse()
{
coins = new ArrayList();
}
/**
Add a coin to the purse.
@param aCoin the coin to add
*/
public void add(Coin aCoin)
{
coins.add(aCoin);
}
/**
Get the total value of the coins in the purse.
@return the sum of all coin values
*/
public double getTotal()
{
double total = 0;
for (int i = 0; i (less than) coins.size(); i++)
{
Coin aCoin = (Coin)coins.get(i);
total = total + aCoin.getValue();
}
return total;
}
private ArrayList coins;
}
How long does a linear search take? If we assume that the element v is present in the array a, then the average search visits n/2 elements, where n is the length of the array. If it is not present, then all n elements must be inspected to verify the absence. Either way, a linear search is an O(n) algorithm.
A binary search is an O(log(n)) algorithm.
That result makes intuitive sense. Suppose that n is 100. Then after each search,
the size of the search range is cut in half, to 50, 25, 12, 6, 3, and 1. After seven comparisons we are done. This agrees with our formula, because log2(100) ≈ 6.64386, and indeed the next larger power of 2 is 27 = 128.
Selection Sort: Let us count the number of operations that the program must carry out to sort an array with the selection sort algorithm. We don’t actually know how many machine operations are generated for each Java instruction, or which of those instructions are more time consuming than others, but we can make a simplification. We will simply count how often an array element is visited. Each visit requires about the same amount of work by other operations, such as incrementing subscripts and comparing values.
Let n be the size of the array. First, we must find the smallest of n numbers. To achieve that, we must visit n array elements. Then we swap the elements, which takes two visits. (You may argue that there is a certain probability that we don’t need to swap the values. That is true, and one can refine the computation to reflect that observation. As we will soon see, doing so would not affect the overall conclusion.) In the next step, we need to visit only n − 1 elements to find the minimum. In the following step, n − 2 elements are visited to find the minimum. The last step visits two elements to find the minimum. Each step requires two visits to swap the elements. Therefore, the total number of visits is
n + 2 + (n − 1) + 2 + … + 2 + 2 =
n + (n − 1) + … + 2 + (n − 1) ⋅ 2 =
2 + … + (n-1) + n + (n – 1) ⋅ 2 =
n (n – 1)
——— – 1 + (n – 1) ⋅ 2
2
multiplying out and collecting terms of n:
1 5
— n2 + — n – 3
2 2
Let’s simplify the analysis further:
When you plug in a large value for n (say 1,000 or 2,000)
1
— n2 is 500,000 or 2,000,000
2
5
— n – 3 is only 2,497 or 4,997. Neither of these two number would have an impact on
2
the magnitude of 500,000 and 2,000,000. We can just ignore them for the purpose of the analysis.
Further more, we will show that 1/2 in the square term does not have much of an effect in our analysis
We are not interested in the actual count of visits for a single n. We want to compare the ratios of counts for different values of n.
If we want to compare the number of visits required to sort an array of 1,000 elements to an array of 2,000, by what factor the number of visits would increase?
The factor of 1/2 cancels out in comparison of this kind. We will simply say, “The number of visits is of order n2“. That way, we can easily see that the number of comparisons increases fourfold when the size of the array doubles: (2n)2 = 4n2.
To indicate that the number of visits is of the order n2, we will use the big-Oh notation: O(n2)
The big-Oh notation is about the fastest-growing term, n2, and ignores its constant coefficient, no matter how large or small it may be.
It is safe to say that the number of machine operations, and the actual amount of time that the computer spends on them, is approximately proportional to the number of element visits. For argument sake, we could say that there are about 10 machine operations for every element visit. Then, then number of machine operations should be in the neighborhood of 10 x (1/2) n2. Using the big-Oh notation, we can say that the number of machine operations required to sort is in the order of n2 or O(n2) and so is the sorting time.
If an array is increase by a factor of 100, the sorting time increases by a factor of 10,000. To sort an array of a million elements, takes 10,000 times as long as sorting an array of 10,000 items.If 10,000 items can be sort in about half a second, then sorting one million items requires well over an hour.
1. If you increase the size of a data set tenfold, how much longer does it take to sort it with the selection sort algorithm?
2. How large does n need to be so that (1/2)n2 is bigger than (5/2)n – 3?
Classwork:
Write a class Customer with customer number, name, address, and balance.
Write a class Clients. Clients class has an ArrayList to keep all the customers information together. This class has the following methods:
1. add – this method adds a new customer to the ArrayList
2. remove – this method removes the customer from the ArrayList
3. update – this method changes a customer’s balance.
4. getTotal – this method finds the total of all the customers balances.
5. getMaxBal – this method finds the customer with the largest balance and returns the customer object.
6. print – this method prints all the customers information.
7. sortBalance – this method creates a new ArrayList with the customers sorted by balance. This methods prints the customers in sorted order.
Write a driver class to show all the methods above.
NOTE: use generics and for-each loops
