Example algorithms for first class in programming for EE students 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:


Naïve modular exponentiation vs. left-to-right modular exponentiation
Linear search vs. binary search
Trial division vs. sieve of Erathosthenes (for creating a list of primes from, say, 1 to 100)
Naïve polynomial evaluation vs. Horner's rule
GCD by factoring vs. Euclid's GCD
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?
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.