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 result of all printing. If any run-time errors occur, clearly explain where they happen and why.


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

Iterators

Write an iterator for the following class Deck. Use the card implementation that implements Comparable<Card>, but not the one that extends KeyRange. 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.


CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.