This will sever as the main page for information on the Final Exam Review Session:
A few things that were mentioned in class about the exam are:
Remember our good old remove-evens function in Scheme? Now we are also going to return a list of the evens that were removed from the given list, without useing new cons cells ofcourse.
;; remove-and-return-evens! lst -> lst ;; mutates the give list so it no longer contains the even elements ;; and returns a list representing the removed elements. ;; no new cons cells should be created. (define (remove-and-return-evens! lst) ... )
Create a class that implements
Queue<E> (provided) that uses an array to store elements.
You should store an array that is larger then the number of stored values and you should keep
track of the actual number of values being stored and only increase the size of the stored array when nessesary.
You will include the following methods from
ArrayQueue(): construct an ArrayQueue with a starting size of 16.
ArrayQueue(int num): construct an ArrayQueue with a starting size of num.
boolean isEmpty(): returns true iff the stack is empty.
void clear(): removes all values from the Queue.
E peek(): Retrieves, but does not remove, the head of this queue, throws NoSuchElementException if queue is empty.
E poll(): Retrieves and removes the head of this queue, throws NoSuchElementException if queue is empty.
boolean offer(E item): Inserts the specified element into this queue, if possible.
int size(): Returns the number of elements stored in this queue.
E get(int i): Retrieves, but does not remove, the ith element.
void extend(): doubles the size of the stored array.
tip: to create a generic array do a cast "E array = (E) new Object[num];"
We mentioned in class that the code we gave for merge sort was memory inefficient. Improve this memory usage to O(n), ie. only create one extra array of size n and have all the code use that single array. We have also mentioned that in the real world little tweaks are preformed on sorting algorithms to give them a better run time; you are to create a smartMerge that applies an insert sort on pieces of the array that are less then or equal to 8.
Create a class called
Sort that contains:
static void merge(int inta): sorts by mutating the elements in the array using the merge sort algorithm.
static void insert(int inta): sorts by mutating the elements in the array using the insert sort algorithm.
static void smartMerge(int inta): uses a combination of merge and insert, applies insert to parts of the array that are of length 8 or below.
For added practice, change the above int to consume Comparable.
Last modified on Friday, 19 August 2011, at 18:05 hours.