CSci 2101: Review for Midterm II

Types and subtyping

Will the following program compile? If some fragments of it do not compile, comment them out (and explain why they don't compile). If you run the program after these lines (if any) have been commented out, what will happen? Show the results of all printing. If any run-time errors occur, clearly explain where they happen and why. Then comment out the error and continue with the program. 


import java.util.List;
import java.util.LinkedList;
import java.util.Stack;

/**
List<E> is an interface that extends Iterable<E>
and declares methods 
void add(int index, E item)
void remove(int index)
E get(int index)

LinkedList<E> is a class that implements List<E>

Stack<E> is another class that implements List<E>

It defines methods that are not declared in List, including:
boolean empty() 
E pop()
void push(E item) 
E peek() 
 **/

public class ReviewTypes {
    public static void main(String [] args) {
	List<Integer> numbers = new LinkedList<Integer>();
	
	numbers.add(0, 1);
	numbers.add(0, 2);
	numbers.remove(0);
	numbers.add(1, 3);

	System.out.println("Printing 1:");
	for (int number: numbers) {
	    System.out.println(number);
	}

	Stack<Integer> stack = new Stack<Integer>();
	stack.push(4);
	stack.push(5);
	stack.push(6);

	numbers = stack;

	System.out.println("Printing 2:");
	for (int number: numbers) {
	    System.out.println(number);
	}

	numbers.pop();
	System.out.println("numbers.get(0) = " + numbers.get(0));
	stack.pop();
	System.out.println("Printing 3:");
	for (int number: numbers) {
	    System.out.println(number);
	}

	LinkedList<Integer> anotherList = (LinkedList<Integer>) numbers;
	System.out.println("anotherList.get(0) = " + anotherList.get(0));	
	
    }
}

OurLinkedList methods

Write a method in OurLinkedList class according to the following specification. The method does not throw any exceptions.

It helps to start by writing test cases for the method. 


    /**
    * The method returns the number of occurrences of a given element in 
    * the list
    * @param element - the given element
    * @return - the number of occurrences of the element in the list
    **/
 
    public int count(E element) {
         return 0; // this is a stub. Replace it with your code
    }

You can use this implementation of OurLinkedList.

Correctness questions

Which ones of the following code fragments will compile successfully? If a fragment does not compile, what is wrong with it?

Example 1: 


    List<Integer> theList = new LinkedList<Integer>();	
    theList.add(0, "hi");
    theList.add(0, "bye");

Example 2: 


    public class Thing implements Comparable<Thing> {
        private int item;
	
        public Thing(int item) {
            this. item = item;
        }

        public Thing compareTo(Thing other) {
            if (item < other.item) {
                return this;
            } else {
                return other; 
            }
        }
    }

Example 3: 


    import java.util.List;
    import java.util.Stack;

    public class Inheritance {
        public static void main(String [] args) {
            Stack<String> stringStack = new Stack<String>();
            stringStack.push("green");
            stringStack.push("blue");
		
            List<String> stringList = stringStack;
		
            stringList.add("yellow");
		
            for (String str: stringList) {
                System.out.println(str);
            }
        }
    }

Iterators

Write an iterator for the following class Deck. Use the card implementation that implements Comparable<Card>. While Comparable is not needed in this example, it will be needed in the next problem.

The testing class for the iterator (currently throws an exception because the iterator method returns null). 


public class TestDeck {

    public static void main(String [] args) {
	Deck theDeck = new Deck();
	theDeck.shuffle(200);

	for (Card card: theDeck) {
	    System.out.println(card);
	}
    }

}

The Deck class: 


import java.util.Iterator;
import java.util.Random;

public class Deck implements Iterable<Card> {
    Card [] cards = new Card[52];
    Random rand = new Random();

    /**
       Constructor creates a deck of 52 cards
     **/
    public Deck() {
	String [] suits = {"Spades", "Hearts", "Diamonds", "Clubs"};
	String [] values = {"2","3","4","5","6","7","8","9","10","J","Q","K","A"};
	
	int k = 0;
	for (int i = 0; i < suits.length; ++i) {
	    for (int j = 0; j < values.length; ++j) {
		cards[k] = new Card(suits[i],values[j]);
		k++;
	    }
	}
    }

    /**
       shuffles the deck by switching cards numSwitches times
     **/
    public void shuffle(int numSwitches) {
	for (int i = 0; i < numSwitches; ++i) {
	    // pick two random cards:
	    int index1 = rand.nextInt(52);
	    int index2 = rand.nextInt(52);

	    // switch them:
	    Card temp = cards[index1];
	    cards[index1] = cards[index2];
	    cards[index2] = temp;
	}
    }

    public Iterator<Card> iterator() {
	return null;
    }

    // fill in iterator code here
}

Using compareTo

Use the Comparable Card implementation. Write a method that takes an array of cards and returns the number of out-of-order pairs according to the card compareTo method. An out-of-order pair in an array arr is a pair arr[i], arr[i+1] such that arr[i] is greater than arr[i+1] according to the natural ordering (i.e. the ordering given by compareTo). Your method must work with any Comparable type. Try it on an array of strings in addition to cards.

Sorting

Show the work of the following algorithms:

A past takehome test

This is a real takehome test from one of the past years.

CSci 2101 course web site.