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?