CS 136 Tutorials - Spring 2007

CS 136 Review: Exam Review Session (Aug 2)

This will sever as the main page for information on the Final Exam Review Session:

• Date: Thursday, August 2
• Time: 3:00pm to 5:00pm
• Room: MC 4040.

A few things that were mentioned in class about the exam are:

• Review the main ideas from the Assignments, Midterm and Modules.
• Other good sources are the Tutorials and this Review Session.
• 30% will deal with the frist half of the course.
• 50% will deal with the second half.
• 20% will deal with topics that are in both.

Remove and Return Evens!

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.

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

   ArrayQueue<E> Class

   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 actuall 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>:

   
   
   • 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];"

   Improved Merge Sort

   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[].