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 first 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.
;; 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 actual number of values being stored and only increase the size of the stored array when nessesary.
You will include the following methods from
- 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:
Last modified on
Friday, 19 August 2011, at 18:05 hours.