The first couple weeks have gone by very quickly due to the weird fall quarter start and we thought it would be good to take stock in what we have learned so far in terms of what you need to know for the midterm.

In lecture, we sometimes introduce a lot of details so that you have all the tools necessary to tackle the challenging homework assignments. Those details are important to know, but on our exams we are almost entirely focused on you using your problem solving rather than testing your memorization of details.

This document shows an example practice midterm with only the material that you have seen so far. We will come back and look at the rest of exam as we finish more material, but we wanted to just show you what we are expecting you to be responsible for knowing with respect to the exams.

One thing you should also know about our exams: We will give you a cheat sheet on the exam so that you don’t need to remember any particular methods in the Java library. We really want to focus on problem solving!

Problem 4: Collections

This will involve writing a program that does some computation with some data structures. While we did introduce most of the data structures we will see on this problem, we do not list a problem here yet since you have not had a section to practice collections programming and we have one more data structure to learn.

Problem 5: Stacks and Queues - collapse

Write a method collapse that takes a Stack of integers as a parameter and that collapses it by replacing each successive pair of integers with the sum of the pair. For example, suppose a stack stores this sequence of values:

bottom [7, 2, 8, 9, 4, 13, 7, 1, 9, 10] top

Assume that stack values appear from bottom to top. In other words, 7 is on the bottom, with 2 on top of it, with 8 on top of it, and so on, with 10 at the top of the stack.

The first pair should be collapsed into 9 (7 + 2), the second pair should be collapsed into 17 (8 + 9), the third pair should be collapsed into 17 (4 + 13) and so on to yield:

bottom (9, 17, 17, 8, 19) top

As before, stack values appear from bottom to top (with 9 on the bottom of the stack, 17 on top of it, etc). If the stack stores an odd number of elements, the final element is not collapsed. For example, the sequence:

bottom (1, 2, 3, 4, 5) top

would collapse into:

bottom (3, 7, 5) top

with the 5 at the top of the stack unchanged.

You are to use one Queue as auxiliary storage to solve this problem. You may not use any other auxiliary data structures to solve this problem, although you can have as many simple variables as you like. You also may not solve the problem recursively.

In writing your method, assume that you are using the Stack class and Queue interfaces with the LinkedList implementations discussed in lecture. As a result, values will be stored as Integer objects, not simple ints.

Problem 6: ArrayIntList Programming - removeFront

Write a method removeFront that takes an integer n as a parameter and that removes the first n values from a list of integers. For example, if a variable called list stores this sequence of values:

[8, 17, 9, 24, 42, 3, 8]

and the following call is made:


then it should store the following values after the call:

[42, 3, 8]

Notice that the first four values in the list have been removed and the other values appear in the same order as in the original list.

You are writing a method for the ArrayIntList class discussed in lecture:

public class ArrayIntList {
    private int[] elementData; // list of integers
    private int size;          // current # of elements in the list


You are not to call any other ArrayIntList methods to solve this problem. Your method should throw an IllegalArgumentException if the parameter n is less than 0 or greater than the number of elements in the list. Your solution must run in O(n) time.