Difficulty of algorithms homework problems

Question

I have a question for educators, from the perspective of a TA. I'm happy to post my question elsewhere if it's not appropriate for this site.

Homework problems in algorithms classes often involve finding clever tricks that the professors find elegant or interesting. However, it seems like most of the students who solve these problems well are students who are familiar with the tricks already, from prior experience. Students who don't know the tricks end up going to office hours, where the TA has to guide them through most of the solution, and the students are left confused about how they could possibly have derived the solution independently.

This seems like a discouraging pattern, especially because, in the end, research usually involves deep logic and understanding, but students come away feeling like algorithms is simply full of these impossible, clever leaps. Is there a way to help students catch up on these tricks and tools without giving away the answers?

Answer 1

Homework problems in algorithms classes often involve finding clever tricks that the professors find elegant or interesting

That seems like a strange way of teaching algorithms. It shouldn't involve trying to make the students recreate brilliant ideas from scratch (most people won't re-invent Dijkstra's algorithm when asked to find the shortest path through a graph), but rather teaching them which building blocks exist, showing them how (simple) problems can be solved using these building blocks, and then offering them related problems whose solutions are similar.

However, it seems like most of the students who solve these problems well are students who are familiar with the tricks already, from prior experience.

In my mind, the thing your professors do get right is the idea that algorithm design isn't a algorithm itself. I believe it is to a large degree a question of experience. You build a repertoire of "tricks" that work, and then you apply them in new circumstances. What kind of "tricks"? An important aspect is about knowing what kinds of data structures fit the problem.

Is there a way to help students catch up on these tricks and tools without giving away the answers?

As I've said, I believe programming/algorithm design is a craft, not a science. Having mentioned Dijkstra, I don't believe in his approach to algorithm design. He was very methodical and mathematical and seems to have looked at algorithms as basically a mathematical problem to solve. While this is certainly true and often offers valuable insights when dealing with difficult problems, I don't think most people work like that. If programming is a craft, then it is best learned by imitation and lots of practice.

Unfortunately, we don't have nearly enough time to let students practice, but one thing you can do is tell them how important it is to look at how other people solved problems, and provide them with good resources they can use to learn by imitation. Here's a nice one: Beautiful code.

So, to actually answer your question:

• Make sure the students have a good working knowledge of the basics (e.g. how to iterate over a list, how to manipulate list entries etc)

• Present a sequence of problems that lead up to the final problem. For the preliminary problems, explain what kinds of data structures are used and why, and how the algorithm operates on them.

• Encourage the students to look at other people's code. Good candidates are algorithms which solve a certain problem in a way that is applicable to a lot of other domains. (For example, I first learned about atomic commits by reading a description of how subversion worked. This came in handy when I thought about how to implement database transactions. It was also closely mirrored in the way git builds hash trees, which again is closely mirrored by the bitcoin blockchain).

• Finally, explain to them that you can just show them the way, but just like learning to play a musical instrument, or a sport, they'll have to invest their own time if they want to become any good.

Answer 2

I had zero experience with algorithms when I started. Here are a couple of things I wish had been done differently.

Let Students Make Mistakes
My TAs and professors always tried to guide me to the best answer, show me the right "trick", or stop me from making a mistake before I actually made it. Whenever I'm helping someone out with CS now, I usually let them make the mistake. Nine times out of ten, there is something they have to do later in the assignment that won't work because of that mistake. And while we are troubleshooting the problem, they'll have that "ah-ha" moment and see why what they did was wrong. Sure it takes longer. However, I've found that it teaches students what to consider when making programming decisions. As they practice, they will be able to think through and handle those considerations more quickly. Essentially, you put in that extra time upfront and it pays off in the long-run.

Re-think Using "Starter Code"
Not sure if you do this, but my TAs and professors used "starter code" a lot (code that is partially written by the professor, then the student fills in the missing pieces). I personally believe that learning how to understand other people's logic and code is a skill in itself. Trying to do that and studying algorithms seems like a lot for someone new to algorithms to take on. Anyway, I decided to practice algorithms on my own without starter code, and I got a lot better at them. I wrote anything I could from scratch based of logic, descriptions, logic diagrams or pseudocode. Then I could look at traditional approaches to see where my approach could be improved or optimized.

I know these things take more time that a lot of educators don't have. But I wanted to point out a couple of "time savers" that actually hurt me (and a few people I've met and tutored) while studying algorithms.

Answer 3

I can offer two ideas here. The first is to try, whenever possible, to use some real world metaphor for the technical problem at hand. Railway sidings, card shuffling, etc. Some instructors use these as a matter of course in introducing a new algorithmic concept.

But if you want a thorough study of how to approach and develop algorithms, get a copy of:

David Gries, The Science of Programming

The book will change how you think about algorithms and how they are developed. One of the key ideas is algorithm development from loop-invariants along with pre- and post-conditions. There is a science (hence the name) of modifying post-conditions in order to develop a loop and its invariant.

One of the magical problems in the book is a linear time sort of an arbitrary array that contains only three distinct values (Dutch National Flag). It generalizes to a linear time sort of an array containing a finite number of distinct values. [1]

But as a TA, if you are familiar with the technique as described in the book, you can guide a beginner by working with the student to find the pre- and post-conditions, expressing them logically and then looking at formally weaker statements to guide the algorithm development. Note that the classic sorts, for example, all have identical pre- and post-conditions. The different algorithms arise from the various ways in which a logic statement can be weakened.

Note: if P -> Q the P is "stronger" and P is "weaker". So, a post-condition for a sort might include that the array A[0:n] is sorted. A weaker statement is that A[0:k], k <=n, is sorted. Combined with other statements, this can lead to a well defined loop and its exit condition.

So, it isn't a bunch of discrete tricks, but a methodical approach to developing the algorithms. The "tricks" are consequences of the technique, not the technique itself.

Both of the suggestions here are to give students a way to think about the problem, rather than to just reveal a "trick". You may be able to think of other ways to achieve the same end.

---

This book has been mentioned in several other answers on this site. A local search for "Gries" will turn up some additional ideas. I was lucky enough to have been taught this by David himself.

---

[1] For those requiring more explanation, the array can be of any length, but the values contained in it come from a set of three values, often {red, white, and blue}. This implies, of course that while there are only three distinct values in the array, they are repeated. The sort is to bring all of the red values together at the start of the array, and the blue values to the end. The algorithm runs in linear time as a function of the size of the array. The sort is not stable, in that entries of the same value may be exchanged. So, a white value to the "left" of another white value at the start might wind up to the "right" of it at the end. The sort is linear in "time" as mentioned above. It is also linear in comparisons between values and linear in exchanges. If you double the length of the array you (roughly) double the time, the number of comparisons, and the number of exchanges.

I suggest that you try to develop the algorithm using invariants and post-conditions as explained in the book, rather than just finding it online and reading it. (It is an exercise in the book, actually). You will learn something important. The algorithm is effectively a single scan of the array (hence linearity), but not the scan you normally see. That is the magic.

Answer 4

I have seen two approaches that work:

Unplugged:

Leave the computer, and design the algorithm. Use white boards, acting, puppets, physical objects, etc.

(This method is best used when you don't yet know what you are trying to achieve.)

Use Test Driven Development with Transformation Priority.

(This method is best used when you know what you are trying to achieve, but don't know how to get there.)

Test driven

The code is written using test driven design: One test at a time.

• No production code is written except to allow a failing test to pass. (failing to compile is a failing test.)
• No more code is written than necessary. That is stop working on the production code when it passes.
• Stop working on tests, when in fails (as soon as you have a failing test, stop working on it, and start on fixing the production code, so that the test passes).
• Iterate between writing test code, and writing production code. As soon as the code you are working is working, then switch. For production code working means, to make the test pass. For test code working means to highlight a deficiency in the production code, by failing.

TTD is like a battle, with an alternation of each side (test and production code) winning. The tests want the tests to fail, to highlight a deficiency in the production code. The production code wants the tests to pass. First the tests are wining, they show a deficiency, then the production code is fixed and it is winning. ( TDD implements alternating-repetition from Christopher Alexander's 15 properties )

Transformation Priority

Transformation Priority guides you as to which transformations to use, to make the test pass. Some transformations lead to better algorithms than other transformations.

({} → nil) no code at all → code that employs nil
(nil → constant)
(constant → constant+) a simple constant to a more complex constant
(constant → scalar) replacing a constant with a variable or an argument
(statement → statements) adding more unconditional statements.
(unconditional → if) splitting the execution path
(scalar → array)
(array → container)
(statement → tail-recursion)
(if → while)
(statement → non-tail-recursion)
(expression → function) replacing an expression with a function or algorithm
(variable → assignment) replacing the value of a variable.
(case) adding a case (or else) to an existing switch or if

note the items, and the order, are not set in stone. We may discover improvements.

see:

• The Transformation Priority Premise.
• https://vimeo.com/97516288