CSSE 220 – Object-Oriented Software Development

Homework 25

Objectives

Start developing an intuition for algorithm analysis. Experiment with sorting and searching. More design practice.

Tasks

  1. Reading and Quiz:
    1. Complete the assigned reading for the next session: §15.4, 16.1, and 16.2. As you read, see if you can answer the self-check questions. If there is something you do not understand, make note of it so you can ask about it.
    2. Complete the ANGEL quiz over Chapter 15.
  2. Solo Work:
    1. This part is not required to be turned in  (at least, not yet), but problem below is something that you should know how to do sometime before the Final Exam.
      1. Implement a static split method that is
        2. similar to the instance method from the String class. It returns an array of tokens from the argument String. Each token is a substring of non-whitespace characters that is surrounded by whitespace in the argument String. A whitespace character is any character whose ASCII code is less than or equal to that of the space character, ' '.
        public static String[] split(String str)
      2. A class provides a single constructor, which is private.  Why would we ever want to do this?
      3. Write generic methods min and max, each of which accepts two parameters of the same Comparable type, and returns the smallest and largest, respectively. Test your method on the String type.
      4. write a generic method min, which takes an array of an arbitrary Comparable type, and returns the smallest element of the array. Test your method on the String type.
      5. write a generic method max2, which takes an array of an arbitrary Comparable type, and returns an array of the two largest elements of that array. Test your method on the String type.
    2. Your solo programming work for this part must be done in the FunctionObjectsAndSorting project inside Eclipse. You should have checked out this project for the previous class session.
    3. For this task you’ll be working on the sortExercise package. Note that I initially neglected to put this package in the project.  If you right-click on the project name and choose Team→Update, you should then see the sortExercise package and its one .java file.
      1. Study the program there and experiment with it.
      2. (2 points) Briefly explain the algorithm that is implemented.  Enter your answer in the javadoc comment of the sort() method.
      3. (2 points) Enter a brief javadoc comment describing what the combine() method does.
      4. (4 points) What is the best and worst case running time of this algorithm (as a function of n)? Provide formulae for the number of times the  compareTo() method gets called and perform the big-Oh analysis of the running times. Enter your answer as a comment at the end of the program.
  3. Minesweeper Team Assignment:
    1. Read the MineSweeper assignment.
    2. Class and responsibility brainstorming.  Goal: A list of possible classes and as-complete-as-you-can-get list of responsibilities of the program.
    3. CRC cards, assigning each responsibility to a class, and listing the collaborating classes (whenever you discover a collaborator, ask what responsibility the collaborating class must assume in order to do the collaboration, and write that on the collaborating class's CRC card.
    4. A UML class diagram, showing the relationships among your classes, and reflecting what you discovered when you wrote your CRC cards.  See the Minesweeper assignment for more details.
    5. User stories for MineSweeper cycle 1, which begins on the day of Session 26, and ends at 8:05 on the day of Session 27.

 

Turn-in Instructions

Turn-in your individual work by committing it to your SVN repository, and team work to team repository.  Do the CHapter 15 Quiz on ANGEL.  Bring your MineSweeper CRC cards to class.