Dynamic shrinking. With the array implementations of stack and queue, we doubled the size of the array when it wasn’t big enough to store the next element. If we perform a number of doubling operations, and then delete a lot of elements, we might end up with an array that is much bigger than necessary. Implement the following strategy: whenever the array is 1/4 full or less, shrink it to half the size. Explain why we don’t shrink it to half the size when it is 1/2 full or less.
Stack + max. Create a data structure that efficiently supports the stack operations (pop and push) and also return the maximum element. Assume the elements are integers or reals so that you can compare them.
To consider the task of implementing iteration, we start with a snippet of client code that prints all of the items in a collection of strings, one per line:
Stack collection = new Stack();
...
for (String s : collection)
StdOut.println(s);
...
This foreach statement is shorthand for the following while statement:
Iterator i = collection.iterator();
while (i.hasNext()) {
String s = i.next();
StdOut.println(s);
}
To implement iteration in a collection:
Include the following import statement so that our code can refer to Java’s java.util.Iterator interface:
import java.util.Iterator;
Add the following to the class declaration, a promise to provide an iterator() method, as specified in the java.lang.Iterable interface:
implements Iterable
Implement a method iterator() that returns an object from a class that implements the Iterator interface:
public Iterator iterator() {
return new ListIterator();
}
Implement a nested class that implements the Iterator interface by including the methods hasNext(), next(), and remove(). We always use an empty method for the optional remove() method because interleaving iteration with operations that modify the data structure is best avoided.
The nested class ListIterator in Bag.java illustrates how to implement a class that implements the Iterator interface when the underlying data structure is a linked list.
The nested class ArrayIterator in ResizingArrayBag.java does the same when the underlying data structure is an array.
Assignments:
Implement the ADT Set, Set_YI.java with the methods below. The Set ADT uses a LinkedList structure. In mathematics, a Set is a well-defined collection of distinct objects, considered as an object in its own right. In this implementation of Set, the Set ADT behaves like a LinkedList but it doesn’t allow duplicates. Create a Node class.
add(E e)
Ensures that this collection contains the specified element.
addAll(collection<?> c)
Adds all of the elements in the specified collection to this set if they’re not already present. The alternate version is to add all elements from Set_YI.
void clear()
Removes all of the elements from this set (optional operation).
boolean contains(Object o)
Returns true if this set contains the specified element.
boolean containsAll(collection<?> c)
Returns true if this set contains all of the elements of the specified collection.
boolean equals(Object o)
Compares the specified object with this set for equality. The alternate version is to compare objects of Set_YI.
boolean isEmpty()
Returns true if this set contains no elements.
Iterator<E> iterator()
Returns an iterator over the elements in this set.
boolean remove(Object o)
Removes the specified element from this set if it is present (optional operation).
boolean removeAll(collection<?> c) Removes from this set all of its elements that are contained in the specified collection (optional operation). The ? could be whatever you choose.
int size()
Returns the number of elements in this set (its cardinality).
Using what you learned about solving a maze with the previous tracing assignment, implement a maze solver using the Stack ADT you already implemented or the one supplied in the university resource site.
You can choose the name of your program but make sure you follow the guidelines discussed in the CS classes. The final solution should be a stack with the steps to take from start to end of any maze similar to the given below:
In your previous assignment, you should have a trace similar to the two samples from Leon and Kamola. Pay attention to the final product.
Know a bit about the Queen piece in a game of Chess
A solution for the “8 queens” problem
Numberphile video:
You can have access to all the Lynda.com resources with your own Princeton Public Library card.
The problem: Design and implement a recursive program that solves the Non- Attacking Queens problem. That is, write a program to determine how eight queens can be positioned on an eight-by-eight chessboard so that none of them are in the same row, column, or diagonal as any other queen. There are no other chess pieces on the board.
Assignment:
If you already implemented the solution to the problem, answer the following questions:
How does your implementation compare to the one below?
Is your implementation better than this one?
What is the time complexity (for now we can say the big-O notation)?
If you have not implemented yet, do the following:
Trace the code for 4 queens. It only has 2 solutions but 1 unique.
Explain how the implementation works
What is the time complexity (for now we can say the big-O notation)?
//********************************************************************
//
// A recursive program that solves the Non-attacking Queens problem.
//********************************************************************
public class NonAttackingQueens {
int[] queens; // Queen i is always placed in row i. The
// column is variable.
// queens[i] represents the column of the ith row
// where the ith queen is
final int NUM_QUEENS = 8;
public NonAttackingQueens()
{
queens = new int[NUM_QUEENS];
}
//-----------------------------------------------------------------
// Returns true if a queen queenNumber can be placed in column
//-----------------------------------------------------------------
boolean canPlace(int queenNumber, int column)
{
for (int row = 0; row < queenNumber; row++) // check all rows above queenNumber row
{
if (queens[row] == column) // in the same column
return false;
if (Math.abs(queens[row] - column) == Math.abs(row - queenNumber)) // same diagonal
return false;
}
return true;
}
//-----------------------------------------------------------------
// Starting with the row represented by queenNumber, find all correct
// placements in the row and below the row.
//-----------------------------------------------------------------
public void solve(int queenNumber)
{
for (int column = 0; column < NUM_QUEENS; column++) // iterate through all columns
{
if (canPlace(queenNumber, column)) // queen can be placed in current column
{
queens[queenNumber] = column; // place queen in current column
if (queenNumber + 1 >= NUM_QUEENS) // solved
printSolution();
else // keep looking
solve(queenNumber + 1);
}
}
}
//-----------------------------------------------------------------
// Computes and displays all solutions to the problem
//-----------------------------------------------------------------
public void showSolutions()
{
solve(0); // start with the first row
}
//-----------------------------------------------------------------
// Prints a grid showing the position of the queens on the chessboard.
// Queen = X
// Empty space = O
//-----------------------------------------------------------------
private void printSolution()
{
int column;
for (int row=0; row<num_queens; row++)="" {="" for="" (column="0;" column<num_queens;="" column++)="" if="" (queens[row]="=" column)="" system.out.print("="" x");="" else="" 0");="" system.out.print("\n");="" }="" system.out.println("\n-----------------------");="" public="" static="" void="" main="" (string="" args[])="" new="" nonattackingqueens().showsolutions();="" <="" pre=""></num_queens;>
