Algorithms and Data Structures

Tutorial

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:
   
   

   Type	Space (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 1x10⁸ machine instructions per second. This means they can process of the order of 1x10⁷ "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(log₂ n)
2. O(n)
3. O(sqrt(n))
4. O(n log₂ n)
5. O(log² n)
6. O(n²)
7. O(2ⁿ)
8. O(n!)
9. O(nⁿ)

Numbers beyond the range of your calculator can simply be reported as "> 10^x" 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!).