CSC 402

Winter 2015

Craig Miller

• Home
• Basic Information
• Grades and Policies
• Schedule

Weekly Notes

• Week 1
• Week 2
• Week 3
• Week 4
• Week 5
• Week 6
• Week 7
• Week 8
• Week 9
• Week 10

Assignments

• Assignment 1
• Assignment 2
• Assignment 3
• Assignment 4
• Midterm
• Assignment 5
• Assignment 6
• Assignment 7

Assignment 3
Collections with Generics and Iterators
Submit before 11:30 PM Saturday January 31

Overview

Using Queues

Use the Queue class in the alg13 package to simulate a simplified version of the playing card game frequently called War. The Queue represents a player's packet of cards and consist of Card objects, using the Card class provided in class.

Your version should have the following (simpler) rules:

1. When there is a tie, randomly choose (50% probability) which "player" winse.
2. Randomly determine (50% probability) the order of the cards that are randomly placed at the end of the random player's queue.

Rule #2 is important. Similar to the findings of this paper on the game, our simple version of the game won't terminate without the random placement.

Call your class War. Your main method should simulate 10,000 games and report the average number of rounds before the game ends. Expect to see an average in the 600-700 range.

Using Stacks

Use the Stack class in the alg13 package to check if a file has matching HTML tags consistent with the XHTML standard. You may assume the following simplications about the file:

1. The file only consists of simple opening and closing tags.
2. Tags just have simple identifiers (no attributes).
3. All tags are separated with white space (so that the readAllStrings successfully tokenizes and separates the tags).

Using a stack of Strings, the following algorithm tests for properly nested XHTML tags:

1. If the tag is an opening tag, push its identifier on the stack.
2. If the tag is a closing tag, pop the stack and test if the resulting identifier matches that of the closing tag (if not, it's not properly nested).
3. If end of the file is reached and the stack is empty, then the file has properly nested tags (assuming all tests were successful).

For this task, call your class WebParse. Define a static method called checkHTML that takes a String as an argument and returns an integer. The String should specify the name of a file (URL or local file). The method should return the number of matching tags if they are properly nested. If the tags are not properly nested, it should return -1.

The following methods are helpful and greatly simplify the task:

  public static boolean isOpeningTag(String token)
  {
    return token.matches("<\\w+>");
  }

  public static boolean isClosingTag(String token)
  {
    return token.matches("</\\w+>");
  }
  
  public static String getTagIdentifier(String token)
  {
    Pattern tagPattern = Pattern.compile("</?(\\w+)>");
    Matcher m = tagPattern.matcher(token);
    if (m.matches()) {
      return m.group(1);
    }
    else {
      return "";
    }
  }

Here's link to a proper XHTML file and a link to an improper XHTML file. You'll need to right-click and view source to see actual code.

Collection with generic type and iterator

Write a Jar class that supports the same methods as the MarbleJar class, except this Jar class should work for any type. Also, add an iterator method so that it implements the iterable interface.

The Jar class should automatically resize its underlying array by doubling it as needed.

Your main method should provide a comprehensive set of test cases.

Submission

Zip up your assn3 package and submit it as assn3.zip on D2L. If you work with one or two other people, only one person needs to submit. In the submissions comments, indicate who you worked with.