Comp 271 Midterm Study Guide

The exam is Tuesday, October 20. We also have a lab that day; however, if you need more time on the exam you can work on the lab later.

Sections from Bailey

Chapter 3: Vectors

    3.1: Vector interface
    3.4: Implementation
    3.7: Vector-based Sets
I will give you the implementation of MyList<E> as a java reference.

Some self-check problems, page 64:
    3.1 (perhaps with ArrayList replacing Vector), 3.3, 3.4, 3.5, 3.7, 3.10
Problems, page 64:
    3.1, 3.3, 3.5, 3.7, 3.8 (why having size<capacity is important!)

Chapter 4: Generics

Know what public class foo<T> {...} means
4.2: Implementing
Type constraints involving T will not appear on the exam (eg class foo<T extends Number>)

Chapter 6: Sorting

    6.2: Selection Sort
    6.3: Insertion Sort
    6.4: Mergesort
    6.5: Quicksort, including the pivot operation
    Know about O(n²) versus O(n log n)

Self-check problems, p 144:   6.2, 6.3
Problems, p 145: 6.5, 6.6, 6.13, 6.15

This is the chapter with the most material. You don't have to be able to write any of the sorting algorithms, but you should know:

what the k^th pass of Selection Sort does (finds the smallest of A[k]..A[max-1], and swaps it into position k, where it stays)
what the kth pass of Insertion Sort does (inserts A[k] into the correct position among A[0]..A[k-1], which are sorted)
what a merge does
what a pivot = partition(data, left, right) operation does in QuickSort

For Selection and Insertion sort, I will give you some kind of brief outline of what one pass is to do; I get them mixed up regularly and don't expect you to memorize the names.

Chapter 8: Iterators

8.2: Iterator Interface
All you have to be able to do is use an iterator: while (it.hasNext()) { do_something_with(it.next()); }

Self-Check Problems (p 173): 8.2, 8.3
All of the exercises in the Problems section seemed much too involved for an exam.

Chapter 9: Lists

9.4: Singly-Linked Lists
You should know how to use pointers to Cells (Nodes in Bailey)
You should be familiar with while (p!=null) {do_something_with(p.data()); p = p.next(); } loops.

Self-Check Problems (p 212): 9.1, 9.2, 9.5 (answer kind of depends on your library), 9.7, 9.10, 9.11
Problems: 9.1,

Recursion will not be on the exam as such, but note that MergeSort (one form) and QuickSort are recursive.

Java Knowledge

You should be able to write straightforward loops. The AList<E> code sheet I'm providing should cover most things. It is a working version of the lab1 MyList class edited to fit on one sheet of paper (two columns).

Additional Problems

1. Recall that Insertion Sort sorts an N-element array as follows:
    for (k=0; k<N; k++) {
          Precondition: A[0]..A[k-1] are sorted
          insert x=A[k] into the correct position among A[0]..A[k-1]
          Postcondition: A[0]..A[k] are now sorted

Do this for k=0,1,2,3 for the array A= [13, 47, 2, 16, 35, 14, 11, 38 ]

2. Recall that Selection Sort sorts an N-element array as follows:
    for (k=0; k<N-1; k++)
       Pre: A[0]..A[k-1] are sorted and are smaller than any subsequent elements
       Find the smallest among A[k]..A[N-1]
       Swap it into position k
       Post: A[0]..A[k] are sorted and are smaller than any subsequent elements

Do this for k=0,1,2,3 for the array A = [13, 47, 2, 16, 35, 14, 11, 38 ]

3. Here is Bailey's partition code for QuickSort. The partitioning value is originally at data[left].

private static int partition(int data[], int left, int right) {
// pre: left <= right
// post: data[left] placed in the correct (returned) location
    while (true) {
        while (left < right && data[left] < data[right]) right--;        // move right "pointer" toward left
        if (left < right) swap(data,left++,right);
        else return left;

        while (left < right && data[left] < data[right]) left++;        // move left pointer toward right
        if (left < right) swap(data,left,right--);
        else return right;
    }
}

Use this to partition the array [13, 47, 2, 16, 35, 14, 11, 38 ], with left=0 (left end) and right=7 (right end).

You can do this by following the code step-by-step, but it is a lot more efficient to "understand" what it is doing.

4. Merge these two lists into one sorted list:

    [2, 6, 19, 21, 47, 83, 87, 90, 95, 97 ]
    [3, 5, 12, 17, 31, 38, 48, 51, 88 ]

5. Suppose we have a linked list of Cells,
    private class Cell {String data; Cell next; Cell(String d, Cell n) {data=d; next = n};
                String getData() {return data;}     String getNext() {return next;}   }

Suppose the variable p of type Cell is a pointer to the first cell.

(a). Write a loop to count the number of Cells in the list.

(b). Write java statements to insert a new cell containing the string "breadfruit" immediately after the cell pointed to by p.

6. The main efficiency difference between ArrayLists and LinkedLists of size N is that accessing the kth element of an ArrayList is O(1) (that is, a constant that does not depend on k or N), while accessing the kth element of a LinkedList is O(N) (for a randomly chosen k, averaging N/2). For inserting, on the other hand, these are reversed (though inserting at a given position in a LinkedList is only O(1) if we have already got a pointer to the preceding Cell).

All of InsertionSort, SelectionSort, QuickSort, and MergeSort can be ported to LinkedList objects. Which, if any, new implementation would likely be subject to a significant performance hit in doing so?