One of the things that gets used and discussed a lot by beginning programmers is random numbers. of course those of us who have been around the block know that computer generated numbers are really pseudo-random numbers. It's a fairly short and reasonable discussion to explain seed values and why the same sequence of numbers will come up if the same seed value is given. But explaining how these numbers are generated is a more complex discussion completely.
Last week Paul Vick of the Visual Basic team posted a note about pseudo-random numbers and Visual Basic. Included in this post is a code example of one version of a random number algorithm written in Visual Basic. It's not an algorithm for the timid and it involves some concepts that many students will not learn in a first course in programming. But I think it is useful even in those cases for students to get a feel for some of the complexities involved in the process.
An other interesting thing in Paul's post is that he discusses the weakness of the Rnd function in Visual basic and why it hasn't been updated. The short story is that they are concerned that there is code out there that relies on a specific seed value generating the same string of numbers and they don't want to break those programs. At the same time there want to provide a stronger, better function for those people who have that sort of need. Balancing the issues of improvement and innovation against backwards comparability makes an interesting discussion to have in class and other places.