Data Structures and Algorithms
Tutorials

Tutorial 1

  1. Arrays or Linked Lists?

    An array implementation of a collection requires O(n) time to search it (assuming it's not ordered). A linked list also requires O(n) time to search. Yet one of these will be quite a bit faster on a high-performance modern processor. Which one? Why?

    Hint: Part of the answer is found in the next question and part in IPS205 - the computer architecture section.

  2. Overheads

    The storage requirements for a typical modern RISC processor are:
    TypeSpace (bytes)
    integer
    4
    pointer
    4
    float
    4
    double
    8
    A typical implementation of malloc will use an extra 4 bytes every time it allocates a block of memory. Calculate the overheads for storing various numbers of items of the types listed using the array and list implementations of our collection object. Overhead here means that if a data structure requires 1140 bytes to store 1000 bytes of data, the overhead is 14%. Fill in the table:
    Item type
    		Number of items
    Array
    List
    integer
    100
    1000
    double
    100
    1000
     
     
    struct {
     int x, y;
     double z[20];
}
    100
    1000

  3. Complexity

    Modern processors have clock speeds in excess of 100MHz. Thus a RISC processor may be executing more than 1x108 machine instructions per second. This means they can process of the order of 1x107 "operations" per second. An "operation" is loosely defined here as something like one iteration of a very simple loop.

    Assuming that you patience allows you to wait

    1. one second,
    2. one minute,
    3. one hour,
    4. one day.
    Calculate how large a problem you can solve if it is
    1. O(log2 n)
    2. O(n)
    3. O(sqrt(n))
    4. O(n log2 n)
    5. O(log2 n)
    6. O(n2)
    7. O(2n)
    8. O(n!)
    9. O(nn)

    Numbers beyond the range of your calculator can simply be reported as "> 10x" or "< 10-x", where x is determined by your calculator.

    To try this in reverse, assume that to be certain of beating Kasparov in the next "Man vs machine" chess challenge, we would need to look ahead 40 moves. How long will it take one of today's computers to calculate each move?
    For simplicity, assume that, on average, the number of possible moves is the same for every move: but if you know of any other estimate for the number of moves in chess, then use that. And if you don't know western chess, substitute Chinese chess or Go (and the appropriate current champion's name!).

Tutorials (cont)
 Back to the Table of Contents
© John Morris, 1996