Exam 2: Algorithms and Algorithm Analysis

This page may be found online at http://www.math.grin.edu/~rebelsky/Courses/CS152/99S/Handouts/exam.02.html.

Distributed: Friday, March 12, 1999
Due: Start of class, Friday, March 19, 1999
No extensions!

Policies

If you are confused by any question, do not hesitate to ask me for clarification. I will reserve time at the start of classes next week for questions. In addition, you can speak to me individually. I may not be available at the time you are working on the exam. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445). Email is also a reasonable way to contact me.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use any and all resources available to you except for other people and answer keys. That is, you should not consult other students, other faculty, or anyone else. (If someone outside of Grinnell has already created a web page that answers your question, that's okay; however, you can't ask someone to create such a page.) In addition, while you can look at the pages I've created for this and other courses, you should not refer any pages that are clearly answer keys to homework assignments of exams.

As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. It is likely to take you about four hours. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted. I will make a solution key soon after the exam.

Because different students will be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is definitely the hardest exam I have ever taken.'' You may also summarize these policies.

Answer all of your questions electronically. That is, you must write all of your answers on the computer and print them out. Please put your answers in the same order that the problems appear in.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by highlighting your answer and including a clear set of work that you used to derive the answer.

In some questions, you may be asked to write code. You should write correct, working, and tested code.

Problems

1. Deletion in Ordered Lists

Our old pals Carla and Carl Caffeinated are back, asking for your help in writing Java code. They've been building an ArrayBasedOrderedList class and have decided that they should include a deleteAllCopies method that deletes all copies of an element.

Here's what they've come up with

  /**
   * Delete all copies of elt from the current list.
   */
  public int deleteAll(Object elt) {
    // A count of the number of elements deleted.
    int numDeleted = 0;
    // Step through the array, finding equal elements and deleting them.
    // Because this is an ordered list, we need to shift after deletion.
    for (int i = 0; i < this.length; ++i) {
      // Did we find an equal element?
      if (elt.equals(this.elements[i])) {
        // Shift left
        for (int j = i; j < this.length; ++j) {
          this.elements[j] = this.elements[j+1];
        }
        // Delete the last element.
        this.elements[this.length] = null;
        // Update the length.
        this.length -= 1;
        // Update the count.
        this.numDeleted += 1;
      } // if we found an equal element
    } // for each element
    // That's it.
    return numDeleted;
  } // deleteAll(Object)

1.a. Problems with deleteAll [15 points]

Like many novice programmers, Carl and Carla have made a few subtle errors in writing this function. Identify those errors.

Hint: Some problems occur when the list is full. (Yes, others will occur in other situations.)

1.b. Preconditions and Postconditions [15 points]

Carl and Carla never learned about preconditions and postconditions. They've hired you to write them for them, because their client has required them. They note ``our client is as extreme as Dr. Rebelsky, so you need to be particularly careful''.

1.c. Running Time [10 points]

While Carl and Carla understand big-O analysis, they're not very good at it. They think that the running time of deleteAll is O(n), but they're wrong. What is the worst-case running time, and why?

1.d. Improving deleteAll [20 points]

Rewrite deleteAll so that it has running time of O(n).

2. Sorted Lists

After their successes with ordered lists, Carl and Carla have moved on to sorted lists. They've once again decided to implement lists using arrays, They've also decided to keep the elements in order in the array. To simplify things, they've decided that they'll only deal with sorted lists of integers. Here's the add method they've written, as well as a sketch of a findPlace method.

  /**
   * Add a value to this sorted list of integers.
   * Pre: The list is initialized, and there have been no invalid
   *   operations on the list.
   * Pre: There is space remaining in the list to add the new element.
   * Post: Iteration may be invalidated.
   * Post: The value is added, and will be returned in the proper
   *   order during iteration.
   * Post: The length of the list increases by 1.
   */
  public void add(int val) {
    // Determine the correct position in the list.
    int pos = findPlace(val, 0, this.length-1);
    // Shift right to insert the element.
    for (int j = this.length; j > pos; --j) {
      this.elements[j] = this.elements[j-1];
    }
    // Insert the element.
    this.elements[pos] = val;
    // Update the length.
    this.length += 1;
  } // add(int)
  
  /**
   * Find the correct position for a value in a part of the
   * array used to implement the list.  Should be implementable
   * using a technique like binary search.
   * Pre: The list is initialized, and there have been no invalid
   *   operations on the list.
   * Pre: The subarray lb..ub is sorted.
   * Post: Returns a position, pos, such that (1) the element at position
   *   i is less than or equal to val, for all i less than pos; and (2)
   *   the element at position j is greater than or equal to val, for all 
   *   j greater than or equal to pos.  If no elements already in the subarray
   *   are greater than val, returns ub+1.  If no elements already in the
   *   subarray are less than val, returns lb.
   * Post: No elements are added, deleted, or moved.
   */
  protected int findPlace(int val, int lb, int ub) {
    // Help!
  } // findPlace(int,int,int)

2.a. Implement findPlace [30 points]

Implement findPlace using an appropriate variant of binary search. Note that findPlace differs from binary search in that when the element isn't in the array, it needs to report the correct place in the array for the element to be inserted. (If there's an equal element, that's the correct place to insert the element.)

2.b. Reconsidering findPlace [10 points]

Upon studying the code for add and your O(logn) findPlace, Alvin and Althea Analyst declare ``that findPlace method is needlessly complicated; it will have no real effect on the running time if you implement it with sequential search''. Explain why they might say this.

History

• Created Wednesday, March 10, 1999.
• Distributed Friday, March 12, 1999.
• Corrected a few typos (and added history) on Sunday, March 14, 1999.
• Corrected a few more typos on Monday, April 12, 1999.