Carleton College CS 107, Explorations in Computer Science

Assignment:

 0  0
 1  0
 2  U
 3 10
 4  X
 5  8
 6  T
 7  0
 8  E
 9  6
10  L
11 12
12  M
13  4
14  0
15  0

Suppose that this data represents a linked list whose head is at memory location 2. Furthermore, the end of the linked list is found when the "pointer" to the next memory location is a 0.

1. Rewrite this linked list with a "boxes and arrows" diagram like we talked about it in class (also in your textbook).

2. Suppose that you wish to insert the letter 'Q' between the M and X. Show below what memory might look like after this insertion:

 0  _____
 1  _____
 2  _____
 3  _____
 4  _____
 5  _____
 6  _____
 7  _____
 8  _____
 9  _____
10  _____
11  _____
12  _____
13  _____
14  _____
15  _____

3. Work through Laboratory 9 Part 2, and turn in Exercise 1. Here are a couple of clarifications:

• There is nothing to actually do for question 2 apart from appreciating the table for its intrinsic beauty.
• For question 3, where it says "record the numbers it generates in the big white text area": specifically, the number you should record is the number of comparisons. Quicksort spits out lots of additional information that you can ignore for purposes of this exercise.
• For questions 4 and 5, whenever it refers to how "fast" an algorithm is, it really is asking about how many comparisons it performs (the information you uncovered in part 3).