Understanding what students expect from undergraduate teaching assistants (tutors) is essential to improving the effectiveness of student-tutor interactions. Building on the work of Lim et al. (2023), this study replicates and extends prior research by conducting 23 semi-structured interviews across four institutions to further examine the expectations students have on tutors in university CS2 courses. The original study was scoped within a single institution; by expanding beyond a single-institution sample, we examine the generalizability of previously identified student expectations and explore new perspectives on the tutor's role during tutoring hours. Our findings reveal a large set of roles tutors are expected to play. These roles can be categorized into tutors as solutionists, diagnosticians, and facilitators. Tutors are expected to play these roles, switch between them, or at times take on multiple roles at once. We detail the expectations associated with each category and surface both confirmed and novel findings relative to Lim et al.'s work. Our discussion highlights the emotional labors involved in tutoring, identifies implicit and sometimes unreasonable student expectations, and provides a practical framework for supporting tutors in aligning their efforts with student needs. Implications and limitations of our categorization of roles are discussed alongside directions for future research.

We give a new rapid mixing result for a natural random walk on the independent sets of a graph $G$. We show that when $G$ has bounded treewidth, this random walk -- known as the Glauber dynamics for the hardcore model -- mixes rapidly for all fixed values of the standard parameter $λ> 0$, giving a simple alternative to existing sampling algorithms for these structures. We also show rapid mixing for analogous Markov chains on dominating sets, $b$-edge covers, $b$-matchings, maximal independent sets, and maximal $b$-matchings. (For $b$-matchings, maximal independent sets, and maximal $b$-matchings we also require bounded degree.) Our results imply simpler alternatives to known algorithms for the sampling and approximate counting problems in these graphs. We prove our results by applying a divide-and-conquer framework we developed in a previous paper, as an alternative to the projection-restriction technique introduced by Jerrum, Son, Tetali, and Vigoda. We extend this prior framework to handle chains for which the application of that framework is not straightforward, strengthening existing results by Dyer, Goldberg, and Jerrum and by Heinrich for the Glauber dynamics on $q$-colorings of graphs of bounded treewidth and bounded degree.

Markov Chain Monte Carlo (MCMC) algorithms are a widely-used algorithmic tool for sampling from high-dimensional distributions, a notable example is the equilibirum distribution of graphical models. The Glauber dynamics, also known as the Gibbs sampler, is the simplest example of an MCMC algorithm; the transitions of the chain update the configuration at a randomly chosen coordinate at each step. Several works have studied distributed versions of the Glauber dynamics and we extend these efforts to a more general family of Markov chains. An important combinatorial problem in the study of MCMC algorithms is random colorings. Given a graph G of maximum degree Δ and an integer k ≥ Δ+1, the goal is to generate a random proper vertex k-coloring of G. Jerrum (1995) proved that the Glauber dynamics has O(nlog{n}) mixing time when k > 2Δ. Fischer and Ghaffari (2018), and independently Feng, Hayes, and Yin (2018), presented a parallel and distributed version of the Glauber dynamics which converges in O(log{n}) rounds for k > (2+ε)Δ for any ε > 0. We improve this result to k > (11/6-δ)Δ for a fixed δ > 0. This matches the state of the art for randomly sampling colorings of general graphs in the sequential setting. Whereas previous works focused on distributed variants of the Glauber dynamics, our work presents a parallel and distributed version of the more general flip dynamics presented by Vigoda (2000) (and refined by Chen, Delcourt, Moitra, Perarnau, and Postle (2019)), which recolors local maximal two-colored components in each step.

The objective of the well-known Tower of Hanoi puzzle is to move a set of discs one at a time from one of a set of pegs to another, while keeping the discs sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement.