Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Simple Algorithms Contest
Index -> Contests
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
zylum




PostPosted: Tue Dec 06, 2005 1:22 am   Post subject: Simple Algorithms Contest

I was thinking we could have a simple algorithms contest. They would be simple algorithms such as searching and sorting etc. Lets try a sorting contest first and see what you guys think about the format:

This contest will be for Turing only. This is because it will be hard to compare runtimes of different languages. Perhaps we will use a different language if we have another one of these contests.

Each user will submit their algorithm, a test case and a descripition of how their algorithm works.

The winner will be the person whose sum of runtimes from all the user defined test cases is the lowest. If there is a close race, the algorithms will be run multiple times and then averaged to eliminate error.

The algorithm will consist of a procedure defined as follows:

proc sort (var list : array 1..* of int, file : string)

any number of procedures may be declared but that is the one the test program will call. also, the procedure must output the sorted list in the specified file.

The userdefined data will consist of 3 cases. one for 1000 elements, the next for 10000, and finally 100000 elements. the file will contain exactly 111000 positive integers each on a separate line. the first 1000 will be case 1 the next 10k the second and the last 100l the third test case.

The description should explain how the algorithm works and why you chose it. it should showcase your algorithm and perhaps sway the judges Wink



So those are the rules. what do you guys think? anyone up for it? it should be a fast contest since its only a sorting implimentation. im hoping for some good solutions, not just bubble sort Laughing

im thinking the deadline should be sunday.
Sponsor
Sponsor
Sponsor
sponsor
md




PostPosted: Tue Dec 06, 2005 4:14 am   Post subject: (No subject)

it sounds like an interesting contest, but I think it should be open a few more languages. Open it to say turing, java, and C++; then give a winner for each category. Other then that it seems like a good idea
codemage




PostPosted: Tue Dec 06, 2005 10:51 am   Post subject: (No subject)

There needs to be a better problem than sorting. The good sorts have already been discovered and coded, ad nauseum.
zylum




PostPosted: Tue Dec 06, 2005 3:15 pm   Post subject: (No subject)

well the sorts youre thinking of are pretty basic or not very optimized. also, making your own test case makes things a bit more interesting because you can optimize your sort to your test case which can give you an upper hand... i chose sorting because we learn how to sort very early so anyone can participate but also there is lots of room for competition between more experienced programmers...

anyhoo, im working on my sorting algo and it seems to be about 50% faster than the quicksort algorithm i posted a while back on random cases. some cases i created make my algo about 10 times faster Twisted Evil
md




PostPosted: Tue Dec 06, 2005 4:39 pm   Post subject: (No subject)

Using your own cases is dumb, for instance I'll create a case where the data ia all sorted except for hte first two items which need to be swaped. I'll win anything using that case. You need a standard set of cases for testing and another set which isn't released to judge with.

I think it'd be an interesting competition, but it needs some more organization... perhaps I'll work on something instead of studying Wink
Tony




PostPosted: Tue Dec 06, 2005 4:49 pm   Post subject: (No subject)

Well the idea was that you get a crazy-good optimized time for your own case, but then you'd also have to run against every other case submitted by all the other participants, and add up the results.

The problem here is that I could write a check to recognize a certain set as my own, and output a hardcoded result, for a single lightning fast result. Depending on how large the total pool of test-cases is -- such could make a big difference in end score.
Latest from compsci.ca/blog: Tony's programming blog. DWITE - a programming contest.
[Gandalf]




PostPosted: Tue Dec 06, 2005 4:52 pm   Post subject: (No subject)

Indeed, there are some problems but it doesn't seem like a bad idea. I've always wanted to implement a sorting algorithm which I thought up, but I know it's not as efficient as possible although it is a bit unique... Still, probably won't win any contests though.
md




PostPosted: Tue Dec 06, 2005 4:57 pm   Post subject: (No subject)

I have three cases... each when uncompressed is between 100MB and 130MB. I'm thinking they'd make excellent default test cases everyone has to sort... the problem is hosting them...
Sponsor
Sponsor
Sponsor
sponsor
zylum




PostPosted: Tue Dec 06, 2005 5:09 pm   Post subject: (No subject)

Cornflake wrote:
I have three cases... each when uncompressed is between 100MB and 130MB. I'm thinking they'd make excellent default test cases everyone has to sort... the problem is hosting them...


LOL Laughing how many numbers is that ???
md




PostPosted: Tue Dec 06, 2005 5:29 pm   Post subject: (No subject)

Well... the file is 129600000 bytes in size, to taking it as 4 byte integers that's 32400000 numbers Very Happy

[edit]
A sample is here (.gz) **note that this file is compressed by a factor of more then 700 Very Happy

It's not the most random... but the most random file I have is 59MB compressed and my bandwidth just can't handle that.

[edit 2]
I've converted the file to a list of numbers instead of binary encoded numbers... but it's much to big to post; instead I'll post a program to do the conversion if people want.
zylum




PostPosted: Fri Dec 09, 2005 7:13 pm   Post subject: (No subject)

anybody gonna make any submitions? i think im just about done mine...
md




PostPosted: Fri Dec 09, 2005 7:43 pm   Post subject: (No subject)

I was... but then I got distracted by exams...
bugzpodder




PostPosted: Fri Dec 09, 2005 9:17 pm   Post subject: (No subject)

Cornflake wrote:
Using your own cases is dumb, for instance I'll create a case where the data ia all sorted except for hte first two items which need to be swaped. I'll win anything using that case. You need a standard set of cases for testing and another set which isn't released to judge with.

I think it'd be an interesting competition, but it needs some more organization... perhaps I'll work on something instead of studying Wink


you are missing the point. your algorithm needs to be all-purpose.
bugzpodder




PostPosted: Fri Dec 09, 2005 9:21 pm   Post subject: (No subject)

Cornflake wrote:
Well... the file is 129 bytes in size, to taking it as 4 byte integers that's 32400000 numbers Very Happy

[edit]
A sample is here (.gz) **note that this file is compressed by a factor of more then 700 Very Happy

It's not the most random... but the most random file I have is 59MB compressed and my bandwidth just can't handle that.

[edit 2]
I've converted the file to a list of numbers instead of binary encoded numbers... but it's much to big to post; instead I'll post a program to do the conversion if people want.


this file is too small, because it fits in memory. How about sorting a 10 Gig file of integers. anyone up for that challenge? Hint: you will spend most (almost all) of your time reading and writing to disk. The idea here is to "design" the most efficient algorithm. You dont need any implementation (since any implementation is machine dependent, really no point).
Display posts from previous:   
   Index -> Contests
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 14 Posts ]
Jump to:   


Style:  
Search: