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.

There exist several general techniques in the literature for speeding up naive implementations of dynamic programming. Two of the best known are the Knuth-Yao quadrangle inequality speedup and the SMAWK algorithm for finding the row-minima of totally monotone matrices. Although both of these techniques use a quadrangle inequality and seem similar, they are actually quite different and have been used differently in the literature. In this article we show that the Knuth-Yao technique is actually a direct consequence of total monotonicity. As well as providing new derivations of the Knuth-Yao result, this also permits to solve the Knuth-Yao problem directly using the SMAWK algorithm. Another consequence of this approach is a method for solving online versions of problems with the Knuth-Yao property. The online algorithms given here are asymptotically as fast as the best previously known static ones. For example, the Knuth-Yao technique speeds up the standard dynamic program for finding the optimal binary search tree of n elements from Θ( n 3 ) down to O ( n 2 ), and the results in this article allow construction of an optimal binary search tree in an online fashion (adding a node to the left or the right of the current nodes at each step) in O ( n ) time per step.

Algorithms for series-parallel graphs can be extended to arbitrary two-terminal dags if node reductions are used along with series and parallel reductions. A node reduction contracts a vertex with unit in-degree (out-degree) into its sole incoming (outgoing) neighbor. This paper gives an $O(n^{2.5} )$ algorithm for minimizing node reductions, based on vertex cover in a transitive auxiliary graph. Applications include the analysis of PERT networks, dynamic programming approaches to network problems, and network reliability. For NP-hard problems one can obtain algorithms that are exponential only in the minimum number of node reductions rather than the number of vertices. This gives improvements if the underlying graph is nearly series-parallel.