Incorporating algorithmic complexity in grading

Question

What are some advantages of incorporating algorithmic complexity in grading tests and assignments given to students?

Currently, students in 11th grade at my school are required in tests to write functions that should preform some operation (usually operations on data structures like LinkedList, Stack and Queue).

This works fairly well in terms of checking whether a student knows how to use those data structures.

However, it's not uncommon to see an answer that does, eventually, preform the required operation; and yet its complexity is $O(n^3)$ (no kidding. The specific case I'm thinking of is one where the student worked with the unsorted linked list of stacks¹ in 3 nested for loops).

The students are required, after they write their functions, to also write the complexity of their solutions.

In a quest to improve the students' thinking skills, I thought that maybe we should give bonus points if the solutions are inventive and less complex than a head on approach. This means that if a student's function is $O(n)$ for a task that a direct assault would be of $O(n^2)$, they should get more points.

This can also apply to various assignments we can give them, in addition to the tests we already have (or maybe make the tests slightly easier and then add assignments).

The students are in a CS major, and they have experience with java, OOP, Data structures and basic calculations of complexity for various, simple, algorithms)

---

¹We gave them some arbitrary way of comparing stacks (of Integers): The sum of elements.

Answer 1

I wouldn't want to penalize kids who are really relatively inexperienced for not coming up with the fastest solutions on a test. Even if they're in 11th grade and have a couple of years under their belts, they likely haven't been in real situations where run time is important.

If I were to want a specific run time on a test I'd say something like "for full credit make sure your solution runs in $O(blah)$ time."

If I give an open ended solutions and I don't specify any restrictions on run time, storage limitations, or data set size I tell the kids that I won't penalize them for efficiency unless it's so grossly horrible. For example, if they were to write a sort in their code (and I wouldn't really ask this but it makes for an easy example), I wouldn't penalize a kid for coding an $N^2$ sort even if we covered $n log(n)$ unless I talk about a large data set size. On the other hand if they sorted by say an $N^3$ solution or worse, they would lose some points.

In any event, if you're requiring certain run times you have to be careful that you're not just getting kids to memorize and spit back what the teacher expects.

Also remember that there are plenty of times where a simpler, slower algorithm is both clearer and more than sufficient and that complex fast code that doesn't work isn't nearly as good as simple code that does.

To encourage creativity, give multi level assignments. Create lessons where you can have them develop a solution, see that it's too slow, and then refine it. I do that with finding the mode of a data set (https://cestlaz.github.io/posts/2014-11-17-hidden-complexity.html).

You can also create assignments that encourage this and make test data sets and situations that force kids to work on time efficiency issues.

Answer 2

I recognize that this isn't exactly an answer to your question, but is a different way to think of the issue. I applaud the answer of Mike Zamansky given here already, but suggest an orthogonal approach.

One way to get students to focus on efficiency is to ask them to name (or select from a list, perhaps) the efficiency of the solution they present and also possibly to reply whether it is the most efficient algorithm that they have studied. You can go further in an assignment and ask them to say why they think their solution is a good one even if not the most efficient.

And if you teach sorting for this sort of thing, you, and likely your students, should be aware of this paper (pdf) by Owen Astrachan which says, among other things that Bubble Sort is never the best solution - either for simplicity or efficiency.

If you ask for a discussion, in other words, you have more information on which to grade them than just looking at the algorithm itself. It also forces them to think deeper; generally a good thing.

Answer 3

The first step is to mention what the computational complexity of the best solution is so that students will know to look for an algorithm with that efficiency.

You may want to consider a minimum efficiency requirement as an explicit requirement for the assignment (e.g. "must be more efficient than brute force", "must be $O(n^2)$ or less", etc.), especially since brute force solutions may reduce the educational value of the assignment in the first place because brute force solutions are often much easier to come up with than efficient solutions. Consider by way of example the Project Euler problems, many of which are relatively easy to brute-force. The entire point of these questions is to come up with something better than brute force - there's little to no learning value in brute force.

Of course, some questions are simply not feasible to solve with brute force in the first place. For example, the description of problem 67 says that "It is not possible to try every route to solve this problem, as there are $2^{99}$ altogether! If you could check one trillion (1012) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it." It turns out that you'll often encounter problems like this in actual programming: consider what would happen if Google's search engine relied on brute force, for example.

So really, specific performance, efficiency, or scalability requirements are often intrinsic to the problem itself, both in educational settings and in actual engineering - if you didn't solve the problem in a way that meets those requirements, it's quite possible that you didn't really solve the problem at all.

Beyond that, you may want to offer extra points to students who have better solutions (e.g. "solutions must be $O(n^2)$ or better to be considered complete, but you get extra points if you can make your solution $O(n log n)$).

TL;DR All assignments have requirements, so why not just make minimum efficiency requirements one of the requirements and then give extra points to people who exceed the minimum?