Data Structures and Algorithms — Homework 8

Due by 11:59pm Wednesday, March 27

Reading

• Review the code examples from class.
• Review my written notes on time complexity.
• Read section 14.7 of the textbook (Estimating the Running Time of an Algorithm).

Part 1: Programming Exercises

Download and unzip the folder assign8_files.zip, which contains the starting code for this assignment. This folder also contains the pre-compiled Java program SLLChecker.class. Typing java SLLChecker at the command line will test all of the methods of your LinkedList class and report any problems that it encounters.

1. Implement the following methods of the LinkedList class:

   • public Object removeLast() removes and returns the last element in the list. If the list is empty, null is returned. For example, if L is the list of String objects ["a", "b", "c"], calling L.removeLast() would update the list to be ["a", "b"] and return the String "c".

   • public void clear() removes all elements from the list. For example, if L is ["a", "b", "c"], calling L.clear() would update L to be the empty list [].

   • public boolean set(int position, Object element) updates the contents of the list at position to be element, and returns true if successful. If position is invalid, false is returned instead. For example, if L is ["a", "b", "c"], calling L.set(1, "z") would update the list to be ["a", "z", "c"], while calling L.set(3, "z") would return false without changing the list.

   • public boolean contains(Object element) returns true if element is in the list, or false if it is not. For example, if L is ["a", "b", "c"], calling L.contains("c") would return true.

   • public boolean add(int position, Object element) adds element to the list at position, and returns true if successful. For example, if L is ["a", "b", "c"], calling L.add(2, "z") would update the list to be ["a", "b", "z", "c"] and return true. If L is the empty list, calling L.add(0, "z") would update the list to be ["z"] and return true. Hint: this will be easier if you handle the following four cases separately in your code: (1) position < 0 or position > size (i.e., out of bounds); (2) position = 0 (i.e., adding element to the front of the list); (3) position = size (i.e., adding element to the end of the list); (4) position occurs somewhere in the middle of the list.

   • public Object remove(int position) removes and returns the element at position in the list. If position is invalid, null is returned. For example, if L is ["a", "b", "c"], calling L.remove(1) would update the list to be ["a", "c"] and return "b". If L is the empty list, calling L.remove(0) would return false. Hint: like the add method, implementing this method will be easier if you handle these four cases separately: (1) position out of bounds; (2) removing the first element; (3) removing the last element; (4) removing an element from the middle of the list.

Part 2: Written Exercises

2. Suppose algorithm A takes five seconds to handle a dataset of 1,000 elements. If algorithm A has time complexity O(n), approximately how long will it take to handle a dataset of 2,000 elements? Of 10,000 elements? How long would algorithm A take to handle these larger datasets if it has O(n²) time complexity?

3. Analyze the running times of the code fragments below, assuming that the variable steps has been declared as an int and initialized to zero in each case. Consider the running time to be the total number of loop cycles executed (equal to the final value of steps). Give the running time as a function T(n) of the loop-limit variable n, and state its big-O time complexity. Briefly explain your answer in each case.

   1. for (int i = 0; i < n; i++)
         steps++;
      

   2. for (int i = 0; i < n; i += 2)
         steps++;
      

   3. for (int i = 1; i <= n; i *= 2)
         steps++;
      

   4. for (int i = 0; i < n; i++)
         steps++;
      for (int j = 0; j < n; j++)
         steps++;
      

   5. for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
            steps++;
      

   6. for (int i = 0; i < n; i++)
         for (int j = 0; j < i; j++)
            steps++;
      

   7. for (int i = 0; i < n * n; i++)
         for (int j = 0; j < n; j++)
            steps++;
      

• Analyze the running time of these code fragments:

  8. for (int i = 0; i < n * n; i++)
        for (int j = 0; j < i; j++)
           steps++;
     

  9. for (int i = 0; i < n; i++)
        for (int j = n; j > 0; j /= 2)
           steps++;
     

  10. for (int i = 0; i < n; i++)
         for (int j = 0; j < i; j++)
            for (int k = 0; k < n / 2; k++)
               steps++;
      

Turning in Your Homework

Files to submit:

• LinkedList.java
• PDF document with your answers to the written exercises above.

Submit the above files using the Homework Upload Site. Please include your name and the assignment number in a comment at the top of each Java source code file. You DO NOT need to submit your compiled .class files or any other files.

If you have questions about anything, just ask!