2025-11-22T23:52:17.167783

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

Oakeson, Smith, Winder et al.

This paper extends the functionality of block ordering problems (such as Parsons problems and Proof Blocks) to include optional blocks. We detail the algorithms used to implement the optional block feature and present usage experiences from instructors who have integrated it into their curriculum. The optional blocks feature enables instructors to create more complex Parsons problems with multiple correct solutions utilizing omitted or optional blocks. This affords students a method to engage with questions that have several valid solutions composed of different answer components. Instructors can specify blocks with multiple mutually exclusive dependencies, which we represent using a multigraph structure. This multigraph is then collapsed into multiple directed acyclic graphs (DAGs), allowing us to reuse existing algorithms for grading block ordering problems represented as a DAG. We present potential use cases for this feature across various domains, including helping students learn Git workflows, shell command sequences, mathematical proofs, and Python programming concepts.

academic

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

基本信息

论文ID: 2510.11999
标题: Choose Your Own Solution: Supporting Optional Blocks in Block Ordering Problems
作者: Skyler Oakeson (Utah State University), David H. Smith IV (Virginia Tech), Jaxton Winder (Utah State University), Seth Poulsen (Utah State University)
分类: cs.HC (Human-Computer Interaction)
发表时间/会议: 2018年6月 (Conference acronym 'XX)
论文链接: https://arxiv.org/abs/2510.11999

摘要

本文扩展了块排序问题（如Parsons问题和Proof Blocks）的功能，引入了可选块特性。作者详细介绍了实现可选块功能的算法，并展示了将其集成到课程中的教师使用经验。可选块功能使教师能够创建更复杂的Parsons问题，支持利用省略或可选块的多个正确解决方案。这为学生提供了一种处理由不同答案组件组成的多种有效解决方案的方法。教师可以指定具有多个互斥依赖关系的块，使用多图结构表示。然后将此多图折叠为多个有向无环图(DAGs)，允许重用现有的基于DAG的块排序问题评分算法。

研究背景与动机

问题定义

传统的块排序问题（如Parsons问题和Proof Blocks）存在一个关键限制：无法包含可选块或在一个解决方案中有效但在另一个解决方案中无效的块。现有系统要求每个正确解决方案必须包含固定的块集合，这限制了教师创建反映现实世界问题解决过程的复杂问题的能力。

重要性

真实世界反映：现实中的编程、数学证明和shell命令等问题通常有多种等效的解决方案
教育价值：让学生理解问题可以有多个同样有效的答案，这是重要的学习目标
灵活性需求：教师需要能够创建更复杂、更贴近实际应用的教学问题

现有方法局限性

Poulsen等人的工作虽然支持同一块集合的多种排序，但不支持不同块组合的多种解决方案
基于执行的反馈虽然可以处理多解方案，但缺乏基于行的反馈的详细性和适用性
无法在数学证明等非可执行场景中使用多解方案

核心贡献

多图折叠算法：提出了将多图表示的依赖关系折叠为多个有向无环图的算法
可选块接口：为教师提供了编写可选块排序问题的界面和规范
跨域应用案例：展示了在编程入门、离散数学和shell命令教学中的应用
算法复杂度分析：提供了算法的时间复杂度理论分析和实际应用数据

方法详解

任务定义

输入：包含可选依赖关系的块排序问题的多图表示输出：所有可能的有效DAG表示，用于评分学生提交的解决方案约束：保持问题的无环性，支持互斥的依赖路径

核心算法架构

1. 多图表示

使用带颜色边的多图来表示可选依赖关系：

节点代表代码块或证明步骤
带颜色的边表示替代的逻辑依赖路径
管道操作符(|)在HTML规范中表示互斥依赖

2. 多图折叠算法(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