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
-
Reading and Quiz:
- 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.
- Complete the ANGEL quiz over Chapter 15.
-
Solo Work:
-
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.
- Implement a static
split
method that is 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)
- A class provides a single constructor, which is
private. Why would we ever want to do this?
-
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. -
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. -
write a generic method
m
ax2, 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.
-
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.
-
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.
- Study the program there and experiment with it.
- (2 points) Briefly explain the algorithm that is
implemented. Enter your answer in the javadoc
comment of the
sort()
method.
- (2 points) Enter a brief javadoc comment
describing what the
combine()
method
does.
- (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.
- Minesweeper
Team Assignment:
- Read the
MineSweeper assignment.
- Class and responsibility brainstorming. Goal: A list
of possible classes and as-complete-as-you-can-get list of
responsibilities of the program.
- 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.
- 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.
- 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.