What is the best way to introduce algorithms to undergraduate students?

Question

If you are given the task of designing the courses leading up to a degree in computer science and are allowed just two courses on the topic of 'Algorithms', how would you structure the courses? My specific questions are:

1. Should the first course introduce some of the fundamental algorithms of Sorting and Searching without introducing the notions of time and space complexity?
2. A second course on designing algorithms. This course would cover not only time and space complexities but also generic algorithm design techniques such as Divide and Conquer, Dynamic Programming etc..

This is the typical profile of the students I am designing this course for:

1. Most would be new to the notion of programming though familiar with the use of computers.
2. They would be learning C programming in the same semester that they learn about algorithms.
3. They Would be taking a simultaneous course on introduction to computer science.

Most of the text books I have considered are either too voluminous or too intimidating for the student with over emphasis on the analysis of the complexity of algorithms.

Any suggestions on either the appropriate text books or methodology for teaching would be appreciated!

Answer 1

This isn't a solution to your whole question, but something interesting to consider as a teaching/learning experience - if you want to be really memorable but potentially time consuming find somewhere with a lot of space and get your students to sort themselves - put everyone in a line and then let them walk through a few different sorting algorithms. If you have enough students you could even try racing different sorts against each other. The amount of walking around involved would give an idea of complexity as well.

As a lesson it would be a little chaotic, but I would bet good money that every student in those lectures would remember them. It could be a good way to start a basic course as it also gives the students a chance to meet each other and establishes your lectures as potentially interesting to attend.

Answer 2

"What is the best way to introduce algorithms to undergraduates?"

• Fundamental data structures
• • What is an array
• • What is a node
• • • What is a linked list
• • • What is a binary tree
• • • • Binary tree as an array (2n, 2n+1)
• Exploring those data structures
• • How to iterate through an array
• • How to transverse a linked list
• • • Singly linked vs doubly linked
• • How to recurse through a binary tree
• • • Breadth first, depth first ...
• Simple algorithms (beginner)
• • Find the min/max value
• • • Compare/contrast array (sorted/unsorted), linked list, binary tree
• • Searching for a value
• • • Compare/contrast array (sorted/unsorted binary search), binary tree
• Sorting algorithms (in this order) (beginner - intermediate)
• • Briefly cover Big O notation
• • • Relate to the previous search/find algorithms
• • Bubble sort
• • • The easiest but least efficient
• • Radix sort
• • • The fastest but only in certain situations (integers vs long varied strings)
• • Quick sort (most time on this one)
• • • Divide and conquer
• • Heap sort, insertion sort (if you have time)
• • • Reinforce concepts from earlier
• Graph algorithms (more advanced)
• • Concept of NP hard
• • Path finding
• • • Shortest path vs finding any correct path

That's more than enough for one semester.

Regarding how to present the ideas to the students. A lot of animations and illistrations exist (online/wikipedia/google image) for searching, sorting and path finding algorithms. Present them to the students and step through them one frame at a time with explanation.

DON'T INSULT THEIR INTELLIGENCE with the junior/high school "how to make a sandwich" or have them stand in a line and sort themselves. Just start off with something like "an algorithm is the series of logical steps to complete a task". After a lesson or two "some algorithms are more efficient than others".

Answer 3

I would focus your first course around putting them in the mindframe of a programmer. By that I mean, use examples to demonstrate why you couldn't just tell a robot to make you a sandwich, that you'd have to specify that you'd want cheese and ham and the white bread and where to find them and how to put them together. Walk them through the problem of sorting the names of four countries in alphabetical order (being sure that at least two share the first letter and are not in order at the start). Tell them the rules are, you can swap the positions of any two countries. The most obvious method they will use to sort will be insertion sort, so you can tell them that's exactly what they've done.

Then you could probably move onto data structures and how you could balance a binary tree for instance. Again, you don't have to tell them how to implement it. All of this can be kept completely abstract simply by drawing its representation on the board. Allow the students to suggest how to do it and be sure to cut them off if they attempt to overgeneralize or "cut steps" by saying "So how do you do that?" Keep them in "critical thinking" mode, which is to say, let them reason through why something is done in a specific way or why computers can't simply be told what to do in plain english, all the while dropping hints of complexity which you'd cover in your next course.

In your next course, with the same country sort (perhaps with 6 countries rather than 4), let them suggest insertion sort and write down the number of swaps done. Then show them how they can do the same thing using divide and conquer, all the meanwhile keep track of the number of swaps done. Demonstrate that it took more swaps to do it one way than another and that this is what's called algorithm complexity, which is an excellent lead-in to discussion to why algorithm complexity is important to consider (why you would start in the middle of a phone book to look for a name rather than at the first page and flip one at a time, for instance.. binary searching).

As for a textbook, I would recommend Introduction to Algorithms. It would probably cover both courses entirely aside from perhaps data structures, but I think that's important to demonstrate the types of problems programmers face with different data structures.

Answer 4

Try this exercise;

you need: grid paper or a grid on a board a group being the 'programmers' a group being the 'computers'

instructions: the programmers must instruct the computers to draw a cat, dog, whatever using only circles, triangles, squares and lines, and coordinates.

example: at line (5,5), draw a 1x1 circle

obviously the computers don't know what the end result will be :)

it helps them understand how to think about a problem in such small steps (which is actually really difficult for people), and put themselves on the receiving end of specific instructions. in other words, some instructions are better than others.

ps i graduated from computer science 6 years ago and this example, done in 1st year, was helpful

Answer 5

1. Should the first course introduce some of the fundamental algorithms of Sorting and Searching without introducing the notions of time and space complexity?

You should not, it would quite much obscure what the point of having different sorting algorithms is.

But you know, they surely could accept that they get an approximate figure (Big-O notation - it'll be enough to have an ordered table for the complexity classes in Big-O as reference) for the "best" and "worst" case of the algorithms now. The actual methodology for doing the complexity analysis could be delivered later.

This will not be a problem as long as your students don't have to learn these values by heart for the test(s), but get / can use reference sheets.

1. A second course on designing algorithms. This course would cover not only time and space complexities but also generic algorithm design techniques such as Divide and Conquer, Dynamic Programming etc..

I'm not sure doing this while they are not yet familiar with C or any other programming language is clever. In effect, a little of this probably should be taught in the C course, the rest only after they have basic skills with at least one language and the programming tools they use to program it (including especially the debugger(s)).

Most of the text books I have considered are either too voluminous or too intimidating for the student with over emphasis on the analysis of the complexity of algorithms.

I think students get a bit upset about buying expensive books for one semester only for cost reasons, or lecturers expecting them to learn too much, or it being unclear what degree of knowledge actually is required in tests. If you take care to avoid this, a big book is fine, even desirable.

I wouldn't shy away from recommending (or maybe requiring) something like "Introduction to Algorithms" by Cormen et al. (and similarly large works for maths and so on) as teaching and reference material.

As a general doctrine, it is just really a good idea to pretend you're coaching students more or less specifically to pass a specific, not terribly low or high standards test you have in mind. You're simply trying to offer time-efficient learning to that end. If a diagram doesn't seem good, do another better one, if some section in a book doesn't seem straight-forward or coherent or goes too far off the scope of the course, do your own. But you probably still require a good, detailed book as catch-all and provider of good text, because you aren't quite perfect.

Answer 6

I can only speak from a personal point of view, and how I like to learn things. I'm a recent graduate so University is still fresh in my head, and to be honest I would be very critical of my University's methods towards teaching algorithms. I don't feel like I understand algorithm complexity, big O notation etc well enough.

Personally I find it easiest to learn by example, and learn by doing. I don't like listening to a lecturer drone on about theory, I'd prefer to see an example algorithm (sorting or something) and then the lecturer going through it and explaining how the complexity is worked out etc.

If they are learning a programming language at the same time then I'd prefer to see the algorithm in that language rather than some sort of pseudo-code (because pseudo-code just introduces unneeded uncertainties for students - if they can relate directly to how they'd code it themselves it helps IMO).

So, if it were me, and I had 2 lectures on it, I'd like the first to introduce some of the more popular algorithms, go through them and briefly talk about the complexity.

During the second then you could go into complexity analysis in more detail and then into designing algorithms with complexity in mind (so saying things like "why is it better to do this piece of functionality this way than that way"), maybe getting students to give suggestions.

Answer 7

Make sure you offer the material in more then one form! Not everone (as is demonstrated in the other answers) learns the same way. So both have a short lecture, play the drawing game mentioned in one of the answers, have some problems to solve, etc.

Answer 8

My school has two courses: Data Structures & Programming Technique, and Design & Analysis of Algorithms. The first course covers everything you mentioned (sorting, searching, greedy algo's, divide & conquer, dynamic programming, hashing and data structures like stacks, queues, tries, trees..).

Data Structures, however, also covers C programming and our assignments involved using some sort of data structure/algorithm to write a C program (bin packing, boggle, remove comments from C code, etc). We covered run-time analysis, but we didn't really prove properties of algorithms or anything like that.

The other course (which I haven't taken yet), is basically a proof based in-depth version of the first one. There's no programming involved, so it's all entirely on understanding the concepts. There's also a much bigger focus on graph theory.

Answer 9

I suggest you appeal to their inteligence and look at optimisation problems, however simple.

Show an example of a sort or something else where it takes a long time, then a couple of different solutions with better times.

Give them the idea that memory use or speed is the goal, maybe stick to just speed to keep it simple, and challenge them.

Answer 10

My suggestion on setting up these courses:

1. First course would be Algorithms and Data Structures. There would be an introduction to big-O and complexity as well as learning various Data Structures like Queues, Stacks, and Heaps so that there is something to use as examples for these. This doesn't get too high up in the theoretical stuff but does cover some basics on why there are some data structures and what advantages do some of these have. There could even be a list of various heuristics behind algorithms like being greedy, divide and conquer, dynamic programming, etc.

2. Second course would be on complexity classes and more theoretical material. Covering NP-complete, P, and other subjects here. Sorting here could be studied in terms of showing the O(n log n) bound while in the other course giving different sorting methods,e.g. Quick, Bubble, Heap, Merge, and Shell, is the point.

Answer 11

The classic (and possibly best) book on the subject is Niklaus Wirth's Algorithms + Data Structures = Programs.

Answer 12

Many years ago now I saw bubble sort in an introductory programming course, with a warning that there were far better methods for sorting. It looked a reasonable enough method, and I couldn't think of any obvious improvements - so my fascination with algorithms started when I saw a description of heapsort. Based on this experience, I would display sorting or some other problem where you can show a significant performance improvement coming from an easily explained idea.

Collection classes solve a huge number of everyday algorithmic problems, and more specialised libraries are also available. I think you should consider emphasising simple analysis of algorithms - so that students don't write N^2 algorithms without meaning to - and the use of existing packages, including understanding their complexity, over implementing basic algorithms from scratch. Alas, I will not earn my living by rewriting heapsort in a succession of different programming languages and systems. OTOH I have been paid for profiling systems with performance problems and looking for quick wins.