Specialist programming modules and algorithm efficiency

[c***@wmin.ac.uk]

Hi everyone. I'm told that this is a good place to discuss university
level programming modules.

Over the next year I'll be teaching a module on "Audio Application
Development" using Java and JSyn. JSyn is a package for electronic
music synthesis (native code) in Java. The students will mostly not
have programmed before. Hence I have to teach a basis in Java before I
start showing them how to do the electronic music bits. I have a
lecture schedule prepared that I believe balances these two aims, and
gives them sufficient grounding before we start on basic beeps, buzzes,
and whooshes (to use the technical terms :-) ).

Here's my question. One thing that concerns me about programming
modules nowdays is that sometimes at least there's a lack of coverage
of issues such as good program design and algorithm efficiency. I hope
to at least mention such issues such as top down or bottom up program
design in the more advanced sections of the course in the context of
sample applications. However, program efficiency is where it's more
difficult to create an example. In my current notes, I have a single
lecture on sorting, which describes bubblesort, and then mergesort. I
then show (more in an arm-waving way than a general proof) that
bubblesort is O(n^2) but mergesort is O(n log n ). I then mention
heapsort as being O(n log n) without requiring additional space and
talk about time and space efficiency.

To include this lecture in the module, naturally other things are not
included. At present my default action is to leave the efficiency
lecture in, and perhaps create "additional" unexamined notes for
"ghost" lectures that won't be given (I do this quite frequently in my
modules) covering the material that I'm missing out. If I kicked out
the efficiency lecture, the notes would still be made available to the
students.

I'd like to hear people's comments on the importance on including at
least a mention of algorithm efficiency in special purpose programming
modules.

Cheers,

Ross -c

[Brian Harvey]

Post by c***@wmin.ac.uk
I'd like to hear people's comments on the importance on including at
least a mention of algorithm efficiency in special purpose programming
modules.

Imho you shouldn't ask such a general question; instead you should look at
your students' homework submissions. If they are turning in Theta(n^2)
solutions to problems for which there is a Theta(n) solution, then you need
a lecture on efficiency. If not, not.

By the way, I would can bubblesort (since it's pretty complicated even to
convince yourself that it actually sorts correctly) in favor of insertion or
selection sort, and I would can heapsort because you don't need two n log n
ones, and in these days of unlimited free memory it's silly to worry about
a factor of 2 -- not even an order of growth issue -- in memory use.
This way you need only half a lecture. :-)

[c***@wmin.ac.uk]

The module I will be teaching will not require the students to do any
real algorithm design. It's actually an electronic music module.
However it is likely that the students will not study programming in
any other module. Having learnt programming myself some time ago I
believe that at least an awareness of efficiency issues and algorithm
design is really important.

The lecture doesn't cover heapsort, only bubblesort and mergesort. The
students are asked to implement heapsort in a practical session that
will follow the lecture. I take note of your point about insertionsort
or selectionsort, but the real question is whether I have nothing on
algorithm design and include additional synthesis background, or
whether I include the sorting lecture.

Cheers,

Ross-c