Tutorial

### Arrays or Linked Lists?

An array implementation of a collection requirestime 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?*O(n)**Hint:*Part of the answer is found in the next question and part in IPS205 - the computer architecture section.### 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

### Complexity

Modern processors have clock speeds in excess of 100MHz. Thus a RISC processor may be executing more than 1x10^{8}machine instructions per second. This means they can process of the order of 1x10^{7}"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- one second,
- one minute,
- one hour,
- one day.

Calculate how large a problem you can solve if it is**O(log**_{2}*n*)**O(***n*)**O(sqrt(***n*))**O(***n*log_{2}*n*)**O(log**^{2}*n*)**O(***n*^{2})**O(2**^{n})**O(***n*!)**O(***n*)^{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!).
## No comments:

## Post a Comment