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

আপনার নিজের সমাধান বেছে নিন: ব্লক অর্ডারিং সমস্যায় ঐচ্ছিক ব্লক সমর্থন

মৌলিক তথ্য

পেপার আইডি: 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 (মানব-কম্পিউটার ইন্টারঅ্যাকশন)
প্রকাশনা সময়/সম্মেলন: ২০১৮ সালের জুন (সম্মেলন সংক্ষিপ্ত নাম 'XX)
পেপার লিঙ্ক: https://arxiv.org/abs/2510.11999

সারসংক্ষেপ

এই পেপারটি ব্লক অর্ডারিং সমস্যা (যেমন Parsons সমস্যা এবং Proof Blocks) এর কার্যকারিতা প্রসারিত করে, ঐচ্ছিক ব্লক বৈশিষ্ট্য প্রবর্তন করে। লেখকরা ঐচ্ছিক ব্লক কার্যকারিতা বাস্তবায়নের জন্য অ্যালগরিদম বিস্তারিতভাবে উপস্থাপন করেন এবং এটি পাঠ্যক্রমে একীভূত করার শিক্ষক অভিজ্ঞতা প্রদর্শন করেন। ঐচ্ছিক ব্লক বৈশিষ্ট্য শিক্ষকদের আরও জটিল Parsons সমস্যা তৈরি করতে সক্ষম করে, যা বাদ দেওয়া বা ঐচ্ছিক ব্লক ব্যবহার করে একাধিক সঠিক সমাধান সমর্থন করে। এটি শিক্ষার্থীদের বিভিন্ন উত্তর উপাদান নিয়ে গঠিত একাধিক বৈধ সমাধান পরিচালনা করার একটি উপায় প্রদান করে। শিক্ষকরা একাধিক পারস্পরিক একচেটিয়া নির্ভরতা সহ ব্লক নির্দিষ্ট করতে পারেন, মাল্টিগ্রাফ কাঠামো ব্যবহার করে প্রতিনিধিত্ব করা হয়। এই মাল্টিগ্রাফটি তারপর একাধিক নির্দেশিত অ্যাসাইক্লিক গ্রাফ (DAGs) এ ভাঁজ করা হয়, যা বিদ্যমান DAG-ভিত্তিক ব্লক অর্ডারিং সমস্যা স্কোরিং অ্যালগরিদম পুনরায় ব্যবহার করতে দেয়।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

ঐতিহ্যবাহী ব্লক অর্ডারিং সমস্যা (যেমন Parsons সমস্যা এবং Proof Blocks) একটি মূল সীমাবদ্ধতা রয়েছে: ঐচ্ছিক ব্লক অন্তর্ভুক্ত করতে বা এক সমাধানে বৈধ কিন্তু অন্য সমাধানে অবৈধ ব্লক অন্তর্ভুক্ত করতে পারে না। বিদ্যমান সিস্টেমগুলির জন্য প্রতিটি সঠিক সমাধানে অবশ্যই ব্লকের একটি নির্দিষ্ট সেট থাকতে হবে, যা শিক্ষকদের বাস্তব-বিশ্বের সমস্যা সমাধান প্রক্রিয়া প্রতিফলিত করে এমন জটিল সমস্যা তৈরি করার ক্ষমতা সীমাবদ্ধ করে।

গুরুত্ব

১. বাস্তব-বিশ্ব প্রতিফলন: বাস্তবে প্রোগ্রামিং, গাণিতিক প্রমাণ এবং শেল কমান্ড ইত্যাদি সমস্যাগুলির সাধারণত একাধিক সমতুল্য সমাধান থাকে २. শিক্ষামূলক মূল্য: শিক্ষার্থীদের বুঝতে দেওয়া যে সমস্যাগুলির একাধিক সমানভাবে বৈধ উত্তর থাকতে পারে, এটি একটি গুরুত্বপূর্ণ শেখার লক্ষ্য ३. নমনীয়তার প্রয়োজন: শিক্ষকদের আরও জটিল, বাস্তব প্রয়োগের কাছাকাছি শিক্ষামূলক সমস্যা তৈরি করতে সক্ষম হতে হবে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

Poulsen এবং অন্যদের কাজ একই ব্লক সেটের একাধিক অর্ডারিং সমর্থন করে, কিন্তু বিভিন্ন ব্লক সমন্বয়ের একাধিক সমাধান সমর্থন করে না
সম্পাদন-ভিত্তিক প্রতিক্রিয়া বহু-সমাধান কেসগুলি পরিচালনা করতে পারে, কিন্তু লাইন-ভিত্তিক প্রতিক্রিয়ার বিস্তারিততা এবং প্রযোজ্যতার অভাব রয়েছে
গাণিতিক প্রমাণের মতো অ-সম্পাদনযোগ্য পরিস্থিতিতে বহু-সমাধান পদ্ধতি ব্যবহার করা যায় না

মূল অবদান

१. মাল্টিগ্রাফ ভাঁজ অ্যালগরিদম: মাল্টিগ্রাফ প্রতিনিধিত্ব করা নির্ভরতা সম্পর্ক একাধিক নির্দেশিত অ্যাসাইক্লিক গ্রাফে ভাঁজ করার অ্যালগরিদম প্রস্তাব করে २. ঐচ্ছিক ব্লক ইন্টারফেস: শিক্ষকদের ঐচ্ছিক ব্লক অর্ডারিং সমস্যা লেখার জন্য ইন্টারফেস এবং বিশেষ নির্দেশনা প্রদান করে ३. ক্রস-ডোমেইন প্রয়োগ কেস: প্রোগ্রামিং প্রবর্তনী, বিচ্ছিন্ন গণিত এবং শেল কমান্ড শিক্ষায় প্রয়োগ প্রদর্শন করে ४. অ্যালগরিদম জটিলতা বিশ্লেষণ: অ্যালগরিদমের সময় জটিলতা তাত্ত্বিক বিশ্লেষণ এবং ব্যবহারিক প্রয়োগ ডেটা প্রদান করে

পদ্ধতি বিস্তারিত

কাজের সংজ্ঞা

ইনপুট: ঐচ্ছিক নির্ভরতা সম্পর্ক সহ ব্লক অর্ডারিং সমস্যার মাল্টিগ্রাফ প্রতিনিধিত্ব আউটপুট: সমস্ত সম্ভাব্য বৈধ DAG প্রতিনিধিত্ব, শিক্ষার্থী জমা দেওয়া সমাধান স্কোর করার জন্য ব্যবহৃত সীমাবদ্ধতা: সমস্যার অ্যাসাইক্লিক প্রকৃতি বজায় রাখা, পারস্পরিক একচেটিয়া নির্ভরতা পথ সমর্থন করা

মূল অ্যালগরিদম আর্কিটেকচার

१. মাল্টিগ্রাফ প্রতিনিধিত্ব

রঙিন প্রান্ত সহ মাল্টিগ্রাফ ব্যবহার করে ঐচ্ছিক নির্ভরতা সম্পর্ক প্রতিনিধিত্ব করে:

নোড কোড ব্লক বা প্রমাণ পদক্ষেপ প্রতিনিধিত্ব করে
রঙিন প্রান্ত বিকল্প যুক্তিগত নির্ভরতা পথ প্রতিনিধিত্ব করে
পাইপ অপারেটর (|) HTML বিশেষ নির্দেশনায় পারস্পরিক একচেটিয়া নির্ভরতা নির্দেশ করে

२. মাল্টিগ্রাফ ভাঁজ অ্যালগরিদম (অ্যালগরিদম १)

Function Collapse(M, F):
    CollapsedGraphs (CD) ← খালি তালিকা
    PartiallyCollapsedGraphs (PCGs) ← খালি সারি
    Enqueue(PCGs, M)
    
    যখন PCG খালি নয়:
        G ← Dequeue(PCGs)
        (v, DAG) ← DFSuntil(G, F)
        
        যদি v NULL হয়:
            CD তে DAG যোগ করুন
        অন্যথায়:
            G তে প্রতিটি রঙের জন্য:
                PCG ← copy(G)
                v এর সাথে রঙ ≠ রঙ এর সমস্ত প্রান্ত সরান
                Enqueue(PCGs, PCG)
    
    CD ফেরত দিন

३. DFS-Until অ্যালগরিদম (অ্যালগরিদম २)

থামার শর্ত সহ পরিবর্তিত গভীরতা-প্রথম অনুসন্ধান:

চূড়ান্ত নোড থেকে পিছিয়ে ট্রাভার্সাল শুরু করুন
বহু-রঙের প্রান্ত সম্মুখীন হলে থামুন এবং প্রক্রিয়া করার প্রয়োজনীয় নোড ফেরত দিন
ট্রাভার্সাল সম্পূর্ণ হলে বৈধ DAG ফেরত দিন

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. মাল্টিগ্রাফ থেকে DAG রূপান্তর: সৃজনশীলভাবে রঙিন প্রান্ত ব্যবহার করে পারস্পরিক একচেটিয়া নির্ভরতা প্রতিনিধিত্ব করে, তারপর সিস্টেমেটিকভাবে সমস্ত সম্ভাব্য DAG সমন্বয় তৈরি করে

२. অ্যালগরিদম জটিলতা অপ্টিমাইজেশন:

সময় জটিলতা: O(d·(n+m)), যেখানে d হল উৎপন্ন DAG সংখ্যা
ব্যবহারিক প্রয়োগে d মান ছোট (≤८), ব্যবহারযোগ্যতা নিশ্চিত করে

३. পিছিয়ে সামঞ্জস্যতা: বিদ্যমান DAG স্কোরিং অ্যালগরিদম পুনরায় ব্যবহার করে, স্কোরিং মেকানিজম পুনরায় ডিজাইন করার প্রয়োজন নেই

পরীক্ষামূলক সেটআপ

প্রয়োগ ডোমেইন পরীক্ষা

পেপারটি তিনটি প্রধান ক্ষেত্রে পরীক্ষা করা হয়েছে:

१. বিচ্ছিন্ন গণিত: গাণিতিক প্রমাণের একাধিক নির্মাণ পদ্ধতি २. প্রোগ্রামিং প্রবর্তনী: Python ফাংশনের বিভিন্ন বাস্তবায়ন পদ্ধতি
३. শেল কমান্ড: Git কর্মপ্রবাহ এবং Unix কমান্ড সিকোয়েন্স

জটিলতা বিশ্লেষণ ডেটা

লেখক १२টি বাস্তব সমস্যার জটিলতা ডেটা সংগ্রহ করেছেন:

বিষয়বস্তু ধরন	ব্লক সংখ্যা (n)	প্রান্ত সংখ্যা (m)	DAG সংখ্যা (d)
Bash কমান্ড	५-१३	४-१०	२-४
Python প্রোগ্রামিং	६-१३	८-१३	२-८
গাণিতিক প্রমাণ	१०-११	१०-१३	२

শিক্ষক ব্যবহার অভিজ্ঞতা

দ্বিতীয় লেখক বড় প্রোগ্রামিং প্রবর্তনী কোর্সে ব্যবহার করেছেন, অ্যাসাইনমেন্ট এবং পরীক্ষা অন্তর্ভুক্ত
তৃতীয় লেখক সফটওয়্যার ইঞ্জিনিয়ারিং ভিত্তি কোর্সে শেল এবং Git জ্ঞান মূল্যায়ন করেছেন
পুনরাবৃত্তি বনাম কার্যকরী প্রোগ্রামিং প্যারাডাইমের সমান্তরাল উপস্থাপনা সমর্থন করে

পরীক্ষামূলক ফলাফল

প্রধান অনুসন্ধান

१. ব্যবহারযোগ্যতা যাচাইকরণ: সমস্ত বাস্তবে তৈরি সমস্যা যুক্তিসঙ্গত জটিলতা পরিসীমার মধ্যে থাকে (d≤८)

२. শিক্ষামূলক কার্যকারিতা:

শিক্ষার্থীরা একাধিক সমাধান পথ অন্বেষণ করতে পারে
একক সমাধানের চেয়ে আরও সমৃদ্ধ শেখার অভিজ্ঞতা প্রদান করে
Git কর্মপ্রবাহ শিক্ষায় ভাল বৈষম্য প্রদর্শন করে

३. সিস্টেম কর্মক্ষমতা:

অ্যালগরিদম ব্যবহারিক প্রয়োগে ভাল কর্মক্ষমতা প্রদর্শন করে
PrairieLearn প্ল্যাটফর্মে সফলভাবে একীভূত
বিদ্যমান DAG স্কোরিং অ্যালগরিদমের সুবিধা বজায় রাখে

প্রয়োগ কেস বিশ্লেষণ

প্রোগ্রামিং উদাহরণ

যোগফল ফাংশন সমস্যা ४টি বৈধ সমাধান প্রদর্শন করে:

বিস্তারিত পদ্ধতি: ভেরিয়েবল ঘোষণা, ধাপে ধাপে সংযোজন
সংক্ষিপ্ত পদ্ধতি: সরাসরি অ্যাসাইনমেন্ট অভিব্যক্তি
মিশ্র পদ্ধতি: দুটি পদ্ধতির সমন্বয় ভেরিয়েন্ট

গাণিতিক প্রমাণ উদাহরণ

সম সংখ্যা সম্পত্তি প্রমাণ দুটি পদ্ধতি সমর্থন করে:

সরাসরি প্রমাণ: n সমান অনুমান করুন, n+१० সমান প্রমাণ করুন
প্রমাণ দ্বারা বিরোধাভাস: n+१० বিজোড় অনুমান করুন, বিরোধাভাস উদ্ভব করুন

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. প্রযুক্তিগত সম্ভাব্যতা: মাল্টিগ্রাফ ভাঁজ অ্যালগরিদম সফলভাবে ঐচ্ছিক ব্লকের প্রতিনিধিত্ব এবং স্কোরিং সমস্যা সমাধান করে २. শিক্ষামূলক মূল্য: একাধিক সমাধান সমর্থন করে এমন ব্লক অর্ডারিং সমস্যা বাস্তব-বিশ্বের সমস্যা সমাধান প্রক্রিয়া আরও ভালভাবে প্রতিফলিত করে ३. ব্যাপক প্রযোজ্যতা: পদ্ধতি প্রোগ্রামিং, গণিত এবং সিস্টেম ব্যবস্থাপনা সহ একাধিক ক্ষেত্রে প্রয়োগ মূল্য রয়েছে

সীমাবদ্ধতা

१. জটিলতা বৃদ্ধি: DAG সংখ্যা রঙ নির্বাচনের সাথে সূচকীয়ভাবে বৃদ্ধি পায়, তাত্ত্বিকভাবে নির্দিষ্ট সমস্যার ব্যবহার সীমাবদ্ধ করতে পারে २. ইন্টারফেস ডিজাইন: প্রচুর ব্লক জ্ঞানীয় চাপ বৃদ্ধি করতে পারে, আরও ভাল ব্যবহারকারী ইন্টারফেস ডিজাইনের প্রয়োজন ३. মূল্যায়ন সীমিত: বৃহৎ-স্কেল শেখার কার্যকারিতা মূল্যায়ন গবেষণার অভাব

ভবিষ্যত দিকনির্দেশনা

१. শেখার কার্যকারিতা গবেষণা: শিক্ষার্থী শেখার উপর বহু-সমাধান পদ্ধতির নির্দিষ্ট প্রভাব মূল্যায়ন করুন २. ইন্টারফেস অপ্টিমাইজেশন: জ্ঞানীয় চাপ হ্রাস করে এমন ব্যবহারকারী ইন্টারফেস বিকাশ করুন ३. ন্যায্যতা গবেষণা: পরীক্ষার পরিবেশে মূল্যায়ন করুন যে বহু-সমাধান পদ্ধতি পূর্বধারণা মিলের কারণে অন্যায্য সুবিধা হ্রাস করতে পারে কিনা

গভীর মূল্যায়ন

শক্তি

१. প্রযুক্তিগত উদ্ভাবনী: মাল্টিগ্রাফ থেকে DAG ভাঁজ অ্যালগরিদম ডিজাইন চতুর, তাত্ত্বিক ভিত্তি দৃঢ় २. ব্যবহারিক মূল্য: শিক্ষা প্রযুক্তিতে বাস্তব চাহিদা সমাধান করে, ইতিমধ্যে একাধিক কোর্সে প্রয়োগ করা হয়েছে ३. সিস্টেম সম্পূর্ণতা: অ্যালগরিদম ডিজাইন থেকে সিস্টেম বাস্তবায়ন থেকে শিক্ষামূলক প্রয়োগ সম্পূর্ণ চক্র গঠন করে ४. ক্রস-ডোমেইন প্রযোজ্যতা: প্রোগ্রামিং, গণিত, সিস্টেম ব্যবস্থাপনা ইত্যাদি একাধিক ক্ষেত্রে প্রয়োগ মূল্য প্রদর্শন করে

অপূর্ণতা

१. মূল্যায়ন গভীরতা: প্রধানত বর্ণনামূলক প্রমাণের উপর নির্ভর করে, কঠোর শেখার কার্যকারিতা তুলনামূলক পরীক্ষার অভাব २. তাত্ত্বিক বিশ্লেষণ: জটিলতা বিশ্লেষণ প্রদান করে যদিও শেখার তত্ত্বের আলোচনা তুলনামূলকভাবে দুর্বল ३. ব্যবহারকারী অভিজ্ঞতা: জটিল সমস্যা পরিচালনার জন্য আরও ভাল ব্যবহারকারী ইন্টারফেস ডিজাইন করার উপায় সম্পর্কে আলোচনা পর্যাপ্ত নয়

প্রভাব

१. প্রযুক্তিগত অবদান: শিক্ষা প্রযুক্তি ক্ষেত্রে বহু-সমাধান পদ্ধতি পরিচালনার জন্য সাধারণ পদ্ধতি প্রদান করে २. শিক্ষামূলক অনুশীলন: ঐতিহ্যবাহী ব্লক অর্ডারিং সমস্যা ডিজাইন চিন্তাভাবনা পরিবর্তন করে ३. গবেষণা অনুপ্রেরণা: কাজ করা উদাহরণ তত্ত্ব এবং বিঘ্নকারী আইটেম গবেষণার জন্য নতুন দৃষ্টিভঙ্গি প্রদান করে

প্রযোজ্য পরিস্থিতি

१. প্রোগ্রামিং শিক্ষা: একাধিক প্রোগ্রামিং প্যারাডাইম এবং সমাধান প্রদর্শনের পরিস্থিতিতে উপযুক্ত २. গণিত শিক্ষা: বিশেষত একাধিক প্রমাণ পদ্ধতি সহ উপপাদ্য শিক্ষায় উপযুক্ত ३. দক্ষতা প্রশিক্ষণ: সিস্টেম ব্যবস্থাপনা, সরঞ্জাম ব্যবহার ইত্যাদি একাধিক অপারেশন পথ সহ দক্ষতা প্রশিক্ষণে উপযুক্ত

তথ্যসূত্র

এই পেপারটি শিক্ষা প্রযুক্তি ক্ষেত্রের গুরুত্বপূর্ণ সাহিত্য উদ্ধৃত করে, যার মধ্যে রয়েছে:

Parsons সমস্যার মূল গবেষণা १४
Proof Blocks এর ভিত্তি কাজ १६,१७
অভিযোজনশীল শেখা এবং কাজ করা উদাহরণ তত্ত্ব সম্পর্কিত গবেষণা १,६,८
বিঘ্নকারী আইটেম প্রভাব অভিজ্ঞতামূলক গবেষণা ९,१०,१९

সামগ্রিক মূল্যায়ন: এটি শিক্ষা প্রযুক্তি ক্ষেত্রে গুরুত্বপূর্ণ অবদান সহ একটি পেপার, যা প্রস্তাবিত মাল্টিগ্রাফ ভাঁজ অ্যালগরিদম মার্জিতভাবে ব্লক অর্ডারিং সমস্যায় ঐচ্ছিক ব্লক সমর্থন সমস্যা সমাধান করে। যদিও শেখার কার্যকারিতার অভিজ্ঞতামূলক মূল্যায়নে উন্নতির জায়গা রয়েছে, তবে এর প্রযুক্তিগত উদ্ভাবনী এবং ব্যবহারিক মূল্য এটিকে এই ক্ষেত্রের একটি গুরুত্বপূর্ণ অগ্রগতি করে তোলে।