22C:30, 22C:115 Homework 2

Due date: Monday, 10/21

Problem 1
The input is a sequence of integers and the problem is to sort this sequence using linked lists. I want you to use two methods to do this and then compare the two methods using their running time as a measure.

Method 1 Use a singly linked list to maintain a sorted list of the numbers read so far. When you read the next number, scan the the list starting from the first node, find the appropriate location for the new number, and insert a node containing the new number there. In this manner, after processing the next number, we still have a sorted list. To implement this method you just need to maintain a head pointer to point to the first node in the list. When the function has finished sorting all numbers, it should return head.
Method 2 Use a doubly linked list to maintain a sorted list of the numbers read so far. To have access to the list use a current pointer pointing to the node most recently inserted. When you read the next number, scan the the list starting from the current node, find the appropriate location for the new number, and insert a node containing the new number there. Note that you may scan the list going forward from the current node or backward from the current node depending on the relative sizes of the new number and the number most recently inserted. In this manner, after processing the next number, we still have a sorted list. When the function has finished sorting all numbers, it should return current.

For both methods, you stop as soon you have found the appropriate location for the new number. In other words, you don't want to scan the entire list always---just as much as you absolutely have to. The two methods only differ in where you start scanning from. Implement the two methods as functions Sort1 and Sort2. Feel free to uses functions from the linked list toolkit as helper functions. You should have Sort1 and Sort2 return

What do you turn in? Printouts of code for Sort1 and Sort2.

Problem 2
Modify Sort1 and Sort2 so that, rather than read from the keyboard, they pick up elements one at a time from an apvector in which they are already stored. So you can assume that the function header for Sort1 and Sort2 are:

          node * Sort1(const apvector & numbers);
          node * Sort2(const apvector & numbers);

This modifcation will help in the following experiment.

Create an apvector with n randomly generated integers in the range 1 through n. Use the RandGen class to generate the random integers. Call each of the functions Sort1 and Sort2 and time their execution. For a particular value of n, repeat this experiment 10 times (generating afresh the random sequence of integers) and compute the average running time of Sort1 and Sort2 for sorting a sequence of length n. Perform this experiment for n = 1000, 2000, 3000, ..., 10,000. Plot the running times of Sort1 and Sort2 in the same graph and comment on the following:

The shapes of your plots. Are these linear (straight lines) or not? Try to explain the shapes.
How do the running times of the two sort functions compare? Try to explain any differences or similarity you find.

What do you turn in? The plot showing the running times along with your answers to the above questions.

Problem 3
Start with the functions Sort1 and Sort2 you created for Problem 2. Here is another timing experiment comparing the running times of Sort1 and Sort2. This differs from the experiment in Problem 2 in how the random sequence of n elements is generated. The goal here is to generate a sequence of n elements that is "almost sorted" in the sense that each element is not too far from its position in a sorted list. To do this start with an apvector of n integers and initialize this to 1, 2, 3, ..., n. Let block 1 be the first contiguous block of 10 elements in the apvector, block 2 be the second contiguous block of 10 elements in the apvector, block 3 be the third contiguous block of 10 elements in the apvector, and so on. So we have n/10 blocks of elements. Randomly permute the elements within each block. The resulting sequence satisfies the property that no element is more than a "distance" 10 away from its position in a sorted list. Using this input sequence, perform the experiment you performed in Problem 2. The only difference between this experiment and the experiment in Problem 2 is the way the input sequence is generated.

What do you turn in? The plot showing the running times along with your answers to the above questions.

Problem 4
For the graph given below, show: [Graph]

its adjacency representation, assuming that nodes are stored in the node apvector and in each list of neighbors in increasing order of their labels,
a breadth first search tree obtained by searching the tree starting at source 6, with the distance of each node from the source clearly marked.