Stacks – Linked List vs Array

Classwork:

September 18th, 2015

Implementing a Maze Solver Using Stacks

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.

Stack.java

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.

Maze Solver Tracing 2

Recursive N-queen Problem – An implementation

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;>

Polish Notation Stack Calculator

Postfix

Iterable Interface Example

java.lang.Iterable Interface Example

…

…

Posted by: Prasad Saya in Iterator January 30th, 2015 0 2282 Views

This article shows an example of Iterable interface. This is defined in java.lang package and was introduced with Java 5. The Iterable is defined as a generic type; Iterable<T>, where T type parameter represents the type of elements returned by the iterator.

An object that implements this interface allows it to be the target of the “foreach” statement. The for-each loop is used for iterating over arrays, collections etc. Collection classes and classes where iterations are useful implement this interface.

Before the iterable’s for-each loop was introduced, a way to iterate is to use the for(;;) loop or to use an Iterator; typically the Iterator could be acquired by invoking a collection object’s iterator() method. The iterator has been in Java since Java 1.2.

The Iterable interface provides a clean approach to coding the iteration functionality. An example shows iterating over a List collection with String object elements:

List stringList = new ArrayList<String>();
stringList.add("a");
stringList.add("b");
stringList.add("c");

for (String s : stringList) {
    System.out.println(s);
}

for (int i = 0; i < stringList.size(); i++) {

    System.out.println(stringList [i]);
}

Iterator iter = stringList.iterator();

while (iter.hasNext()) {

    System.out.println(iter.next());

}

…

Note that there is also a possibility of introducing a bug in the above two code snippets, because of the details.

1. Example

The following example class implements the Iterable interface. The class takes an input array of any type and iterates it in a for-each loop and in reverse order.

Oracle doc

The Iterable interface has one method to override: Iterator<T> iterator().

The example has the iterable implementation MyIterable.java and a tester class MyIterableTester.java.

1.1. The code

MyIterable.java

import java.util.List;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Collections;

public class MyIterable implements Iterable {

    private List list;
    public MyIterable(T [] t) {
        list = Arrays.asList(t);
        Collections.reverse(list);
    }
    @Override
    public Iterator iterator() {
        return list.iterator();
    }

}

…MyIterableTester.java

public class MyIterableTester {

    public static void main(String [] args) {

        Integer [] ints = {1, 2, 3};

        MyIterable myList = new MyIterable<>(ints);

        for (Integer i : myList) {
            System.out.println(i);
        }

    }

}

…

1.2. The output

3
2
1

…

2. Download Java Source Code

This was an example of java.lang.Iterable Interface Example.

Download
You can download the full source code of this example here: IterableExample.zip

BSTs – Proposition

2-3 search trees
Screen Shot 2015-02-27 at 7.46.26 AM

We introduce in this section a type of binary search tree where costs are guaranteed to be logarithmic. Our trees have near-perfect balance, where the height is guaranteed to be no larger than 2 lg N.

Proposition.

Search and insert operations in a 2-3 tree with N keys are guaranteed to visit at most lg N nodes.

However, we are only part of the way to an implementation. Although it would be possible to write code that performs transformations on distinct data types representing 2- and 3-nodes, most of the tasks that we have described are inconvenient to implement in this direct representation.

Implementing Binary Search Trees

Binary Trees

Homework:
Implementing Binary Search Trees: With Links

1. How are the constructors implemented?
2. Write the pseudocode for public void addElement (T element). Draw an example of adding an element to a BST.
3. Write the pseudocode for public T removeElement (T targetElement). Draw an example of removing an element to a BST.
4. Write the pseudocode for public void removeAllOccurrences (T targetElement).

LispList interface

November 13th, 2014

Linked lists. A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list. To implement a linked list, we start with a nested class that defines the node abstraction

private class Node {
   Item item;
   Node next;
}

Homework:
LispList interface and the EmptyList and NonEmptyList classes implementations.
Write a test program that constructs a list and prints it.
From Wikipedia:
Lisp (historically, LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized Polish prefix notation. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older (by one year).
The name LISP derives from “LISt Processing”. Linked lists are one of Lisp language’s major data structures, and Lisp source code is itself made up of lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or new domain-specific languages embedded in Lisp.