Re: Offtopic: How to Design Programming Tests

[Matthias Felleisen <matthias@cs.rice.edu>]

  > Michael Bogomolny suggested:
  > 
  > > compare the advantages and disadvantages of arrays
  > versus linked lists.
  > 
  > This is a good question.  My answer would be:
  > 
  > - random access time O(1) vs O(n)
  > - queue/stack operations O(n) vs O(1)
  > - memory usage: array better
  > 
  > Anything I missed?
  >

  Just the obvious speed issue.  Ideas that should probably
  occur to the candidate:

  1.  Dynamic growth of the linked list is probably better
  performance-wise.
  2.  Large data sets will probably work better with linked
  lists (e.g., I just did something similar for an account
  transaction history, where I needed to "window" the
  history available in core memory from the overall history
  due to memory and performance issues.) 

Hold it. How about logical verification tools can validate many aspects of
a linked-list program because it doesn't involve numeric reasoning while it
is often impossible to do the same (for the same cost, or at all) if you
use arrays instead. 

This is a question of design that will sooner or later matter a lot more
than the apparently easy question on speed. Most of the time, lists are
short, the data set is accessed sequentially anyway, ... But the program 
should *never* fail. Prove that. 

-- Matthias