We introduce and study a two-stage stochastic stable matching problem between students and schools. A decision maker chooses a stable matching in a marriage instance;then, after some agents enter or leave the market f...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
We introduce and study a two-stage stochastic stable matching problem between students and schools. A decision maker chooses a stable matching in a marriage instance;then, after some agents enter or leave the market following a probability distribution D, chooses a stable matching in the new instance. The goal is, roughly speaking, to maximize the expected quality of the matchings across the two stages and minimize the expected students' discontent for being downgraded to a less preferred school in the second-stage. We consider both the case when D is given explicitly and when it is accessed via a sampling oracle. In the former case, we give a polynomial time algorithm. In the latter case, we show that, unless P = NP, no algorithm can find the optimal value or the optimal solution of the problem in polynomial-time. On the positive side, we give a pseudopolynomial algorithm that computes a solution of arbitrarily small additive error. Our techniques include the use of a newly defined poset of stable pairs, which may be of independent interest.
computerscience instructors have long advised students that success in CS1 requires many hours, such as 8-10 hours/week outside class time, but students often don't believe it. Recently, the most-widely used CS1 ...
详细信息
ISBN:
(纸本)9798400701399
computerscience instructors have long advised students that success in CS1 requires many hours, such as 8-10 hours/week outside class time, but students often don't believe it. Recently, the most-widely used CS1 learning system (zyBooks), which is web-native and records student activity data, began providing instructors with data on student time spent reading and answering reading questions, solving small homework problems, and coding the programming assignments, all online and autograded, representing nearly all a student's time outside class. In our 300+ student CS1 course at a large state university in Spring 2022, we required all work to be done in the zyBook and analyzed student time, including analysis relative to self-reported prior programming experience. Students who completed the class averaged 6.1 hours/week, with a large standard deviation of 2.3, and averaged a B+. Students averaged 6.9 hours in weeks 1-5 leading up to the midterm, peaking at 9 hours in Week 5. We found that over 90% of students who averaged 9-12 hours/week earned As or Bs, even those reporting no prior programming experience. Spending under 4 hours/week nearly guaranteed failing the midterm, and almost no students who spent fewer than 6 hours/week got an A on the midterm (unless they had prior experience). We also found that measuring actual time is important because students overreport time in surveys. With this concrete time data available to share with CS1 students, the hope is that future students may be more likely to allocate the time needed for success in CS1.
Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomi...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give a family of n-node graphs for which every polynomial-sizeMIP formulation requires Omega(n/ log(2) n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack problems. In both cases, this improves the previously known bounds of Omega(root n/ log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we show that there exists a family of n-node graphs whose stable set polytopes satisfy the following: any (1 + epsilon/n)-approximate extended formulation for these polytopes, for some constant epsilon > 0, has size 2(Omega(n / log n)). Our proof extends and simplifies the information-theoretic methods due to Goos, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) who showed the same result for the case of exact extended formulations (i.e. epsilon = 0).
On many occasions, Rocco De Nicola has shown an amazing ability to combine different research topics to offer original results to seemingly different research problems. We review the origins of Klaim, one of the outst...
详细信息
ISBN:
(纸本)9783031737084;9783031737091
On many occasions, Rocco De Nicola has shown an amazing ability to combine different research topics to offer original results to seemingly different research problems. We review the origins of Klaim, one of the outstanding ideas of Rocco that, around the mid-nineties, emerged as a solution for problems at the confluence of research in process calculi, models of distributed coordination, and languages for network-aware programming. Besides the opportunity to reconstruct Klaim's genesis and reflect on its impact, which continues over time, this paper is a sign of our gratitude to Rocco for sharing his ideas, views, and friendship with us.
Game design is often considered a motivational approach to get young children interested in programming and computational thinking. However, while the idea of game programming may be compelling from an educational poi...
详细信息
ISBN:
(纸本)9798400710056
Game design is often considered a motivational approach to get young children interested in programming and computational thinking. However, while the idea of game programming may be compelling from an educational point of view, creating games with interesting interactions that are actually fun to play remains challenging. Modern tools aimed at novice programmers should empower their users to create games, such as Pac-Man, that approach or even exceed the gameplay of 1980's arcade games. By adding a high-level AI pathfinding block to the *** tool, 13 students in grades 1-4 attempted to build Pac-Man-like games. The findings suggest that all students were able to create Pac-Man-like games with compelling gameplay interactions, including ghosts finding the shortest path through complex mazes to Pac-Man, multiple ghosts collaborating with each other, and sophisticated game world topologies featuring toroidal portals.
Background and Context: Learning to create self-directed and personally authentic programming projects involves encountering challenges and learning to get unstuck. Objective: This article investigates how one U.S. fo...
详细信息
Background and Context: Learning to create self-directed and personally authentic programming projects involves encountering challenges and learning to get unstuck. Objective: This article investigates how one U.S. fourth-grade classroom engaged in practices which emphasized community supports, in the context of the classroom's implementation and testing of an upper elementary intermediate Scratch curriculum. Method: We engaged in thematic analysis of classroom observations, student and teacher interviews, and student and teacher reflection journals, and student work. Findings: We explore three interaction types: remixing others' projects and ideas, asking for help and helping others, and talking about projects in class. Working on and talking about programming projects enabled learners to develop new understandings of themselves and their peers. Implications: Teachers play a central role in designing structures which encourage the development of students' individual creative capacity and the classroom's sense of community. We offer considerations for designing engaging and collaborative experiences in elementary and intermediate computing education.
Although answer set programming has been a tried way of problem-solving for over thirty years, few tools and methodologies exist today to test it rigorously. Previous research suggests that mutation testing is able to...
详细信息
ISBN:
(纸本)9783031808883;9783031808890
Although answer set programming has been a tried way of problem-solving for over thirty years, few tools and methodologies exist today to test it rigorously. Previous research suggests that mutation testing is able to uncover flaws even with small inputs. In this paper, we introduce clingabomino, a mutant generator implemented in C++ that directly operates on the abstract syntax tree of the Clingo solver. Our tool consists of a command-line application that implements commonly useful mutation operators as well as a library to aid in the development of domain-specific mutation operators.
Large language models (LLMs) are becoming increasingly better at a wide range of Natural Language Processing tasks (NLP), such as text generation and understanding. Recently, these models have extended their capabilit...
详细信息
ISBN:
(纸本)9798400705311
Large language models (LLMs) are becoming increasingly better at a wide range of Natural Language Processing tasks (NLP), such as text generation and understanding. Recently, these models have extended their capabilities to coding tasks, bridging the gap between natural languages (NL) and programming languages (PL). Foundational models such as the Generative Pre-trained Transformer (GPT) and LLaMA series have set strong baseline performances in various NL and PL tasks. Additionally, several models have been fine-tuned specifically for code generation, showing significant improvements in code-related applications. Both foundational and fine-tuned models are increasingly used in education, helping students write, debug, and understand code. We present a comprehensive systematic literature review to examine the impact of LLMs in computerscience and computer engineering education. We analyze their effectiveness in enhancing the learning experience, supporting personalized education, and aiding educators in curriculum development. We address five research questions to uncover insights into how LLMs contribute to educational outcomes, identify challenges, and suggest directions for future research.
Novice learners of programming tend to neglect error messages, even though the messages have a lot of useful information for solving problems. While there exists research that aims to user-friendly error messages by c...
详细信息
ISBN:
(纸本)9798400701382
Novice learners of programming tend to neglect error messages, even though the messages have a lot of useful information for solving problems. While there exists research that aims to user-friendly error messages by changing the wording and by adding visual assistance, most of them do not focus on drawing learners' attention to error messages. We propose the enbugging quiz, a novel quiz format that requests the learner to craft a program that produces a specified error. This paper reports our design of enbugging quizzes and reports the results of our initial experiment, where we observed positive effects on the learners' attitudes towards error messages.
This paper describes a new memetic semantic algorithm for symbolic regression (SR). While memetic computation offers a way to encode domain knowledge into a population-based process, semantic-based algorithms allow on...
详细信息
ISBN:
(数字)9783031295737
ISBN:
(纸本)9783031295720;9783031295737
This paper describes a new memetic semantic algorithm for symbolic regression (SR). While memetic computation offers a way to encode domain knowledge into a population-based process, semantic-based algorithms allow one to improve them locally to achieve a desired output. Hence, combining memetic and semantic enables us to (a) enhance the exploration and exploitation features of genetic programming (GP) and (b) discover short symbolic expressions that are easy to understand and interpret without losing the expressivity characteristics of symbolic regression. Experimental results show that our proposed memetic semantic algorithm can outperform traditional evolutionary and non-evolutionary methods on several real-world symbolic regression problems, paving a new direction to handle both the bloating and generalization endeavors of genetic programming.
暂无评论