JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Implementation practice | Reply
So I spent most of Thanksgiving weekend relaxing. And by that I mean "studying algorithms" because I really am a geek. And I feel much more relaxed now.

Anyway, I studied max flow and bipartite matching. I realized that bipartite matching is the first algorithm complicated enough that I should try some "implementation practice" - by which I mean simply repeatedly typing in the algorithm from scratch to see how long it takes to get it working. After the first one (which was a bit of time), the implementation times I had for Ford-Fulkerson were (in a row): 19 minutes, 11 minutes, 7 minutes. I tried also with a standard BFS and got 11 minutes, 5 minutes, 3 minutes.

How curious...

I'm not sure how useful this exercise is, but it appears to have some value. I haven't done part two of the experiment, which is to repeat the experiment in a couple days and see if I have times similar to or better than the first.

Anyway, I was struck by the shape of the curve. Thoughts?
Re: Implementation practice (response to post by eraserhd) | Reply
'Anyway, I was struck by the shape of the curve. Thoughts?'

I should sit on my ass and implement this shit at last... ;)
Re: Implementation practice (response to post by eraserhd) | Reply
My current implementation of max flow is about 260 days old. That is when I first coded it and so far I haven't gotten around to doing it a second time. I did plan to do it again on a number of times but i never got around to actually writing them so my current results:
30 minutes, infinity, infinity, ...
My thoughts: do that later...
Re: Implementation practice (response to post by karpio) | Reply
Very eloquent.
Re: Implementation practice (response to post by otinn) | Reply
Like tomorrow?
Re: Implementation practice (response to post by ilham) | Reply
Probably in the upcoming months ;-)
Re: Implementation practice (response to post by otinn) | Reply
Hahaha. "Tomorrow" is what the Javanese (people from the Java Island) usually use to depict the same situation :)
Re: Implementation practice (response to post by ilham) | Reply
You should aware that there are Javaneses here ;)
Re: Implementation practice (response to post by ilham) | Reply
Wow! They made an island called Java!
Re: Implementation practice (response to post by Malkava) | Reply
Oh my. So many jokes I could make. Let's go with this one:

"Yes, it's about 100 miles off of its populating ancestor Cape Smalltalk, although the native Smalltalkians frequently wonder if there's any purpose to the odd rituals the Javanese have acquired."
Re: Implementation practice (response to post by Malkava) | Reply
Probably I should change my default language to Java to make me truly Javanese.
Re: Implementation practice (response to post by eraserhd) | Reply
As if Smalltalk wasn't an odd ritual itself. (The programming language and the activity.)
Re: Implementation practice (response to post by karpio) | Reply
Hey c'mon, please keep it clean. "You know, for the kids".
Re: Implementation practice (response to post by eraserhd) | Reply
The results are in from the second half of the experiment. The original times above were from my memory, which is apparently not so good :)

DateProblemCoding Time
Fri Nov 23 10:33:23 2007
BFS.cpp11:10
Fri Nov 23 10:45:04 2007
BFS.cpp05:35
Fri Nov 23 10:59:27 2007
BFS.cpp04:11
Fri Nov 23 11:06:38 2007
BFS.cpp03:37
Fri Nov 23 13:01:52 2007
FordFulkerson.cpp34:37
Fri Nov 23 13:37:18 2007
FordFulkerson.cpp11:53
Fri Nov 23 14:42:36 2007
FordFulkerson.cpp06:56
Tue Dec 4 21:30:03 2007
BFS.cpp06:22
Tue Dec 4 22:03:26 2007
BFS.cpp04:47
Tue Dec 4 22:08:56 2007
BFS.cpp03:26
Tue Dec 4 22:13:57 2007
BFS.cpp03:02
Tue Dec 4 22:46:49 2007
FordFulkerson.cpp17:43
Tue Dec 4 23:23:11 2007
FordFulkerson.cpp06:45
Wed Dec 5 17:30:41 2007
FordFulkerson.cpp05:23


I think this means that implementation practice (aside from the problem-solving stuff) is useful for SRMs.
RSS