CSci 2101: Review for Midterm II

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.


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.