I am professor of Electrical Engineering who will teach, for my first time, a class to first-year EE students about programming. This will be their first contact in an academic setting with programming, algorithms, data structures, etc.

When introducing the subject of algorithms, I'd like to present a few problems, give a naïve algorithm that might be the first thing that comes to mind to solve it, and then show an efficient algorithm that is clearly more efficient than the naïve one. Ideally, something that none of the students might come up with on their own. Obviously, being their first class in programming, I can't use overly complicated algorithms or I'll run the risk of confusing rather than illuminating them.

Right now I've collected a few examples:

  1. Naïve modular exponentiation vs. left-to-right modular exponentiation
  2. Linear search vs. binary search
  3. Trial division vs. sieve of Erathosthenes (for creating a list of primes from, say, 1 to 100)
  4. Naïve polynomial evaluation vs. Horner's rule
  5. GCD by factoring vs. Euclid's GCD
  6. Schoolbook multiplication vs. Karatsuba multiplication

Of these, (1) and (2) I believe students could come up on their own, and maybe (3) and (4) as well. (5) and (6), I'd risk saying most wouldn't come up with on their own.

What other algorithms could I use to demonstrate the importance of efficient algorithms? Also, would anyone advise against using one of the examples I've listed above, and for what reason?

  • 1
    $\begingroup$ What research have you done? There are lots of introductory CS courses and CS courses on algorithms. Why don't you start by reviewing some of them to gain better understanding of what others have tried? $\endgroup$ – D.W. Jun 12 '14 at 20:54
  • $\begingroup$ The classic example is bubble sort vs. basically any other standard sorting algorithm $\endgroup$ – Nick Alger Jun 12 '14 at 21:40
  • $\begingroup$ think this isnt a bad question & maybe even works as a reference question. feel there are really not a huge number of algorithms that fit here & that this is a basic lesson in CS that deserves attn.... however there are 4 kill votes as "too broad"... so poof $\endgroup$ – vzn Jun 12 '14 at 21:55
  • $\begingroup$ Allow me to respectfully disagree that the question is too broad, as argued by vzn. Good answers wouldn't be too long for the format, as shown by the sole answer below. As for having too many possible answers: are there really that many algorithms that 1. can be explained to students with no prior programming experience and 2. are exponentially more efficient than a naïve version (e.g. ordinary exponentiation vs. binary exponentiation)? I've thought about this for days and only came up with the examples above. $\endgroup$ – swineone Jun 13 '14 at 2:02

My favorite example of the value of efficiency is Fibonacci number computation. A naive programmer could use the recursive top-down solution, which takes exponential time. A bottom-up iterative solution, on the other hand, runs in linear time.

  • $\begingroup$ This possibility had crossed my mind, but I decided not to use it because students won't be familiar with recursion at this point, and the inefficiency of the recursive version is an artifact of the use of recursion itself. Summing up, I don't think this would be helpful in making the point I'm trying to make. $\endgroup$ – swineone Jun 12 '14 at 22:04
  • $\begingroup$ like fibonnacci sequence also because there are various ways to compute it & it can also be contrasted with the mathematical formula (Binet's formula). fibonacci sequence can be done without recursion using "memoization".... $\endgroup$ – vzn Jun 12 '14 at 22:46

Not the answer you're looking for? Browse other questions tagged or ask your own question.