Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Simple Algorithms Contest
Author Message
zylum

Posted: 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

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

im thinking the deadline should be sunday.

md

Posted: 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

Posted: 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

Posted: 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
md

Posted: 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
Tony

Posted: 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.
Tony's programming blog. DWITE - a programming contest.
[Gandalf]

Posted: 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

Posted: 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...

zylum

Posted: 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 how many numbers is that ???
md

Posted: 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

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

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

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

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

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

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

Posted: 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

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

Posted: 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

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

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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 14 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: