Computer Science Canada Topic for a turing contest! |
| Author: | Token [ Fri Mar 11, 2005 12:05 pm ] |
| Post subject: | Topic for a turing contest! |
Hey everyone, i would like to start a contest but i was talking to tony and he said i would get more submissions if i had a theme, what would you people like to see for this contest theme, please give me some ideas |
|
| Author: | thegoose [ Fri Mar 11, 2005 2:48 pm ] |
| Post subject: | |
Approximation algorithms for NP-complete problems (sort of like the IPSC) |
|
| Author: | Token [ Fri Mar 11, 2005 3:17 pm ] |
| Post subject: | |
what are those? could somone please elaborate? |
|
| Author: | thegoose [ Fri Mar 11, 2005 3:22 pm ] |
| Post subject: | |
Basically, NP complete problems are problems such that no efficient (polynomial time) solving algorithms have been found. The approximation algorithms for such problems are usually very intuitive and nice (usually a simple strategy that performs much better than the back-tracking algorithms). I think this would be a good idea because this type of problems requires the least programming background and the most intuition. An example of such a problem is found on the following link: http://olympiads.win.tue.nl/ioi/ioi2003/contest/day1/reverse/reverse.pdf solution: http://olympiads.win.tue.nl/ioi/ioi2003/contest/day1/reverse/data-reverse.pdf This is a hard problem if you don't see the idea but if you see it, the solution becomes obvious. As a sidenote, somebody in my class who never took computer science managed to get 100/100 on it while I only got 49/100 when I first did it. |
|
| Author: | Aidin Kashigar [ Fri Mar 11, 2005 4:25 pm ] |
| Post subject: | |
lol. i think you'd get way more submission by dropping the turing thingy and opening it up to all languages. As far as the theme goes, the typical Farmer John and his wonderful, yet computer-deprived, cows (in USACO contests) seems to work well with lots of people. |
|
| Author: | Token [ Fri Mar 11, 2005 4:31 pm ] |
| Post subject: | |
the thing with that is that it will be hard to compare the programs against each other, because its easier to do certian things in certian programming languages whereas others it is harder |
|
| Author: | Tony [ Fri Mar 11, 2005 4:51 pm ] |
| Post subject: | |
Token wrote: its easier to do certian things in certian programming languages whereas others it is harder
well that's part of programming. A skillful programmer will know which language to better approach those certain parts with. Most applications are made in more than one language. Personally I combine two for my work projects. |
|
| Author: | thegoose [ Fri Mar 11, 2005 5:09 pm ] |
| Post subject: | |
Token wrote: the thing with that is that it will be hard to compare the programs against each other, because its easier to do certian things in certian programming languages whereas others it is harder
That's why I think it would be a good idea to make the problems output-only. i.e. you give out the input files, you ask for the output files rather than the program. Also, there is already a student-run contest (DWITE II, very original name), we currently have me, Aidin and Simon making the problems (and 2 other consultants) with the next contest being somewhere near the end of March. If you guys would like to contribute, please contact one of us. |
|