Scaffolded Prim: remove need to process nodes in alphabetic order

[ttaiv]

Problem

The current version of Prim exercise (PrimAVPE-scaffolded-v2) does not usually require to process the neighbors of a node in alphabetic order. However, when two edges connecting the previously dequeued node to unvisited nodes happen to have the same weight, it is required to process them in alphabetic order to satisfy the grader. Example: Here it is required to first enqueue K to satisfy the grader.

Solution (edited)

Just add adjacency list representation of the graph --> emphasizes that the algorithm is deterministic and makes it clear what determines the processing order of the nodes. NOTE: the grading should now also be modified to require processing nodes in the order specified by adjacency list.

[ttaiv]

Unfortunately, it seems that the proposed solution is not sufficient to remove the need for alphabetic order. For example in this situation:

Enqueuing M, then N and pressing dequeue results to:

That is, N is the highest priority element.

On the other hand, enqueuing first N, then M and pressing dequeue result to:

That is, F being the highest priority element.

Possible solutions

• Make all the edge weights unique so that the order of elements in the PQ is always independent of enqueuing order.
• Revert back to version of PQ (MinHeapInterface) where position in alphabets influenced priority of element (again PQ order is independent of enqueuing order).
• Modify grading to create multiple model answers where nodes are processed in different order and compare the user's solution against them all.
• Just keep the alphabetic order requirement (and maybe consider adding neighbour list to determine the processing order of nodes).

[atilante]

An excellent finding! My comments on possible solutions:

Solution 1. Unique edge weights Pros:

• Easy to implement: when there are |E| edges, generate an array of unique values 1...|E| and then shuffle it.
• The solution is unique.
• |E| ~ 20, so this would be doable.
• No user interface modifications needed.

Cons:

• The student never faces a problem of equal choice.

Solution 2. Revert back to alphabetic order in priority queue Pros:

• Keeps everything as it is
• However, the implementation of the priority queue is not a central learning objective of this exercise. Cons:
• What happens inside the priority queue might puzzle a rare (unknown) minority of students.

Solution 3. Modify grading to create multiple model answers. Pros:

• Theoretically possible

Cons:

• Brute force solution with combinatorics: based on empirical examinations of four model answers, there are at most 48 different solutions. (Yes, we would have to run Prim's algorithm 48 times, and create JSAV slideshows for each of those.) Comment:

• More elegant solution by time complexity might be achieved by extending the idea in Dijkstra-PQ exercise (v3)

Solution 4. Keep the alphabetic order requirement Pros:

• If neighbour list added, the solution is unique
• No need for complex grading algorithms

Cons:

• Requires some user interface design & programming
• The user interface becomes more complex

Comment:

• Consistency with other graph algorithm exercises?

Considering the options, I would choose Solution 2, unless Archie would like to have Solution 4 to emphasize the neighbour list.

[atilante]

Archie's comments:

Solution 1 is nasty, not recommended. Proposal 1: ensure that there are two edges with the same weight, but not three. Proposal 2: ban solutions which are not deterministic. Combine Proposal 1 and Proposal 2.

Solution 3: more programming work. Then one should choose the correct model answer version to be displayed.

Archie would prefer #213 because it make the exercise more deterministic. Then also switch back from the alphabet-agnostic grader to the default JSAV grader. Then, if the student enqueues neighbors to the priority queue in other order than what is in the neighbour list, the step is graded as incorrect. The idea is to show the student that the solution is different depending on the enqueuing order.