# Difficulty of algorithms homework problems

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?

• This is a perfect question. Welcome to Computer Science Educators! – Ben I. Jun 1 '18 at 22:46
• It would also be good if you would register for the site so you can become more a part of the conversation here. – Buffy Jun 1 '18 at 23:25

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.

• 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.

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.

• Isn't that an argument for starter code? There are so few opportunities within a broader curriculum to give students practice honing that skill, and algorithms is one of the few places where it fits rather naturally, no contortions required. After all, it really does take practice to get decent at it. It is rather like stepping into someone else's brain. – Ben I. Jul 3 '18 at 12:05
• I'm not sure I agree with everything you say, but it is well thought out and something to consider. Of course, if you let them make mistakes you need other pedagogical tricks to catch them and focus on the mistakes. Likewise, starter code needs to be well thought out for its overall effect and for where in the curriculum you use it. +1 – Buffy Jul 3 '18 at 13:05
• I had an experience where the TA did not explain my mistake to me, so it took a while to figure out, but I never forgot that lesson! I try to find a balance between letting students discover their problems and having them waste time needlessly. I agree on the starter code. I think that it becomes something the students don't look at because they have their face pressed against the windshield trying to go faster, and the more they overlook, the less they learn. Writing the same boilerplate code several times is the only way to learn that stuff. – Scott Rowe Jul 3 '18 at 14:52
• @BenI. I agree 100% about that being a benefit with starter code. But understanding someone else's code and learning an algorithm does seem a bit daunting for some students. Would it be more reasonable to say that it depends on the student or experience level? If the student is struggling just to understand the starter code, then you can take a step back and try looking at the algorithm from scratch? Also - I hope I'm not breaking any rules by asking that question. If I was on StackOverflow, it would be bordering on "a discussion in the comments" which is discouraged. – JustBlossom Jul 5 '18 at 18:22
• The purpose of comments is to improve the quality of the questions and answers, so I'm happy to report that this would be acceptable on SO as well :) As far as the level of the students, figuring out when it is appropriate to make accommodations, and what accommodations to make, is one of the very toughest problems teachers face. :) – Ben I. Jul 5 '18 at 23:16

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.

• Comments are not for extended discussion; this conversation has been moved to chat. – thesecretmaster Jun 21 '18 at 22:58

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:

• Can you explain the "stop working on tests when it fails part"? I thought if it fails, you fix it until it passes (and then you stop). – JustBlossom Aug 5 '18 at 0:52
• @JustBlossom I have amended answer: hope is is clearer. When a test fails (not compilation error). When a test fails, it succeeds to find a problem in the production code. It is not the test that is failing, but the production code, so fix the production code. When the test passes, write a new test. – ctrl-alt-delor Aug 5 '18 at 16:51
• Yup, that's clearer. It's kind of like you're stress testing your code and making sure that you're not only testing for what you know will work. Thanks! – JustBlossom Aug 13 '18 at 3:42
• Yes, If you write tests that always pass, you are wasting your time (expect that writing the tests makes you think). You could have the same outcome by not writing and running the tests. And if a test never fails, you do not know if it can fail. Therefore write the tests first: so that you think, so that you can test the tests (they fail). – ctrl-alt-delor Aug 13 '18 at 9:43