Looking for good bonus quiz to test efficiency (specifically efficiency related to time)

Question

I am doing a Introductory to Computer Science lab once a week. I was hoping to have a quick contest at the end of my next lab. I want to give them a block of code like this:

public class EfficientCode{

    public static void main(){
        long startTime, endTime, executionTime;
        startTime = System.currentTimeMillis();

        yourEfficientMethod():
        endTime = System.currentTimeMillis();
        executionTime = endTime – startTime;

    }

    public static void doSomething(){
        // you do this part.  
    }

}

They will implement the doSomething method and the person with the fastest code will get a handful of bonus marks.

The problem is that the question needs to be somewhat simple. The students have a good grasp of: loops, if/else, Strings, adding, arrays, etc.

Here are my ideas for what the question could be:

• find all the perfect numbers between 1 and 1,000,000. (A perfect number is a number where all of the number's factors add up to the number. Ie: 6 = 3 + 2 + 1)
• find all prime numbers between 1 and 1,000,000

I think in order for there to be a measurable difference in performance between methods you must do something many times.

Answer 1

Because this is an introductory class and your students haven't covered sorting yet I think it's going to be very hard to come up with something simple enough to do, interesting enough to have a few different ways of doing it, and complex enough that there is an appreciable difference in speed between the different implementations on a modern computer. Your real problem, though, is that anything simple enough for them to try already has a canonical implementation only a short Google search away.

My suggestion is to invert the challenge. Have your students compete to come up with the gnarliest, slowest, most memory hogging solution they can think of. I believe it's as educationally valuable to think about all the wrong ways of doing something as it is to think about the right, and it's just as hard to be the worst as it is to be the best. It's easier to see results subjectively as well since bad code will be really slow. No Googling for an answer either. Finally, in my (irrelevant) opinion, this has the added bonus of making the challenge more fun.

Something like finding a string within another string is easier made bad than good. Maybe have them extract all the prime numbers from a 2kb string of random alphanumeric characters. Lots of ways to make a pig's ear of that problem.