algorithms and data structures exercises

[masters3d]

Hi team,

I'd like to push for the inclusion of more algorithms and data structures exercises. The idea would be that these could be used by somebody to refresh their knowledge, learn for the first time and also to contribute / collab with other people.

We already have some:
https://github.com/exercism/problem-specifications/tree/master/exercises/binary-search
https://github.com/exercism/problem-specifications/tree/master/exercises/binary-search-tree
https://github.com/exercism/problem-specifications/tree/master/exercises/linked-list
https://github.com/exercism/problem-specifications/tree/master/exercises/simple-linked-list

I'd like to add a few more:

• Stable sorts like Insertion sort and Merge sort.
• Simple Min Heap added simple-min-heap problem #1128
• Max Heap / Priority Queue
• Double-Ended Priority Queues
• https://en.wikipedia.org/wiki/Graham_scan

In the future I'd like to add more complex ones

Feedback, additions?

[cmccandless]

We always welcome exercise suggestions here. Most of those ideas sound like they could be easily made into exercises. The only suggestion which I'm not sure about is the sorting algorithms; I'm not sure how easy it would be to ensure that the algorithm being tested is the one being used (i.e. how do the test know I'm not just using quick sort?).

[masters3d]

@cmccandless This is why I was thinking only including stable sorting algos. There is nothing stopping people from "cheating", the best we can do is to require some internal functions to be exposed so we can test them. The tests are not 100% important thought, the important part is to get people talking their code.

[budmc29]

Sounds like a great idea.

In the case we can't rely on the tests to check the algorithm, that can be a good starting discussion point for mentors.

[coriolinus]

Stable sort is useful when sorting objects which have some identifiable attribute other than the sorting key, but simple strings and numbers don't have that property. I think our best option is to construct a list of objects, instruct the students to sort them only by a particular key property, and leave it to the language track maintainers to decide what that actually means.

Instead of writing a number of different sorting exercises, each with independent canonical data, what do you all think of a big Custom Sort exercise for which the canonical data includes a variety of data types and cases, and all the lists are called for each of the relevant sort methods? Disadvantage is that it'll be a bigger exercise than most, but the advantage would be that the test runner could call for each type of sort by name: list.insertion_sort(), list.merge_sort(), etc. This doesn't prevent students from cheating, but I think we can assume that most students are operating in good faith; if asked for an insertion sort, they'll attempt to implement one.

I'm not a fan of requiring internal functions to be exposed, because part of what students learn from these exercises is what good and idiomatic module/package/namespace design looks like. For those languages which support it, we want to teach students to minimize the surface area, and keep the implementation details private.

[Insti]

This topic has previously been discussed here: "Are Computer Science exercises a good fit the exercism platform.": exercism/discussions#124

[coriolinus]

Interesting, particularly in that the conclusion there appears to be the opposite of what we were heading toward here.

The conclusion at that time was

Instead of asking "Write a program that implements erastosthenes sieve." we should ask "Write a program which returns a list of prime numbers, there are a couple of efficient algorithms: erastostenes sive, wheel sieve, etc", perhaps even with links.

As a general policy, that's fine. However, I think that this thread indicates some interest in more traditional computer-science exercises which desire a specific well-known algorithm. I believe that nexercism models its exercises not as a list but as a tree, and branches may be optional. Could the exercises proposed here, plus the ones linked by OP, form a "Algorithms" optional branch?

If so, what would that take? I'm not following nexercism development closely, so I honestly don't know how close it is to release or whether the branching-tracks feature is yet available.

[masters3d]

Closing in favor of this: #761