Choose Your Own Solution: Supporting Optional Blocks in Block Ordering Problems

Basic Information

• Paper ID: 2510.11999
• Title: Choose Your Own Solution: Supporting Optional Blocks in Block Ordering Problems
• Authors: Skyler Oakeson (Utah State University), David H. Smith IV (Virginia Tech), Jaxton Winder (Utah State University), Seth Poulsen (Utah State University)
• Classification: cs.HC (Human-Computer Interaction)
• Publication Date/Conference: June 2018 (Conference acronym 'XX)
• Paper Link: https://arxiv.org/abs/2510.11999

Abstract

This paper extends the functionality of block ordering problems (such as Parsons problems and Proof Blocks) by introducing optional block features. The authors detail the algorithms for implementing optional block functionality and present teacher experiences integrating it into curricula. Optional blocks enable instructors to create more complex Parsons problems that support multiple correct solutions utilizing omitted or optional blocks. This provides students with a method for handling multiple valid solutions composed of different answer components. Instructors can specify blocks with multiple mutually exclusive dependencies, represented using multigraph structures. This multigraph is then collapsed into multiple directed acyclic graphs (DAGs), allowing the reuse of existing DAG-based block ordering problem scoring algorithms.

Research Background and Motivation

Problem Definition

Traditional block ordering problems (such as Parsons problems and Proof Blocks) have a critical limitation: they cannot include optional blocks or blocks that are valid in one solution but not in another. Existing systems require each correct solution to contain a fixed set of blocks, which limits instructors' ability to create complex problems that reflect real-world problem-solving processes.

Significance

1. Real-World Reflection: Real-world problems in programming, mathematical proofs, and shell commands typically have multiple equivalent solutions
2. Educational Value: Helping students understand that problems can have multiple equally valid answers is an important learning objective
3. Flexibility Requirements: Instructors need the ability to create more complex, practically-oriented instructional problems

Limitations of Existing Approaches

• While Poulsen et al.'s work supports multiple orderings of the same block set, it does not support multiple solutions with different block combinations
• Execution-based feedback, while capable of handling multi-solution problems, lacks the granularity and applicability of line-based feedback
• Cannot be used in non-executable scenarios such as mathematical proofs

Core Contributions

1. Multigraph Collapsing Algorithm: Proposes an algorithm for collapsing dependency relationships represented as multigraphs into multiple directed acyclic graphs
2. Optional Block Interface: Provides instructors with an interface and specification for writing optional block ordering problems
3. Cross-Domain Application Cases: Demonstrates applications in introductory programming, discrete mathematics, and shell command instruction
4. Algorithm Complexity Analysis: Provides theoretical complexity analysis and practical application data for the algorithm

Methodology Details

Task Definition

Input: Multigraph representation of block ordering problems with optional dependencies Output: All possible valid DAG representations for scoring student submissions Constraints: Maintain acyclicity of the problem, support mutually exclusive dependency paths

Core Algorithm Architecture

1. Multigraph Representation

Uses colored edges in a multigraph to represent optional dependencies:

• Nodes represent code blocks or proof steps
• Colored edges represent alternative logical dependency paths
• Pipe operators (|) in HTML specifications represent mutually exclusive dependencies

2. Multigraph Collapsing Algorithm (Algorithm 1)

Function Collapse(M, F):
    CollapsedGraphs (CD) ← empty list
    PartiallyCollapsedGraphs (PCGs) ← empty queue
    Enqueue(PCGs, M)
    
    while PCG is not empty:
        G ← Dequeue(PCGs)
        (v, DAG) ← DFSuntil(G, F)
        
        if v is NULL:
            append DAG to CD
        else:
            foreach Color in G:
                PCG ← copy(G)
                Remove all edges on v with color ≠ Color
                Enqueue(PCGs, PCG)
    
    return CD

3. DFS-Until Algorithm (Algorithm 2)

Modified depth-first search with stopping conditions:

• Traverses backward from the final node
• Stops and returns the node requiring processing when encountering multi-colored edges
• Returns a valid DAG upon completing traversal

Technical Innovations

1. Multigraph to DAG Conversion: Innovatively uses colored edges to represent mutually exclusive dependencies, then systematically generates all possible DAG combinations
2. Algorithm Complexity Optimization:
   • Time Complexity: O(d·(n+m)), where d is the number of generated DAGs
   • In practical applications, d values are small (≤8), ensuring practicality
3. Backward Compatibility: Reuses existing DAG scoring algorithms without requiring redesign of the scoring mechanism

Experimental Setup

Application Domain Testing

The paper conducted testing in three primary domains:

1. Discrete Mathematics: Multiple construction methods for mathematical proofs
2. Introductory Programming: Different implementation approaches for Python functions
3. Shell Commands: Git workflows and Unix command sequences

Complexity Analysis Data

The authors collected complexity data from 12 real-world problems:

Teacher Usage Experience

• Second author used it in large-scale introductory programming courses, including assignments and exams
• Third author assessed shell and Git knowledge in software engineering fundamentals courses
• Supports parallel presentation of iterative vs. functional programming paradigms

Experimental Results

Main Findings

1. Practicality Verification: All real-world created problems maintained reasonable complexity ranges (d≤8)
2. Teaching Effectiveness:
   • Students were able to explore multiple solution paths
   • Provided richer learning experiences compared to single solutions
   • Demonstrated good discriminative ability in Git workflow instruction
3. System Performance:
   • Algorithm performed well in practical applications
   • Successfully integrated into the PrairieLearn platform
   • Maintained advantages of existing DAG scoring algorithms

Application Case Analysis

Programming Example

A summation function problem demonstrated four valid solutions:

• Detailed approach: declare variables, accumulate step-by-step
• Concise approach: direct assignment expression
• Hybrid approach: variants combining both methods

Mathematical Proof Example

Even number property proof supported two methods:

• Direct proof: assume n is even, prove n+10 is even
• Proof by contradiction: assume n+10 is odd, derive contradiction

Related Work

Parsons Problem Research

• Dale Parsons and Patricia Haden first introduced the programming puzzle concept
• Ericson et al. demonstrated that Parsons problems are as effective as traditional programming exercises but more efficient
• Adaptive Parsons problems allow students to adjust difficulty based on skill level

Proof Blocks Extensions

• Poulsen et al. extended block ordering to mathematical proof domains
• Introduced DAG representation to handle multiple correct orderings
• Developed partial credit mechanisms based on edit distance

Distractor Research

• Traditional distractors are incorrect code blocks
• This paper redefines them: after selecting an optional block path, blocks from other paths become distractors
• Provides new perspectives for distractor research

Conclusions and Discussion

Main Conclusions

1. Technical Feasibility: The multigraph collapsing algorithm successfully addresses representation and scoring of optional blocks
2. Educational Value: Block ordering problems supporting multiple solutions better reflect real-world problem-solving processes
3. Broad Applicability: The approach has application value across multiple domains including programming, mathematics, and systems management

Limitations

1. Complexity Growth: The number of DAGs grows exponentially with color choices, potentially limiting use of certain problems
2. Interface Design: Large numbers of blocks may increase cognitive load, requiring better user interface design
3. Limited Evaluation: Lacks large-scale empirical studies of learning effectiveness

Future Directions

1. Learning Effectiveness Research: Evaluate specific impacts of multi-solution problems on student learning
2. Interface Optimization: Develop user interfaces that reduce cognitive load
3. Fairness Research: Assess whether multi-solution problems in exam environments can reduce unfair advantages from preconception matching

In-Depth Evaluation

Strengths

1. Technical Innovation: The multigraph-to-DAG collapsing algorithm is elegantly designed with solid theoretical foundations
2. Practical Value: Addresses real needs in educational technology, already applied in multiple courses
3. Systematic Completeness: Forms a complete loop from algorithm design through system implementation to educational application
4. Cross-Domain Applicability: Demonstrates application value across programming, mathematics, systems management, and other domains

Weaknesses

1. Evaluation Depth: Primarily relies on anecdotal evidence, lacking rigorous comparative experiments on learning effectiveness
2. Theoretical Analysis: While providing complexity analysis, discussion of learning theory is relatively limited
3. User Experience: Insufficient discussion on designing better user interfaces for handling complex problems

Impact

1. Technical Contribution: Provides a general method for educational technology to handle multi-solution problems
2. Educational Practice: Changes the design paradigm of traditional block ordering problems
3. Research Inspiration: Provides new perspectives for worked example theory and distractor research

Applicable Scenarios

1. Programming Education: Suitable for scenarios demonstrating multiple programming paradigms and solutions
2. Mathematics Teaching: Particularly suitable for teaching theorems with multiple proof methods
3. Skills Training: Suitable for training in systems administration, tool usage, and other skills with multiple operational paths

References

This paper cites important literature in educational technology, including:

• Original Parsons problem research 14
• Foundational Proof Blocks work 16,17
• Related research on adaptive learning and worked example theory 1,6,8
• Empirical research on distractor effects 9,10,19

Overall Assessment: This is an important contribution to the field of educational technology. The proposed multigraph collapsing algorithm elegantly solves the problem of supporting optional blocks in block ordering problems. While there is room for improvement in empirical evaluation of learning effectiveness, its technical innovation and practical value make it a significant advance in the field.