5

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.

false
  • 10,264
  • 13
  • 101
  • 209
sixtyfootersdude
  • 25,859
  • 43
  • 145
  • 213
  • Might this question be more appropriate for http://programmers.stackexchange.com? – user85461 Jan 23 '11 at 02:18
  • 2
    Am I reading this right? You're teaching the course and you are asking "I think in order for there to be a measurable difference in performance between methods you must do something many times."? – Mitch Wheat Jan 23 '11 at 02:18
  • You'll need to be careful to specify strict guidelines and parameters as to what is acceptable. I'd just hard-code a list of the perfect/prime numbers, and have it print that. No code will beat that. Arguably, I shouldn't be awarded bonus points (I'd argue differently were I in the class, but either way, that's something you need to address *before* someone tries it.) – Cody Gray - on strike Jan 23 '11 at 04:09
  • Sorry, but I don't think this is a good question to ask beginning students. Before they get into data structures and algorithms, I'm not sure there's much serious stuff they can do that can take much time. Sure, maybe you can have them do something like hunt for primes, but who does that for real? My suggestion - keep it real. – Mike Dunlavey Jan 23 '11 at 16:29

5 Answers5

7

Agreed about 'many times' for short operations, but for longer ones, once might be enough on its own.

I suggest looking into Project Euler, an excellent collection of programming questions. The best part is that the problems are designed with a "one minute rule" in mind, that most problems should take a moderate computer less than one minute to execute an efficient algorithm to find the answers. So an excellent place to start. :)

sarnold
  • 102,305
  • 22
  • 181
  • 238
4

Two things.

First, efficiency is about more than execution time. It also is about memory usage, memory access, file-system/resource access, etc. There are tons of things that go into efficiency. So please be explicit that you're looking for the routine with the shortest run-time. Otherwise you are sending a mixed message...

Second, I heard this problem about 15 years ago, and I can't forget it:

Produce a list of all 5-digit number pairs that sum to 121212. However, neither of the 2 numbers can repeat a decimal digit. So 1 can only appear once in either number. So an example result pair is 98167 + 23045. There are a fair number, and it's easy to build a brute-force solution, but an efficient solution requires some thought. There are 192 unique pairs...

ircmaxell
  • 163,128
  • 34
  • 264
  • 314
  • good point about efficiency being more than time. I know this but I will be careful to be explicit about it when I present the question. – sixtyfootersdude Jan 23 '11 at 03:19
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.

Tim
  • 5,024
  • 2
  • 30
  • 58
0

Those are good ideas. What about having a sorting question?

David Weiser
  • 5,190
  • 4
  • 28
  • 35
0

Sorting an array of numbers might also be a good idea, since there are a whole bunch of algorithms for it (insertion, selection, quick, heap, etc.) that all have different performance characteristics. This would also give students a chance to learn about big-O notation, etc.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065