Coursera: Launching Mathematical Expressions Checking

mahmud · on Sept 25, 2012

This is almost as old as automated theorem proving. There exists systems for mathematics, programming, music, essays and various analytical fields of study.

I think labeling it an "expression" checker is a good thing, as it narrows down its purpose and scope.

rz2k · on Sept 25, 2012

The database class before it was explicitly Coursera included exercises using relational algebra where any expression that produced correct answers in the general case was correct.

gosub · on Sept 25, 2012

In the symbolic case, general functional equivalence is undecidable, see: http://stackoverflow.com/questions/1132051/is-finding-the-eq....

In the numeric case, it should be enough to rewrite the question in a different form until the symbolic checker gives up.

In the practical case, trying to game the system would be more difficult than finding the actual solution.

thebooktocome · on Sept 25, 2012

I recently took Sedgewick's course on algorithms, and you wouldn't believe how hard people on the forums worked to game the grader.

scarmig · on Sept 25, 2012

Just to be clear... that's a good thing, right? =)

thebooktocome · on Sept 25, 2012

Not necessarily.

So the grader usually tested how much memory any exercise used over several data sets, and fit it to a quadratic. So one had to use, e.g., less than N^2 + 16N + 64 bytes.

One exercise specified that a data structure used ints, but the grader only tested it on values that could be stored in a short. The extra spare memory allowed for an alternate implementation using a more complicated data structure.

The point of the exercise was to figure out the somewhat trivial optimization that allowed the simpler data structure to run in roughly the same time, not to learn the more complicated data structure. After the more complicated solution was posted to the forums, there was really no incentive for people to figure out the simpler method.