CS 136 Tutorials - Spring 2007

Tutorials »

CS 136 Review: Exam Review Session (Aug 2)

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:

  1. Remove and Return Evens!
  2. 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.

  3. ;; 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) ... )

  4. ArrayQueue<E> Class
  5. 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 Queue<E>:

  6. Improved Merge Sort
  7. 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: