Description
I've been thinking of exercises that fall at two ends of the spectrum; when I saw the linked-list exercise, it got me thinking: the majority of the exercises fall into the "clever puzzle" category or the "project euler" category, both of which are great.
But I'd love to see more fundamental CS type exercises, as they're both critical to understanding data structures, algorithms, Big O complexity, etc. - for instance, "implement insertion sort" or quicksort, maybe Dijkstra's shortest-path algorithm.
Then I started thinking about knapsacks. Do we want NP-complete problems in the exercise set? Obviously a chess solver would be out of bounds as chess is in EXP, but what about problems in NP?
What about writing tests that are smart enough to determine the space/time complexity of the solution? (Easier in languages with reflection, I know, but just spitballing here.)
What's the lower-bound (I think linked-list sets it pretty low) and what's the upper bound (NP-hard, NP-complete, beyond?), or is it just "try it, people can skip it?"