CS 231: Homework

Homeworks

Current HW

HW 1: Write two classes, both of which you will use throughout the semester.

Due 12 September 2007

Solution
• RandomInt: this class should have a constructor that takes a single integer A, which is the number of integer random values the class can produce, from 0 to A-1. The class should also have a public method roll():int, that returns an integer with a randomly chosen value between 0 and A-1. Finally, the class should have a method seed(int B):void that takes an integer B and seeds the random number generator with it. You may want to use an instance of the Random class to build RandomInt.
• RandomReal: this class should have methods similar to the RandomInt class (a constructor that takes a double A, roll():double and seed(B):void), but the roll function should produce real numbers (doubles) randomly distributed in the range of [0, A). In other words, the range of values should include zero, but not A.

HW 2: Data structures in the world.

Due in class 19 September 2007

Solution

Look around you in the world for how things are organized. Find examples of five different kinds of organization of objects in the world. For example, how do people organize themselves in the dining halls or at a checkout counter? Look for examples with different characteristics, such as whether things can be easily inserted into the data structures, whether things can be easily deleted, and the order in which elements of the data structure are accessed.

HW 3: Stacks and Queues

Due by class 26 September 2007

Solution

Implement generic Stack and Queue classes using your choice of implementation (array or linked). Write a main function for each class that demonstrates their functionality using type Float.

Stack methods:
• public void push(T obj); pushes an object on the stack.
• public T pop(); removes the top object from the stack.
• public T peek(); returns a reference to the top object on the stack.
• public boolean empty(); returns whether the stack is empty.
• public int size(); returns the number of elements on the stack.
Queue methods:
• public void insert(T obj); puts an object in the back of the queue.
• public T remove(); removes the front object from the queue.
• public T peek(); returns a reference to the object in the front of the queue.
• public boolean empty(); returns whether the queue is empty.
• public int size(); returns the number of elements on the queue.

HW 4: Iterators

Due by class 10 October 2007

Solution

Implement an ordered list data structure called ListInteger for type Integer using a linked implementation. The list should permit duplicate elements. Make the list implement the Iterable interface, and create a class ListIterator that implements the Iterator interface for ListInteger. Create a main method for the ListInteger class that tests the methods for both the list and iterator.

ListInteger methods:

• public void insert(Integer val) - inserts the element into the list in the appropriate location so that the list remains sorted in ascending order after the insert.
• public Integer remove(int index) - removes and returns the element in the ith location of the list (zero should remove the first element in the list).
• public Integer front() - removes and returns the element at the front of the list.
• public Integer peek(int index) - returns, but does not remove, the element in the ith location of the list.
• public void clear() - clears the list of all elements.
• public boolean empty() - returns whether the list is empty.
• public int size() - returns the number of elements on the list.
• public Iterator iterator() - returns an iterator for the list.

ListIterator methods:

• public boolean hasNext() - returns whether there are any more elements left in the iteration.
• public Integer next() - returns the next element in the iteration. The first call to next() should return the first element in the list. The function can either return null or throw an exception if it is called on an empty list or if there are no elements left in the iteration.
• public void remove() - (optional) removes the element whose value was returned by the last call to next(). A valid implementation is to simply throw an UnsupportedOperationException.

HW 5: Exam Prep

These questions are for study only, not to be handed in. Solutions will be discussed in class on Wednesday.

1. Given a class MyList that implements the Iterable interface, show how you would use the hasNext() and next() methods of its iterator to traverse the list.
2. Explain the difference between a Stack, a Queue, and a List.
3. Given an array-based implementation of an arbitrary sized Stack, explain why the push() function is O(1) if the stack doubles in size when it needs more space but is O(n) if the stack only increases by K locations each time it needs more space.
4. Explain the difference between a static and a non-static method. Why is the main method always static?
5. What is the difference between implementing an interface and extending a class?
6. Why can a variable of type Object hold a reference to any other type of reference?

HW 6: Sorting and Recursion

Due by class 31 October 2007

1. Write implementations of both bubble sort and merge sort for an array of integers.
2. Run both algorithms on arrays of length 10, 100, 1000, 10000, and 100000 filled with random integers and calculate the time taken by the computer to process the arrays. You probably will need to repeat the sorting procedure many times (esp for small arrays) in order to have good numbers to work with. Figure out how to time your code (hint, look at the Time class).

HW 7: Path Planning

Due by class time 28 November 2007