We introduce CyberQuest, an interactive learning platform for teaching cybersecurity to upper secondary school students. It is fully web-based, does not require additional software besides a browser, and provides an entry barrier that is as low as possible for novices. Two main components form the platform: the lesson center and the ''target applications.'' The lesson center holds the theoretical lessons, questions, exercise tasks that require an interaction with the target applications, as well as progress tracking and classroom management for teachers. The target applications are sandbox environments that mimic common real-world apps that are interesting for educational purposes.

We study the proportional online knapsack problem with removal. For randomized algorithms, we tighten the gap between the current lower and upper bounds on the expected competitive ratio by presenting a lower bound of roughly 1.27. We further study this problem under the model of online algorithms with predictions. Our lower bound arguments are agnostic to the type of available prediction, which makes them very general. For deterministic algorithms, we provide a tightly matching upper bound on the competitive ratio for a specific kind of weight prediction.

The shift to BYOD (bring your own device) policies at schools requires browser-based programming tools that balance accessibility and functionality. We introduce WebTigerPython, a Python IDE combining novice-friendly features (Turtle graphics, robotics, error messages) with advanced capabilities (NumPy, Matplotlib). Its client-side execution and web worker architecture ensure non-blocking interactivity. Python code is run in WebAssembly, performing only about three times slower than native CPython but significantly faster than other web-based IDEs to which we compared it. Deployed in classrooms with 800+ daily users, WebTigerPython supports offline use, URL-based sharing of code, and aligns with existing curricula—demonstrating how web tools can rival local IDEs without compromising power or accessibility.

Programming, its status in education, and how its fundamental concepts can be taught to an inexperienced audience are among the oldest debates in the field of computer science education. While there is consensus about programming being a crucial skill to acquire, there is much less consensus about which programming paradigm to use. Popular paradigms include both block-based and text-based programming.

We survey the current state of research on the knapsack problem in online and semi-online environments. In particular, we summarize what is known about models where different assumptions commonly made in online computation are relaxed: namely that online algorithms do not know the complete instances they are processing; have to make decisions that are irrevocable; and deal with an input chosen by a malicious adversary.

Graph coloring is a notoriously challenging problem, especially when considering the online setting where each arriving vertex must be colored immediately and irreversibly. Even on trees, which are trivially two-colorable, achieving anything better than a logarithmic competitive ratio becomes impossible if the order of arrival is adversarially determined. We investigate tree coloring in a slightly relaxed model where vertices arrive online but in random order, focusing specifically on algorithms with predictions of varying reliability. Furthermore, we extend our analysis to all two-colorable graphs and provide matching lower bounds for both cases.

The time-optimal k-server problem minimizes the time spent instead of the distance traveled when serving n requests, appearing one after the other, with k servers in a metric space. The classical distance model was motivated by a hard disk with k heads. Instead of minimal head movements, the time model aims for optimal reading speeds. This paper provides a lower bound of 2k-1 on the competitive ratio of any deterministic online algorithm for the time-optimal k-server problem on a specifically designed metric space. This lower bound coincides with the best known upper bound on the competitive ratio for the classical k-server problem, achieved by the famous work function algorithm. We provide further lower bounds of k+1 for all Euclidean spaces and k for uniform metric spaces. Our most technical result, proven by applying Yao’s principle to a suitable instance distribution, is a lower bound of k+H_k-1 that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem, which is polylogarithmic in k. We hope to initiate further intensive study of this natural problem.

We introduce a learning platform to teach cybersecurity topics in an interactive way to a K--12 audience. The platform targets cybersecurity novices and is entirely browser-based, making using it in class as simple as possible. It consists of two main components: a lesson center and a small mock social media network. The lesson center introduces students to basic concepts such as HTTP status codes and cookies, and asks them to carry out simple tasks within the social media network. Furthermore, students can look behind the curtains to see what kind of data is generated through interactions with the network. The ultimate goal is to ''hack'' into the social media network and impersonate a different user.

Abstract We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide whether or not and how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack’s capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical knapsack problem (also called the 0-1 knapsack problem), the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm’s performance. More randomness lowers the competitive ratio to less than 1 . 736 , but it can never be below 1 . 693 . In the advice complexity setting, we measure how many bits of information (so-called advice bits) the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to $$\varvec{3/2}$$ 3 / 2 . While this cannot be improved with fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n} $$ log 2 n advice bits for instances of length n , a competitive ratio of $$\varvec{1}\varvec{+}\varvec{\varepsilon }$$ 1 + ε can be achieved with $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$ O ( ε - 1 · log ( n ε - 1 ) ) advice bits for any $$\varvec{\varepsilon }\varvec{>}\varvec{0}$$ ε > 0 . We further show that no amount of advice bounded by a function $$\varvec{f(n)}$$ f ( n ) allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for both deterministic and randomized algorithms, as well as for algorithms using fewer than $$\varvec{\log }_{\varvec{2}} \varvec{n}$$ log 2 n advice bits. We also provide a surprisingly simple algorithm that uses $$\varvec{O}\varvec{(}\varvec{\varepsilon }^{\varvec{-1}} \varvec{\cdot }\varvec{\log }\varvec{(}\varvec{n}\varvec{\varepsilon }^{\varvec{-1}}\varvec{))}$$

Abstract Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighbor instances, that is, instances with one local modification? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems, most notably, graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, colorability and vertex cover. For example, we show that it is $$\text {NP}$$ NP -hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in $$\text {P}$$ P . We observe that vertex cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for $$\text {DP}$$ DP (differences of $$\text {NP}$$ NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For vertex cover, we show that recognizing $$\beta $$ β -vertex-critical graphs is complete for $$\Theta _2^\text {p}$$ Θ 2 p (parallel access to $$\text {NP}$$ NP ), obtaining the first completeness result for a criticality problem for this class.

Understanding data flow and tracing the values of variables across a program is an essential skill for reading and comprehending program code. Two major hurdles in tracing variable values are variable (re)assignment and scopes with parameter passing and possible shadowing of variables.

Abstract We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we identify a broad class of online problems for which the existence of a randomized online algorithm with constant expected competitive ratio r implies the existence of a randomized online algorithm that has a competitive ratio of $$(1+\varepsilon )r$$ ( 1 + ε ) r with high probability, measured with respect to the optimal profit or cost, respectively. The class of problems includes some of the well-studied online problems such as paging, k-server, and metrical task systems on finite metric spaces.

We are given nodes in a communication network that request connections to other nodes. A central authority may accept or reject such a request right away, and once a connection is established its duration is unbounded and its edges cannot be used for other connections; actions are performed without knowledge of future requests, that is, we consider an online setting. We examine this so-called call admission problem in tree networks. The focus is on the quality of solutions achievable in an advice setting, that is, when the central authority has a certain amount of information on the incoming requests. We show that O(mlog2⁡d) bits of additional information are sufficient for an online algorithm run by the central authority to perform as well as an optimal offline algorithm, where m is the number of edges and d is the largest degree in the tree network. In the case of a star tree network, we show that Ω(mlog2⁡d) bits are also necessary (note that d=m). We also present a lower bound on the advice complexity for small constant competitive ratios and an algorithm whose competitive ratio gradually improves with added advice bits to 2⌈log2⁡n⌉, where n is the number of nodes in the network.

With its direct feedback and the tangible machine, robotics is a strong motivator for engaging students in STEM fields, as evidenced by the popularity of competitions and events such as FIRST and Robo Games. However, in the context of K-12 computer science education, the potential of robotics seems as yet hardly tapped into. In an attempt to bridge the gap, we designed a Python library for robotics with Lego's EV3 robots to complement programming classes. We employed our library to teach secondary school students as part of an outreach activity. Our approach is built around open-ended tasks instead of narrow exercise statements. Although our activity was based on the EV3 Space Challenge Set, we encouraged the students at any time to pursue their own ideas and even their own challenges. While students had little problems in using Python to program their robots, we still found a series of misconceptions and observed that female students were more interested in following their own creative projects than in solving given challenges.

Can we efficiently compute optimal solutions to instances of a hard problem from optimal solutions to neighboring (i.e., locally modified) instances? For example, can we efficiently compute an optimal coloring for a graph from optimal colorings for all one-edge-deleted subgraphs? Studying such questions not only gives detailed insight into the structure of the problem itself, but also into the complexity of related problems; most notably graph theory’s core notion of critical graphs (e.g., graphs whose chromatic number decreases under deletion of an arbitrary edge) and the complexity-theoretic notion of minimality problems (also called criticality problems, e.g., recognizing graphs that become 3-colorable when an arbitrary edge is deleted). We focus on two prototypical graph problems, Colorability and Vertex Cover. For example, we show that it is NP-hard to compute an optimal coloring for a graph from optimal colorings for all its one-vertex-deleted subgraphs, and that this remains true even when optimal solutions for all one-edge-deleted subgraphs are given. In contrast, computing an optimal coloring from all (or even just two) one-edge-added supergraphs is in P. We observe that Vertex Cover exhibits a remarkably different behavior, demonstrating the power of our model to delineate problems from each other more precisely on a structural level. Moreover, we provide a number of new complexity results for minimality and criticality problems. For example, we prove that Minimal-3-UnColorability is complete for DP (differences of NP sets), which was previously known only for the more amenable case of deleting vertices rather than edges. For Vertex Cover, we show that recognizing beta-vertex-critical graphs is complete for Theta_2^p (parallel access to NP), obtaining the first completeness result for a criticality problem for this class.

We study the relationship between the competitive ratio and the tail distribution of randomized online problems. To this end, we define a broad class of online problems that includes some of the well-studied problems like paging, k-server and metrical task systems on finite metrics, and show that for these problems it is possible to obtain, given an algorithm with constant expected competitive ratio, another algorithm that achieves the same solution quality up to an arbitrarily small constant error with high probability; the "high probability" statement is in terms of the optimal cost. Furthermore, we show that our assumptions are tight in the sense that removing any of them allows for a counterexample to the theorem.