Invisible wrote:
> As for examples of my work... it strikes me that I've almost never 
> produced a "finished" program in my life.

I don't know anyone who ever thought their program was finished. Even 
games that go out the door aren't "finished" as far as the people 
working on them are concerned.

> And then there's the minor detail that although I know a lot of stuff 
> about stuff... how many people actually need to know what a Huffman tree 
> is? None. Nobody needs to know this. 

Actually, the cool places do. Read some of the google whitepapers and 
actually look at the algorithms they use. It's the first place in 25 
years I've seen using Bloom filters.

> You can't do that without a postal address. (And stamps. Do you have any 
> idea how hard it is to purchase stamps?!)

Now you're just making up excuses. :-) I'll admit stamp purchasing is 
unobvious in Europe to someone from America who would expect to be able 
to buy stamps at, say, the post office, but it can't be *that* difficult.

-- 
Darren New / San Diego, CA, USA (PST)
  Helpful housekeeping hints:
   Check your feather pillows for holes
    before putting them in the washing machine.

Post a reply to this message

>> Of course it does, it is evidence that you are *willing* and *capable* of 
>> learning such things.  That is more important than what you actually 
>> know.
>
> Certainly a point worth making, and one I always try to emphasise. Heck, 
> that's how I got *this* job in the first place! ;-)

Any decent company will have this mentality while interviewing too.  Do you 
pick the person who has spent 10 years learning the exact skills you need, 
or the person who has spent 5 years learning a dozen different skills that 
are all just as difficult as the one you need?

Post a reply to this message

>> As for examples of my work... it strikes me that I've almost never 
>> produced a "finished" program in my life.
> 
> I don't know anyone who ever thought their program was finished. Even 
> games that go out the door aren't "finished" as far as the people 
> working on them are concerned.

Well yeah, but you don't ship a game while it's still not playable 
without a C compiler and some heavy-duty programming skills. :-P

>> And then there's the minor detail that although I know a lot of stuff 
>> about stuff... how many people actually need to know what a Huffman 
>> tree is? None. Nobody needs to know this. 
> 
> Actually, the cool places do. Read some of the google whitepapers and 
> actually look at the algorithms they use. It's the first place in 25 
> years I've seen using Bloom filters.

Yeah, but I won't be working for Google, will I? :-P

>> You can't do that without a postal address. (And stamps. Do you have 
>> any idea how hard it is to purchase stamps?!)
> 
> Now you're just making up excuses. :-) I'll admit stamp purchasing is 
> unobvious in Europe to someone from America who would expect to be able 
> to buy stamps at, say, the post office, but it can't be *that* difficult.

The Post Office?

Oh, you mean that place that shuts 20 minutes before I got home? :-P

[What annoys me is that there used to be a machine outside that 
despenses stamps. But then they turned it off... It's still there, it 
just won't give you any stamps!]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> Plus, all their software development stuff clearly says all over it 
>> "prior experience of developing large-scale applications is an 
>> absolute requirement". So I guess I fail, right there.
> 
> Yoda would think otherwise. You can only fail if you don't try.
> 
> Well, that's not quite true. But believe me, you won't get past the 
> phone interview if they're actually serious about that.

They're talking about people who have experience with Linux kernel 
development and stuff - *I* can't even *read* C.

>> Hmm. Tell me something - all that stuff I just posted? Does it make 
>> any semblance of comprehensible sense?
> 
> Quite! That's what people are trying to tell you. You explain things 
> very clearly.

Well, *I* like to think I explain things very clearly. But unless other 
people actually agree with me, I have to wonder whether I'm just kidding 
myself...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> The Post Office?
>
> Oh, you mean that place that shuts 20 minutes before I got home? :-P
>
> [What annoys me is that there used to be a machine outside that despenses 
> stamps. But then they turned it off... It's still there, it just won't 
> give you any stamps!]

Don't you have any supermarkets or newsagents nearby?  They usually open 
much later and have stamps.

Post a reply to this message

>> The Post Office?
>>
>> Oh, you mean that place that shuts 20 minutes before I got home? :-P
>>
>> [What annoys me is that there used to be a machine outside that 
>> despenses stamps. But then they turned it off... It's still there, it 
>> just won't give you any stamps!]
> 
> Don't you have any supermarkets or newsagents nearby?  They usually open 
> much later and have stamps.

To be honest, I've never seen stamps on sale anywhere except at a post 
office. Maybe they keep 'em hidden behind the counter or something, but 
I've never seen them on sale...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> To be honest, I've never seen stamps on sale anywhere except at a post 
> office. Maybe they keep 'em hidden behind the counter or something, but 
> I've never seen them on sale...

http://www.royalmail.com/portal/rm/jump2?catId=400046&mediaId=26800663

Post a reply to this message

>> To be honest, I've never seen stamps on sale anywhere except at a post 
>> office. Maybe they keep 'em hidden behind the counter or something, 
>> but I've never seen them on sale...
> 
> http://www.royalmail.com/portal/rm/jump2?catId=400046&mediaId=26800663

Heh. Yeah. I ended up having to use this once...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

>> A Huffman code is a similarly straight-forward idea. 
> 
> Tell that to Huffman. ;-)

Huffman coding is one of those algorithms that seems delightfully 
"obvious" after you've been told the algorithm. No doubt it seemed 
highly non-obvious before anybody thought of it. ;-)

> Seriously, put together some essays and/or whitepapers about this stuff, 
> explaining it. You might be able to get a job teaching, or find a 
> publisher who will pay you to write a book.  If you can write clearly 
> enough to teach complex stuff like this to youngsters, you can have a 
> pretty good career.
> 
> If nothing else, go to your local high-school and ask them if anyone 
> needs tutoring in computer programming.

Nah. Teaching requires social skills, not to mention a truly heroic 
level of self-confidence. I possess neither.

I do enjoy writing about such things... but it never seems to generate 
much of a reaction. I guess I'm the only person who cares. :-(

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Invisible wrote:

> [For anybody not already familiar with such things...
> 
> A Min Heap is a kind of binary tree that stores data in such a way that 
> retrieving the "minimum" element is an O(1) operation. Insertion and 
> deletion are both O(log n), and I believe joining two heaps should be 
> O(log n) as well.

data MinHeap x = Node x (MinHeap x) (MinHeap x) | Null

is_empty Null = True
is_empty _    = False

top (Null) = error "empty heap"
top (Node x _ _) = x

insert nx (Null) = Node x Null Null
insert nx (Node x h0 h1) = Node (min x nx) (insert (max x nx) h1) h0

delete (Null) = error "empty heap"
delete (Node _ h0 Null) = h0
delete (Node _ Null h1) = h1
delete (Node _ h0 h1) =
   let x0 = top h0; x1 = top h1
   in  if x0 < x1
         then Node x0 (delete h0) h1
         else Node x1 (delete h1) h0

> A "heap sort" involves turning something into a heap (with O(n log n) 
> complexity) and then repeatedly removing the minimum element (with O(n) 
> complexity) to yield a fully sorted list.

list_to_heap = foldl' insert Null

heap_to_list = unfoldr (\h -> if is_empty h then Nothing else (top h, 
delete h))

heap_sort = heap_to_list . list_to_heap

> To build a "Huffman tree", you start with a set of trivial 1-node trees. 
> Each tree has a probability assigned to it. The algorithm is to simply 
> select the two lowest-probability tries, remove them from the set, 
> combine them into a larger tree (with a correspondingly higher 
> probability) and insert this back into the set. Eventually you will have 
> 1 tree with Pr=1.

data Tree x =
   Leaf   {prob :: Double, symbol :: x} |
   Branch {prob :: Double, branch0, branch1 :: Tree x}

instance Eq (Tree x) where
   x == y   =   prob x == prob y

instance Ord (Tree x) where
   compare x y = compare (prob x) (prob y)

huffman :: (Ord x) => [(x,Double)] -> Tree x
huffman = top . build . setup
   where
     setup :: (Ord x) => [(x,Double)] -> MinHeap (Tree x)
     setup = list_to_heap . map (\(x,pr) -> Leaf {prob = pr, symbol = x})

     build :: (Ord x) => MinHeap (Tree x) -> Tree x
     build (Node t Null Null) = t
     build h =
       let
         (t0,h0) = (top h,  delete h)
         (t1,h1) = (top h0, delete h0)
       in insert (make_branch t0 t1) h1

     make_branch t0 t1 =
      Branch {prob = prob t0 + prob t1, branch0 = t0, branch1 = t1}

> Here ends the lesson on algorithms and data structures.]

[You knew it had to be done...]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message