Algorithms courses are a foundational part of an undergraduate computer science degree that require abstract thinking and creativity and are known to be challenging for many students. Recently researchers have been developing auto-graded tools to scaffold students through the problem-solving process. We examine student's perceptions of such a tool in a required upper-division Algorithms course at a R1 University. The goal of the tool is to improve student experience in three ways: (1) help students break down the problem-solving process into clear steps; (2) increase students' self-efficacy by raising their confidence and understanding of the material; (3) have low ''cost'', by being easy to use, enjoyable, and a good use of students' time. The tool itself is designed to provide these benefits to students at every level of mastery through instantaneous feedback over increasingly challenging problems. It is designed as an addition to and not complete replacement of the written homework in the course. Based on a survey of almost 1000 students across four semesters, each with a different instructor, we examine whether student feedback is favorable over all four offerings, and for groups of students with different course outcomes. Using qualitative and quantitative methods, we found that across each of the four semesters and across letter grades A, B, C, and D students favored the tool as compared to written homework.

We study a generalization of the widely studied discrete influence maximization problem. We consider that instead of marketers using a budget to send free products to a few influencers, they can provide discounts to partly incentivize a larger set of influencers with the same budget. We show that this problem is an instance of maximizing the multilinear extension of a monotone submodular set function subject to an L1 constraint and characterize its optimal solution in terms of the solutions to the discrete influence maximization problem. We then use this characterization to propose and analyze an efficient (1 - 1/e)-approximation algorithm. We also show that with negligible additional work, this algorithm also allows the marketer to evaluate cost-benefit trade-offs over a range of budgets. Furthermore, we performed small-scale experiments on synthetic and real-world social networks to demonstrate our optimal solution characterization and greedy approximation. We also performed large-scale experiments on real-world social networks to show the performance and scalability of our method in contrast to methods proposed for other generalizations of influence maximization. Moreover, we demonstrated the practicality of our method in evaluating the cost-benefit tradeoffs involving budget selection for desired influence and profit maximization.

We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.

We show that a variant of the continuous Fréchet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version. The new variant is not necessarily monotone, but this shortcoming can be easily handled via refinement. Combined with a Dijkstra/Prim type algorithm, this leads to a realization of the Fréchet distance (i.e., a morphing) that is locally optimal (aka locally correct), that is both easy to compute, and in practice, takes near linear time on many inputs. The new morphing has the property that the leash is always as short as possible. These matchings/morphings are more natural, and are better than the ones computed by standard algorithms - in particular, they handle noise more graciously. This should make the Fréchet distance more useful for real world applications. We implemented the new algorithm, and various strategies to obtain fast practical performance. We performed extensive experiments with our new algorithm, and released publicly available (and easily installable and usable) Julia and Python packages. In particular, the Julia implementation, for computing the regular Fréchet distance, seems to be {significantly faster} than other currently available implementations. See Table 2.2. Our algorithms can be used to compute the almost-exact Fréchet distance between polygonal curves. Implementations and numerous examples are available here: https://frechet.xyz.

We consider the fractional influence maximization problem, i.e., identifying users on a social network to be incentivized with potentially partial discounts to maximize the influence on the network. The larger the discount given to a user, the higher the likelihood of its activation (adopting a new product or innovation), who then attempts to activate its neighboring users, causing a cascade effect of influence through the network. Our goal is to devise efficient algorithms that assign initial discounts to the network's users to maximize the total number of activated users at the end of the cascade, subject to a constraint on the total sum of discounts given. In general, the activation likelihood could be any non-decreasing function of the discount, whereas, our focus lies on the case when the activation likelihood is an affine function of the discount, potentially varying across different users. As this problem is shown to be NP-hard, we propose and analyze an efficient (1-1/e)-approximation algorithm. Furthermore, we run experiments on real-world social networks to show the performance and scalability of our method.

Deterministic and nondeterministic finite automata (DFAs and NFAs) are abstract models of computation commonly taught in introductory computing theory courses. These models have important applications (such as fast regular expression matching), and are used to introduce formal language theory. Undergraduate students often struggle with understanding these models at first, due to the level of abstraction. As a result, various pedagogical tools have been developed to allow students to practice with these models.

In recent years, there has been increasing interest in network diffusion models and related problems. The most popular of these are the independent cascade and linear threshold models. Much of the recent experimental work done on these models requires a large number of simulations conducted on large graphs, a computationally expensive task suited for low-level languages. However, many researchers prefer the use of higher-level languages (such as Python) for their flexibility and shorter development times. Moreover, in many research tasks, these simulations are the most computationally intensive task, so it would be desirable to have a library for these with an interface to a high-level language with the performance of a low-level language. To fill this niche, we introduce CyNetDiff, a Python library with components written in Cython to provide improved performance for these computationally intensive diffusion tasks.