CS 231: Homework


Current HW

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

Due 12 September 2007


HW 2: Data structures in the world.

Due in class 19 September 2007


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
Please email your .java files to the prof


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: Queue methods:

HW 4: Iterators

Due by class 10 October 2007
Please email your .java file to the prof


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:

ListIterator methods:

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
Please email your .java files to the prof along with a table of your timing results.

  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
Please email your .java files to the prof, along with your visibility graph file.

  1. Download the visibility graph java file. The class is appropriate for representing a topological map for navigation (by a robot, or something like Google maps).

  2. Implement Dijkstra's algorithm for the class. The method takes the index of the root node as its argument. Run it on the example graph

  3. Create your own map, preferably of some real situation, and evaluate your algorithm using your map. If you can't think of something to map, pick ten large cities across the US that are connected by interstates and build a graph from those. A set that forms a nice grid are: Seattle, Portland, San Francisco, LA, Salt Lake City, Denver, St. Louis, Dallas, Oklahoma City, Houston, and Omaha.

  4. Try running this homework using a terminal. The relevant commands are javac VisGraph.java to compile the .java file into a .class file and java VisGraph myfile.vis to run the main function with the argument myfile.vis.