Programming Pearls Clmn 12

A “Simple” Sample Problem

Okay, So what is the Simple Sample problem?

We come out with trying to solve a drawing a random sample from a list.

Our core problem becomes how to generate m distinct numbers within n.

Three solution are given for this problem. But you see, there is no prove for any of these algorithm. In stead, what we see here is just time complexity and space complexity, in additional, the code complexity.

Here we can figure out that the author is a completist. He required his student to be come as simple, as faster as possible.

This column is much easier to read than TAOCP(The Art of Computer Programming, Donald Knuth). I tried to read this book when I was year 1…

That book is a real killer. I think I should try this book instead of that one. This column is a good hook for TAOCP Volume 2.

(But that book is really heavy and expensive, LoL)

The problems are not to difficult, but some thoughts are worth borrowing.

1. define new random int generation function

Use what we get just now to solve what we will face in the future.

6. The more you submit, the less mark you will get

Honestly speaking, I like geek lecturer. Your lessons will be really funny. But I really do not like him/her to be the one who gives mark to your course work. Sometime you may get a slip under his/her geek instruction. Or he/her may think your work is not clever enough…

7. Functional Programming

Code in Programming Pearls are coded in pseudo code or C. TAOCP uses MIX. I still insist we need to read a algorithm book written in functional programming.

Maybe this is a good open source project:

Haskell and Algorithm. LoL

8. Solution gives an excellent code

The code is subtle. One could need read it several times to get the programmer’s idea.

One important thing here.

Code complexity, Time complexity and Space complexity are in a sophisticated trade-off relation. Which one is the most important one?