CSSE 220 – Object-Oriented Software Development

Homework 23

Objectives

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

Tasks

  1. Complete the assigned reading for the next session: §15.1–3. (See schedule for topics to focus on.) 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. Solo Work: No Late Days. We’ll be going over the answers to the sortExercise below in class next session, so note late days are allowed on this assignment.
    1. Your solo work for this part must be done in the SortingAndSearching project inside Eclipse. Use the SVN Repository Exploring perspective to check out this project, then switch back to the Java perspective.

    2. For this tasks, you’ll be working in the Loops class of the counting package. For each method in that class, add a comment stating how many times the count variable is incremented in the best and worst cases. Give your answers as closed form formulae in n, the length of the input array. One of the comments is given as an example.

      You may add profiling code if you wish, but should not change the behavior of the given methods.

    3. For this task you’ll be working on the sortExercise package.
      1. Study the program there and experiment with it.
      2. Briefly explain the algorithm that is implemented. Enter your answer in the javadoc comment of the sort() method.
      3. Enter a brief javadoc comment describing what the combine() method does.
      4. What is the best and worst case running time of this algorithm? Provide formuli for the number of times compareTo() 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. Team Assignments:
    1. Prepare a short (5 minute) demonstration of your Vector Graphics project. In your demo show that the required features work and pick 2 or 3 of your niftiest additional or bonus features to show off. Prepare a written “script” listing the features that you will demonstrate. I will ask you to hand in this script after your demonstration.
    2. Working with your team, complete the assigned milestone of the Dam Beavers project.

Turn-in Instructions

Turn-in your individual work by committing it to your SVN repository.

See the Dam Beavers assignment description for team project deliverables.