Slashdot Mirror

Grass is a very powerful, free GIS system which is quite useful to scientists. A good GIS application can be used for any number of things such as terrain and weather modeling, migration pattern tracking, etc.

The ACM (Association for Computing Machinery) has held college-level programming competitions for many years. Though the actual problems may be at a level beyond what you are looking for, they have long ago solved the issues of how to hold such a contest.

Here is the 2001-2002 ACM International Collegiate Programming Contest page which lists, by region: a report, the standings, and the programming problems.

The basic format is to have a number of problems for the contestant teams to try and solve in a fixed amount of time. (The first one I checked out listed 8 problems for a 5-hour contest.) It included explicit problem specifications, sample input, and sample output for each problem.

I'm sure that by looking down the list, you'll find a baseline of informationt that will go well towards helping you to design your own competition. Good Luck!

In the ACMs, you get three people, four problems, four hours, and one computer.

I haven't done it yet (I'm a sophomore; its pretty difficult to get very far), but I know I will at least be going to prelims this year.

Maybe this is something profs should recommend for students that have a hard time integrating themselves. Don't force it like torture, but the competition aspect can make it pretty fun, and so non-team-oriented students might find it interesting and challenging.

GRASS has been freely available (GPL'd) for many years and has been continuously upgraded. Grass is Unix based, runs in Linux as well as others including windows. It provides both raster as well as vector capabilities. So why write a new one? For more on GRASS check out one of the mirror sites: US
Germany
Japan
(There are other mirrors as well). Billy The Mountain

It's up there, but in PDF and word2000(?) format.

Some of it is interesting, with some real world type problems. Although I could see some purists griping.

It's up there, but in PDF and word2000(?) format.

Some of it is interesting, with some real world type problems. Although I could see some purists griping.

They didn't post this year's yet, but the problem set for last year's contest is all mathematical and crunchy.

Wimps.

Back in 19[fumfer] when I entered one of these things at [Mumble] U., they included some measure of ascii graphic manipulation. You'd figure that now there would be something to do with multidimensional graphical buffering snafus or distributed client-server p2p neural interface instead of these textual brain teasers...

And when I say "I" I mean "I", as in, when I walked into the room the morning of the contest I realized only then that the format was to be Teams Of Four and I had come alone. Plus, I'd been up all night newsing and hacking already. But maybe that was a blessing because, totally zoned and running on momentum, I tied for first. Three other teams, I outright beat. I won fitty bucks to spend at the campus bookstore. I forget what I bought with it. Probably beer and a sweatshirt.

--Blair
"In space, nobody can hear you brag."

Get yourself a GPS and start mapping your favorite haunts, generate MPG animations of your travels.

Hey if you don't find a use for all 5 of those machines I might have room in my study for one

at the time, we looked at the ideas, found them confusing and foreign, we asked why. the explanation -- and a good one -- was that a strong problem-solving background will always be useful. had they taught us the 1996 idea du jour, we would have skills that were no longer useful.

so in that vein, spend a good chunk (but not all) of your time giving him or her a basis for learning.

that said, i'm a big believer in learning by doing (works for me). have the kid build a web site (i.e. backend), learn OOP (I like Python), work on some ACM contest problems and stuff.

have the kid learn other stuff, too. maybe they're the next john lennon or william gibson (i.e. music, writing, design) or whatever.

Paul

AFAIK there isn't a lot of open-source GIS code available

Actually, there is a substantial GIS known as GRASS that is open source. fink

If your interested in GPS, you may also be interested in GRASS Geographic Information System (GIS) Software. It won't help you interface your Garmin with your PC but it will let you put all that data you collect with your GPS to good use.

----------
AbiWord: The BEST opensource word processor

There is also GRASS (Geographic Resources Analysis Support System), which being a raster geographic information system can do some image processing. When maintained by the US Army Corps of Engineers, it was public domain. It is now maintained at Baylor University and is GPLed.

I wasn't at the overall contest, and didn't see the problems given, but...

I was webmaster and technical assistance for the 1999 Southeast Regional Contest. Bill Poucher came to the contest and was quite available. From my interaction with him (albeit on the side of the people administering the competition), he seemed quite reasonable and quite nice.

This is not to say that the contest ran smoothly. A more detailed account of what the tech staff went through is available.

There were some complaints, but they were handled politely, and by the end of the contest, everyone was tired but happy.

Now, back to the international contest. I don't know what happened. I can guess that the judges got hit with a salvo of complaints and joined forces to repel the assualt :) Look at it from their point of view: Some of the teams got the problem the same way you did...this validates (in your mind) your solution. Other teams struggled but didn't. They then bring accusations that the problem was unfair. There are official channels for complaints as per the rules as listed on the official site.

I said it before, and I'll repeat it. From my experience, Mr. Poucher is a decent and courteous individual. Managing a contest like this frays your nerves, and when people start bombarding you with challenges and accusations, it is easy to lose patience with them. There are also established procedures for dealing with appeals, and circumventing them by directly approaching the judges isn't likely to influence them positively.

:)


Who am I?
Why am here?
Where is the chocolate?

You would think that the hosts of the world's foremost programming competition would take the time to write its own database software with a CGI interface, or at least have the sense to use a more stable, open source package. But NO!! Here's what you get by going to the ACM finals page and clicking "Teams":


Microsoft OLE DB Provider for ODBC Drivers error '80004005'

[Microsoft][ODBC Driver Manager] Data source name not found and no default driver specified

/past/icpc2000/finals/RosterPublicFull.asp, line 11

Check out this link about the Controversy over Problem F, and look for Dominic_Mazzoni's post (+5 interesting). I'll quote from that article:

Take a look at problem F. (Here are the contest problems in PDF if you're interested.) In a nutshell, you're given a complete directed graph, and you need to return the average length of all shortest paths between all pairs of nodes. The problem explicitly stated that you will only be given graphs in which there exists a path from every node to every other.

This is not a hard problem to work out, but anyone who has had a formal course in computer science ought to recognize that the Floyd-Warshall all-pairs shortest path algorithm is designed to solve exactly this problem. Then all you have to do is add up all of the elements of the matrix and divide by n * (n-1).

Except that the judges made a mistake, and tested our input using a graph that was not connected - in other words, there were nodes that could not reach other nodes via a directed path. This would not be a big deal, except that the problem explicitly stated that this would not occur. (Input validation is never a part of this contest.) Furthermore, without further explanation it is unclear how these nonexistent paths should affect the average. It turns out that the judges' solution was not counting these paths, and averaging only the paths that existed. Some teams did this by accident, and others (including Waterloo) figured it out only after submitting multiple runs and incurring large penalties. My team was one of the many that did not figure out the judges' mistake, so we did not get credit for the problem, even though our solution was certainly correct as the problem was worded. If we had received credit we would have had four problems correct, possibly putting us in the top ten. Of course, if we had received credit right away, we might not have wasted so much time figuring out what was wrong with our solution and we could have solved another problem in that time. Of course, many other teams were in a similar situation, so I have no idea what the final ranking would have been, but clearly it would have been different.

The teams recently received letters from the contest directors, who say that they have finally decided to "personally re-examine all submissions of Problem F from the archives" and that "the results of the re-examination will be posted in the standings by April 24th."

So I'm not expecting to see any changes until April 24th, which is next Monday.

If they make any changes, teams will be bumped up to a higher position, but no team will have its position lowered. Best of all, they have changed their official policy so that in the future, teams will have access to their programs after the contest is over, and also there will be a standard procedure for regrading after the contest is over, in case this happens again.

I'm particularly happy since there's a reasonable chance that my team's score will improve, but I think everyone should be glad that they're making an effort to keep this a fair contest. I highly recommend this contest to all interested college students. If you haven't already, check out the problem set from this year.

Hi everyone! I figured while everyone was checking in and patting our friends from Waterloo on the back, i might as well join in too. Congratulations to Donny, Jeff, and Ondrej!

I did the contest once, but there are no memories of the math building's comfy lounge for me: I graduated from Computer Engineering at Waterloo in 1998. 1994 was a fun year: we went with united forces from CS and Engineering and kicked butt. Those ACM contests are really fun, though i agree with the others that judging errors do suck and some accountability would be nice.

I've known Donny from a long time ago...

-- ?!ng

I was on the CMU team. If you look at the statistics, you see that we solved 3 problems and were ranked 15th (in a tie). This is not what actually happened. We actually solved problem F correctly and did not get credit for it. At least a dozen other teams were also denied credit for a correct solution to this problem.

The controversy is that the judges and ACM contest staff still claim that there was no error in the grading of the problem, and that their datasets were consistent with the problem statement. Here's why I don't believe them.

Take a look at problem F. (Here are the contest problems in PDF if you're interested.) In a nutshell, you're given a complete directed graph, and you need to return the average length of all shortest paths between all pairs of nodes. The problem explicitly stated that you will only be given graphs in which there exists a path from every node to every other.

This is not a hard problem to work out, but anyone who has had a formal course in computer science ought to recognize that the Floyd-Warshall all-pairs shortest path algorithm is designed to solve exactly this problem. Then all you have to do is add up all of the elements of the matrix and divide by n * (n-1).

Except that the judges made a mistake, and tested our input using a graph that was not connected - in other words, there were nodes that could not reach other nodes via a directed path. This would not be a big deal, except that the problem explicitly stated that this would not occur. (Input validation is never a part of this contest.) Furthermore, without further explanation it is unclear how these nonexistent paths should affect the average. It turns out that the judges' solution was not counting these paths, and averaging only the paths that existed. Some teams did this by accident, and others (including Waterloo) figured it out only after submitting multiple runs and incurring large penalties. My team was one of the many that did not figure out the judges' mistake, so we did not get credit for the problem, even though our solution was certainly correct as the problem was worded. If we had received credit we would have had four problems correct, possibly putting us in the top ten. Of course, if we had received credit right away, we might not have wasted so much time figuring out what was wrong with our solution and we could have solved another problem in that time. Of course, many other teams were in a similar situation, so I have no idea what the final ranking would have been, but clearly it would have been different.

Now for some disclaimers.

First of all, I do not know firsthand that the judges had an incorrect data set, because their policy is not to release the data sets they use to test our programs. However, literally dozens of the 60 teams there encountered this error and many of them gained serious evidence that this was in fact the exact error. For example, one person showed me code he had written that would cause the program to seg fault if and only if the graph was not connected. He turned it in, and he got "runtime error" from the judges, indicating his program crashed. When he removed that line, he got "wrong answer". Even the team from Waterloo agreed that the data set was faulty.

Also, I am not trying to imply that the teams that did win did not deserve it. All of the top teams did an excellent job and deserve to be congratulated. I'm mostly upset that the ACM contest staff will not either admit there was an error, or release the datasets to prove there wasn't one.

Dominic

I was on the Stanford team (we sucked badly), and I must say it is the most frustrating thing to have a solution which works for every testcase you can think of, but is still rejected by the judges. And very demoralizing to watch eventual winner St. Petersburg State University sitting at the table next to yours and racking up the balloons (one for each problem solved).

One coach at the contest noted that, for U.S. teams, the teams are often formed by students having a local contest and just picking the students who do the best. The students then go off and find someone to be their "coach" for registration purposes only. Whereas for non-U.S. teams, there is usually a prof who is very active as coach, who coordinates team practices and such, and sometimes hand-picks the team members. Not sure how much of an effect this has on team performance.

I decided not to mod this comment down, but rather post this comment . . . . otherwise, nobody would understand.

This is propaganda. There is no basis, no links, no hard evidience. Punch the CDA and McCain through your favorite search engine and see what it finds.

In FACT, McCain was reported to say any new measure that resembled the Communications Decency Act probably would not survive his committee, which oversees telecommunications. Furthermore, he's quoted as saying:

"I'm the father of small children, they all are far more computer literate than I am, and I've seen some of the stuff that they see and it disturbs me terribly. But I didn't know how you would implement that [law]. I didn't know who would decide what's decent."

McCain did endorse a bill that required schools and libraries with federally funded internet access, which I won't debate here. A bit more info on that bill is located here

In reality, the original sponsor behind the 1996 CDA was Senator Pressler. More information on authors of specific portions of the CDA are here.
McCain did add a lot of amendments to the bill, but so did everyone in the Senate. How else did the thing pass?? I'm not sure exactly what his changes entailed, but you can find out here.

Somebody mod the parent comment down into the flamebait category. It's nothing more than a sweeping piece political propaganda without backing at all.

And as much as I also idolized Grace Hopper and Ada Lovelace, bringing up their names in these kind of discussions only adds to the false impression that there are no current women computer scientists. The problem is not simply one of lack of gender parity in the field of computing (though that is a problem), but also lack of adequate recognition.

As for the open source community, I don't know why there appears to be a larger gender parity problem here, if indeed there is one. I can tell you why I'm not part of the open source movement, as much as I admire it: because my life is already full. I have about 12 hours per day available for computer science; 8-10 is already taken up working at a technical job that lights my fire and pays me money. (unix systems administrator, primarily solaris, if you're curious.) The other two or so are taken up coaching for programming team, something else I'm passionate about. My other four waking hours a day tend to get spent on grooming, eating, and socializing. :-) So as you see, my "problem" is far from being not interested, as other posters have suggested. It's being interested in far too many aspects of computer science, and settling on ones that don't necessarily interest you.

There is plenty of free image processing software out there - if you're old school try GRASS, if you want to get involved in the development of a more modern system try LIMP.

Nick