CSSE 220 – Object-Oriented Software Development

Homework 14

Objectives

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

Tasks

  1. Complete the assigned reading for the next session, according to the course schedule.  
  2. Complete the assessment exercises over this reading on ANGEL (under Lessons → Assignments).
  3. Solo Work: Complete the following exercises from the SortingAndSearching project that you checked out in class.

    1. 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 array variable is accessed 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.

    2. For this task you’ll be working on the sortAndSearch package.
      1. Study the MergeSort program there and experiment with it. 
      2. What is the best and worst case running time of this algorithm? Provide formulae 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. Answer the questions in the writtenProblems.txt file in the project directory.

Remember, in all your code:

Here is the grading rubric for this assignment.

Turn-in Instructions

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