Adding to a recently started collection of algorithmic in-class activities, we present new mathematically-oriented activities for mid- to upper-level algorithms courses, aiming to improve students' understanding of arguments of algorithm correctness and other underlying mathematical concepts. We also summarize our preliminary findings: student responses about their impressions of the activities in three different educational settings.

We created and field-tested in-class activities that target mathematical underpinnings of algorithms such as proofs of correctness, design of counterexamples for incorrect algorithms, and design of (correct) new algorithms. These challenging topics are difficult for the students to grasp, and this issue is further exacerbated by students' varied mathematical background and classes with large enrollments. Active learning has become very popular in introductory courses, but materials for algorithms appear to be lacking. We are aware of existing activities that ask students to trace a standard algorithm, which helps them to understand how that algorithm works, but often not why. Our activities target the ''why'' aspect: the algorithmic critical thinking. We deployed our activities in two classes: a large class of 108 students and a small honors section of 8 students. We describe our activities, the rationale behind them, and our impressions and students' feedback related to these activities.

In many CS educational research studies, students are surveyed to understand their reactions to a particular pedagogical approach or tool. These surveys, as well as other types of evaluations, often invite students to provide open-ended feedback about their experiences. However, analyzing these comments can prove to be a challenge, especially to CS educators who may not have strong expertise in qualitative research methods. In addition, in a large study, evaluating all of the provided comments can consume a significant amount of researcher time. In this work, we undertook two separate conversations with ChatGPT in which we prompted it to perform qualitative analysis of a set of comments collected in an earlier study. This allowed us to begin to judge how effectively a modern large language model can serve as an assistant in qualitative analysis. We found that with the prompts we used, ChatGPT can reliably build a set of reasonable labels (codes) for a set of comments, but the application of its labels to specific comments may or may not be effective and human researchers still need to use care and their own understanding in interpreting its output.

Context-based assignments have been shown as effective and popular for introductory-level computing courses. We study the use of one such context, pencil puzzles (puzzles typically found in newspapers), in upper-level core computing courses. These puzzles are designed to inspire computational thinking, making them a great choice for introductory-level computing assignments, but their fit for upper-level courses is less clear. We collaborated with several instructors of upper-level courses at four institutions, who delivered a pencil-puzzle-based assignment in their course and allowed us to survey their students about their experience. Overall, the students indicated positive perceptions of the assignments. The most varied answers related to implementation aspects of the assignments. To analyze correlations between students' sentiments and their demographic and experiential background, we used mixed-effects regression modeling to analyze this heterogeneous data set. The survey responses were characterized by two dimensions, one roughly corresponding to students' sentiment about the assignment and the other to their technical assessment of the assignment. For the first dimension, we found that the students' self-reported level of preparedness from earlier courses positively correlated with their enjoyment of and satisfaction with the pencil puzzle assignment. The second dimension was correlated with both the level of preparedness as well as the students' self-reported problem solving type: Clarifier, Implementor, Ideator, and Developer. Somewhat surprisingly, the analysis indicated Ideator as being the most positively correlated with the technical aspects of the assignment. Notably, the analysis did not indicate any correlation with students' race or gender in either dimension.

We report on our experience using common natural language processing (NLP) tools to analyze two vastly different data sets of free-form responses collected during a study of assignments in introductory computing courses. Our first data set consists of typically short comments left by hundreds of students on assignment surveys. Our second data set is comprised of semi-structured individual interviews of eight instructors of up to an hour long each. We collected the data across several years as part of our investigation of the use of pencil puzzles as a context for introductory computer science. In an earlier work, we manually analyzed a fraction of the student comments (all data collected until that point), using grounded theory. The results were illuminating, but the process was very time consuming, consisting of manual assignment of a small number of codes to each comment. In this work, we investigate the usability of common NLP tools to speed up the process for the entire data set of student comments. We also applied these tools to the instructor interviews. The NLP tools do not appear to be effective to create the code base, but, once the code base was determined, they performed the actual coding (assignment of codes to each student comment) promisingly well. For the long-form instructor interviews, the situation was much more challenging, due to the wide-ranging nature of semi-structured interviews, interleaving discussion topics, and elements of natural speech. We report on the lessons learned while automatically analyzing these complex data sets.

Spectral independence is a recently developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n log n) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using L p -norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, and Yin, FOCS’13). The non-linearity of L p -norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the L p -analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph G (n, d/n) , where the previously known algorithms run in time n O (log d ) or applied only to large d . We refine these algorithmic bounds significantly, and develop fast nearly linear algorithms based on Glauber dynamics that apply to all constant d , throughout the uniqueness regime.

Complex systems across various domains can be naturally modeled as signed networks with positive and negative edges. In this work, we design a new class of signage models and show how to select the model parameters that best fit real-world datasets using maximum likelihood.

Signed networks (networks with positive and negative edges) commonly arise in various domains from molecular biology to social media. The edge signs -- i.e., the graph signage -- represent the interaction pattern between the vertices and can provide insights into the underlying system formation process. Generative models considering signage formation are essential for testing hypotheses about the emergence of interactions and for creating synthetic datasets for algorithm benchmarking (especially in areas where obtaining real-world datasets is difficult). In this work, we pose a novel Maximum-Likelihood-based optimization problem for modeling signages given their topology and showcase it in the context of gene regulation. Regulatory interactions of genes play a key role in the process of organism development, and when broken can lead to serious organism abnormalities and diseases. Our contributions are threefold: First, we design a new class of signage models for a given topology, and, based on the parameter setting, we discuss its biological interpretations for gene regulatory networks (GRNs). Second, we design algorithms computing the Maximum Likelihood -- depending on the parameter setting, our algorithms range from closed-form expressions to MCMC sampling. Third, we evaluated the results of our algorithms on synthetic datasets and real-world large GRNs. Our work can lead to the prediction of unknown gene regulations, novel biological hypotheses, and realistic benchmark datasets in the realm of gene regulation.

Introductory assignments in CS Theory ask students to construct instances of various computational models (such as finite automata, regular expressions, context-free grammars, or push-down automata) for a given language. Verifying the correctness of their model instance is challenging for beginner CS Theory students since the concepts are abstract and there are infinitely many possible inputs. The popular JFLAP software allows students to visualize the running of their instance on a specific input. We recently developed a server extension to JFLAP which checks whether a student's instance is equivalent to the instructor's solution and, if not, it returns a "witness string,'' an input string on which the student's construction and the correct solution differ.

The use of a well-chosen context for course assignments is widely regarded as motivating for students. However, it is challenging to study the utility of bringing a particular context to computing courses across different types of institutions and student demo- graphics. This is especially true in introductory computing since courses vary widely, for example, in topic order and depth of coverage. In this experience report, we present our approach to, and lessons learned from, studying the efficacy of a specific context for introductory computing assignments across a variety of environments. We focus on the context of pencil puzzles (puzzles like Sudoku or crosswords, designed to be solved on paper using a pencil) and the deployment and fit of pencil-puzzle-based assignments across different institutions' introductory curricula. We describe our overall process, including recruitment of instructors from a variety of institutions, development and deployment of assignments, and collection of student grade and survey data (including all necessary approvals). By design, we did not use the same assignment at each university, since we aimed to study the underlying context rather than a specific assignment, while also establishing the adoptability of the context to different circumstances. We discuss the heterogeneity of the resulting data set, how we chose to analyze it, and what conclusions can (and cannot) be drawn from such data. We conclude with lessons learned from this experience, with the hopes that they can help others who wish to propagate their innovations and study them in diverse situations.

We examined the efficacy of automatic partial credit approaches for assignments asking students to construct a Deterministic Finite Automaton (DFA) for a given language. We chose two DFA problems, and generated a representative sample of 10 benchmark submissions for each. Next, in order to get an accurate baseline of the results of human graders, we asked professors at our university to submit their grader guides to us. We found that the grader guides, at least within our institution, were very consistent but also quite problem-specific and reliant on human understanding, hence unlikely to lead to an automated process applicable to all DFA problems. We generated a "consensus grader guide'' and graded each benchmark submission, obtaining a baseline human partial credit score. Then, we assessed the submissions using three techniques proposed by Alur et al.: The Solution Syntactic Difference (SSD) technique's score corresponds to the number of changes that must be made to the DFA. The Problem Syntactic Difference (PSyD) score is based on converting each DFA into Monadic Second Order (MSO) Logic and examining the number of necessary changes. For Problem Semantic Difference (PSeD), the score is the limit of the ratio of incorrect strings to correct strings. The final score is the maximum of these three scores. In general, the results closely matched the consensus grades, but there were some peculiarities generated by PSeD. Additionally, for each problem, one submission included two separate types of mistakes. These submissions had automatic grades much lower than the consensus grades.

Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal $O(n \log n)$ sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations. Our main contribution is to relax the bounded-degree assumption that has so far been important in establishing and applying spectral independence. Previous methods for avoiding degree bounds rely on using $L^p$-norms to analyse contraction on graphs with bounded connective constant (Sinclair, Srivastava, Yin; FOCS'13). The non-linearity of $L^p$-norms is an obstacle to applying these results to bound spectral independence. Our solution is to capture the $L^p$-analysis recursively by amortising over the subtrees of the recurrence used to analyse contraction. Our method generalises previous analyses that applied only to bounded-degree graphs. As a main application of our techniques, we consider the random graph $G(n,d/n)$, where the previously known algorithms run in time $n^{O(\log d)}$ or applied only to large $d$. We refine these algorithmic bounds significantly, and develop fast $n^{1+o(1)}$ algorithms based on Glauber dynamics that apply to all $d$, throughout the uniqueness regime.

Computing theory is often perceived as challenging by students, and verifying the correctness of a student's automaton or grammar is time-consuming for instructors. Aiming to provide benefits to both students and instructors, we designed an automated feedback tool for assignments where students construct automata or grammars. Our tool, built as an extension to the widely popular JFLAP software, determines if a submission is correct, and for incorrect submissions it provides a "witness" string demonstrating the incorrectness.

Assignments based on meaningful real-world contexts have been shown to be valuable in introductory computing education. However, it can be difficult to distinguish the value of a broad context from the value of a particular instantiation of that context. In this work in progress, we report on our initial findings gathered from deployments of different pencil-puzzle-based assignments. Specifically, we have investigated the use of pencil puzzles as a contextual domain, working with instructors at eight institutions to deliver assignments appropriate to their situation and aligning with their existing materials. We then evaluate the assignments using student grades and survey responses regarding student perceptions of the assignments including self-assessed learning, given a wide array of demographic variables. Our initial results show that while there was some dependency of student responses on their prior programming experience, and female students' feedback were more positive about one aspect, overall these types of assignments do not appear to put particular groups of students at a strong (dis)advantage.

Sampling of various types of acyclic orientations of chordal graphs plays a central role in several AI applications. In this work we investigate the use of the recently proposed general partial rejection sampling technique of Guo, Jerrum, and Liu, based on the Lovasz Local Lemma, for sampling partial acyclic orientations. For a given undirected graph, an acyclic orientation is an assignment of directions to all of its edges so that there is no directed cycle. In partial orientations some edges are allowed to be undirected. We show how the technique can be used to sample partial acyclic orientations of chordal graphs fast and with a clearly specified underlying distribution. This is in contrast to other samplers of various acyclic orientations with running times exponentially dependent on the maximum degree of the graph.

Computing theory analyzes abstract computational models to rigorously study the computational difficulty of various problems. Introductory computing theory can be challenging for undergraduate students, and the overarching goal of our research is to help students learn these computational models. The most common pedagogical tool for interacting with these models is the Java Formal Languages and Automata Package (JFLAP). We developed a JFLAP server extension, which accepts homework submissions from students, evaluates the submission as correct or incorrect, and provides a witness string when the submission is incorrect. Our extension currently provides witness feedback for deterministic finite automata, nondeterministic finite automata, regular expressions, context-free grammars, and pushdown automata.

As one develops instructional innovations, it is important not only to propagate them into new and different environments, but also to study their efficacy in these new locations with different demographics of students. Previously, we showed that introductory CS assignments based on various pencil-and-paper puzzles are valuable, but this study was done at a single university. In this poster, we report on propagation of puzzle-based assignments to many universities and collection of the resulting data from these different contexts. This allows us to study the efficacy of the assignments in these disparate environments. In order to ease adoption at other universities, we are also interested in the experience of the instructors in implementing the assignments in their courses. Our overall goal is to "close the feedback loop" by collecting and analyzing all of this data to improve both their effectiveness and adoptability. This poster presents details of the deployment and data collection process, including working with the respective IRBs, selecting and implementing the various assignments, collecting student grades and survey responses, and conducting instructor interviews, in the hopes that it will help other educators to more efficiently and effectively close the feedback loop for their own innovations.

Abstract Strategy Games are games of no chance with complete information - all players (usually two) know all there is about the current position; nothing is hidden. Examples of popular games are Tic-Tac-Toe, Chess, Checkers, Connect-4, Reversi, Mancala, Nim, Dots-and-Boxes, and Go; there are thousands more. In addition to the cultural history and remarkably beautiful mathematics locked within the strategies and game trees, we have found they form a wonderfully fertile, rich, and engaging source of activities around which to teach fundamentals of computer science. This panel will explore the ways in which we have used these games with our students, through interactive tutorials and reflection that will each surface a particular CS concept. After sharing best practices, we will invite the audience to contribute their own experiences.

Chordal graphs are a widely studied graph class, with applications in several areas of computer science, including structural learning of Bayesian networks. Many problems that are hard on general graphs become solvable on chordal graphs. The random generation of instances of chordal graphs for testing these algorithms is often required. Nevertheless, there are only few known algorithms that generate random chordal graphs, and, as far as we know, none of them generate chordal graphs uniformly at random (where each chordal graph appears with equal probability). In this paper we propose a Markov chain Monte Carlo (MCMC) method to sample connected chordal graphs uniformly at random. Additionally, we propose a Markov chain that generates connected chordal graphs with a bounded treewidth uniformly at random. Bounding the treewidth parameter (which bounds the largest clique) has direct implications on the running time of various algorithms on chordal graphs. For each of the proposed Markov chains we prove that they are ergodic and therefore converge to the uniform distribution. Finally, as initial evidence that the Markov chains have the potential to mix rapidly, we prove that the chain on graphs with bounded treewidth mixes rapidly for trees (chordal graphs with treewidth bound of one).

Computing theory is an important part of computer science education, introducing students to computational models of increasing power to study possibilities and limitations of computation. The subject is, however, very abstract and mathematical, and students often struggle with it. Students must master various computational models, but there is often a lengthy delay from the time a model is introduced until a student gets feedback on their related assignment. During this time, the course has typically moved far ahead, and students become progressively more lost. To alleviate this problem, we developed a prototype of an automated feedback tool for CS theory, which extends the widely used JFLAP software. Our tool currently handles student submissions of deterministic and non-deterministic finite automata, regular expressions, context-free grammars, and push-down automata homework, where an instructor specifies the target language and the students receive immediate feedback on their submissions. Currently, for incorrect submissions, the feedback is in the form of a "witness'' string, specifying a string on which the submission fails. Beyond regular languages, our tool attempts to solve undecidable problems; fortunately, the undecidability does not occur on typical homework assignments. We are collecting preliminary evaluation data from students using the prototype tool in their course. In our future work, we will analyze the data, and we aim to produce automated partial credit (along with the witness feedback) using SAT and QBF solvers.

We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the distribution $\mu_{M^*}$ of an unknown model $M^*$, can we efficiently determine if the two models $M$ and $M^*$ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the Ising model and proper colorings, and explore whether identity testing is any easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalakis et al. (2018) presented a polynomial-time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. Specifically, for $n$-vertex graphs of maximum degree $d$, we prove that if $|\beta| d = \omega(\log{n})$ (where $\beta$ is the inverse temperature parameter), then there is no polynomial running time identity testing algorithm unless $RP=NP$. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of #BIS, the problem of (approximately) counting independent sets in bipartite graphs.

We study the complexity of approximating the value of the independent set polynomial $Z_G(\lambda)$ of a graph $G$ with maximum degree $\Delta$ when the activity $\lambda$ is a complex number. When $\lambda$ is real, the complexity picture is well understood, and is captured by two real-valued thresholds $\lambda^*$ and $\lambda_c$, which depend on $\Delta$ and satisfy $0<\lambda^*<\lambda_c$. It is known that if $\lambda$ is a real number in the interval $(-\lambda^*,\lambda_c)$ then there is a fully polynomial time approximation scheme (FPTAS) for approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$. On the other hand, if $\lambda$ is a real number outside of the (closed) interval, then approximation is NP-hard. The key to establishing this picture was the interpretation of the thresholds $\lambda^*$ and $\lambda_c$ on the $\Delta$-regular tree. The “occupation ratio” of a $\Delta$-regular tree $T$ is the contribution to $Z_T(\lambda)$ from independent sets containing the root of the tree, divided by $Z_T(\lambda)$ itself. This occupation ratio converges to a limit, as the height of the tree grows, if and only if $\lambda\in [-\lambda^*,\lambda_c]$. Unsurprisingly, the case where $\lambda$ is complex is more challenging. It is known that there is an FPTAS when $\lambda$ is a complex number with norm at most $\lambda^*$ and also when $\lambda$ is in a small strip surrounding the real interval $[0,\lambda_c)$. However, neither of these results is believed to fully capture the truth about when approximation is possible. Peters and Regts identified the complex values of $\lambda$ for which the occupation ratio of the $\Delta$-regular tree converges. These values carve a cardioid-shaped region $\Lambda_\Delta$ in the complex plane, whose boundary includes the critical points $-\lambda^*$ and $\lambda_c$. Motivated by the picture in the real case, they asked whether $\Lambda_\Delta$ marks the true approximability threshold for general complex values $\lambda$. Our main result shows that for every $\lambda$ outside of $\Lambda_\Delta$, the problem of approximating $Z_G(\lambda)$ on graphs $G$ with maximum degree at most $\Delta$ is indeed NP-hard. In fact, when $\lambda$ is outside of $\Lambda_\Delta$ and is not a positive real number, we give the stronger result that approximating $Z_G(\lambda)$ is actually \#P-hard. Further, on the negative real axis, when $\lambda < - \lambda^*$, we show that it is \#P-hard to even decide whether $Z_G(\lambda)>0$, resolving in the affirmative a conjecture of Harvey, Srivastava, and Vondrák. Our proof techniques are based around tools from complex analysis---specifically the study of iterative multivariate rational maps.

We study the identity testing problem in the context of spin systems or undirected graphical models, where it takes the following form: given the parameter specification of the model $M$ and a sampling oracle for the distribution $\mu_{M^*}$ of an unknown model $M^*$, can we efficiently determine if the two models $M$ and $M^*$ are the same? We consider identity testing for both soft-constraint and hard-constraint systems. In particular, we prove hardness results in two prototypical cases, the \emph{Ising model} and \emph{proper colorings}, and explore whether identity testing is easier than structure learning. For the ferromagnetic (attractive) Ising model, Daskalasis et al. (2018) presented a polynomial time algorithm for identity testing. We prove hardness results in the antiferromagnetic (repulsive) setting in the same regime of parameters where structure learning is known to require a super-polynomial number of samples. Specifically, for $n$-vertex graphs of maximum degree $d$, we prove that if $|\beta| d = \omega(\log{n})$ (where $\beta$ is the inverse temperature parameter), then there is no identity testing algorithm for the antiferromagnetic Ising model that runs in polynomial time unless $RP\!=\!NP$. We also establish computational lower bounds for a broader set of parameters under the (randomized) exponential time hypothesis. In our proofs, we use random graphs as gadgets; this is inspired by similar constructions in seminal works on the hardness of approximate counting. In the hard-constraint setting, we present hardness results for identity testing for proper colorings. Our results are based on the presumed hardness of \textsc{#BIS}, the problem of (approximately) counting independent sets in bipartite graphs. In particular, we prove that identity testing for colorings is hard in the same range of parameters where structure learning is known to be hard, which in turn matches the parameter regime for NP-hardness of the corresponding decision problem.

Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of antiferromagnetic 2-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the subinstances. In this paper, we develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and we amortize against certain “bad” instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain a fully polynomial-time approximation scheme (FPTAS) even when strong spatial mixing fails. We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper bound $\Delta$ and with a lower bound $k$ on the arity of hyperedges. Liu and Lin gave an FPTAS for $k\geq2$ and $\Delta\leq5$ (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalized to $\Delta=6$). Our technique gives a tight result for $\Delta=6$, showing that there is an FPTAS for $k\geq3$ and $\Delta\leq6$. The best previously known approximation scheme for $\Delta=6$ is the Markov-chain simulation based fully polynomial-time randomized approximation scheme (FPRAS) of Bordewich, Dyer, and Karpinski, which only works for $k\geq8$. Our technique also applies for larger values of $k$, giving an FPTAS for $k\geq\Delta$. This bound is not substantially stronger than existing randomized results in the literature. Nevertheless, it gives the first deterministic approximation scheme in this regime. Moreover, unlike existing results, it leads to an FPTAS for counting dominating sets in regular graphs with sufficiently large degree. We further demonstrate that in the hypergraph independent set model, approximating the partition function is NP-hard even within the uniqueness regime. Also, approximately counting dominating sets of bounded-degree graphs (without the regularity restriction) is NP-hard.

We consider the following natural “above-guarantee” parameterization of the classical Longest Path problem: For given vertices $s$ and $t$ of a graph $G$ and integer $k$, the Longest Detour problem asks for an $(s,t)$-path in $G$ that is at least $k$ longer than a shortest $(s,t)$-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time $2^{O(k)} \cdot n^{O(1)}$. Up to the base of the exponential, this running time matches the best algorithms for finding a path of length at least $k$. Furthermore, we study the related Exact Detour problem, which asks whether a graph $G$ contains an $(s,t)$-path that is exactly $k$ longer than a shortest $(s,t)$-path. For this problem, we obtain randomized algorithms with running times $2.746^k\cdot n^{O(1)}$ (for undirected graphs) and $4^k\cdot n^{O(1)}$ (for directed graphs) and a deterministic algorithm with running time $6.745^{k}\cdot n^{O(1)}$, showing that this problem is fixed-parameter tractable as well.

We initiate the study of counting oracles for various path problems in graphs. Distance oracles have gained a lot of attention in recent years, with studies of the underlying space and time tradeoffs. For a given graph G, a distance oracle is a data structure which can be used to answer distance queries for pairs of vertices s,t in V(G). In this work, we extend the set up to answering counting queries: for a pair of vertices s,t, the oracle needs to provide the number of (shortest or all) paths from s to t. We present O(n^{1.5}) preprocessing time, O(n^{1.5}) space, and O(sqrt{n}) query time algorithms for oracles counting shortest paths in planar graphs and for counting all paths in planar directed acyclic graphs. We extend our results to other graphs which admit small balanced separators and present applications where our oracle improves the currently best known running times.

Pencil puzzles (puzzles such as sudoku and many others that are designed to be solved by humans, promoting computational thinking) provide a natural context for CS1/2 assignments. In a prior work we analyzed Likert-scaled student responses and assignment/course grades to show that not only are such assignments effective but are also largely independent of gender and prior computing experience. This paper focuses on open-ended student comments, both to see if they provide additional insights about the assignments and student perceptions not apparent from the Likert-scaled responses, and to see if these comments are consistent with the results from the prior work. We surveyed over 1000 students who had used pencil-puzzle-based assignments and invited them to make open-ended comments in their survey responses. We used grounded theory to develop codes for the large volume of student survey comments, as well as for semi-structured interviews with the instructors and focus groups with student TAs. Statistical analysis of the coded comments identified several interesting relationships, such as students being appreciative of their learning even when they perceived the assignments as difficult, which were not available from the Likert-scaled data. The analysis also confirmed that these assignments are largely gender- and experience-neutral. We conclude by discussing how these results and the coding process lead to improvements in assignment development and inform future research directions.

End-of-course evaluations and other student surveys typically include the opportunity for students to provide free-form comments. These are rich sources of data but are often only subjectively taken into account to further improve course delivery or analyze the effectiveness of assignments. We designed several puzzle-based assignments for typical CS1/2 topics and surveyed students as part of our efforts to analyze the assignments' efficacy and improve them over time. The surveys included traditional measures such as demographic data, Likert-scaled questions about assignment perceptions, and open-ended comments. With thousands of survey responses, we wanted to see if the open-ended comments yield additional, statistically significant, insights on either the assignments or students' learning. We developed a coding scheme for the comments using grounded theory analysis to represent patterns among the data. After refining the coding scheme we statistically analyzed the comments and found some interesting relationships, not apparent from the Likert-scaled questions, among certain codes. We also conducted extensive semi-structured interviews with instructors and student teaching assistants, also using grounded theory analysis to develop a set of codes for these different perspectives. The coding processes themselves allowed for a deeper understanding of the concerns about and appreciation for the assignments from both groups of participants. This poster reports on how the statistical results and the coding schemes, including the overlap and dissonance between the two coding schemes, inform our continued efforts to improve both assignment development and future research on the teaching and learning of CS concepts.

We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem Longest Detour asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k. Furthermore, we study the related problem Exact Detour that asks whether a graph G contains an (s,t)-path that is exactly k longer than a shortest (s,t)-path. For this problem, we obtain a randomized algorithm with running time about 2.746^k, and a deterministic algorithm with running time about 6.745^k, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.

The teaching of introductory computer science can benefit from the use of real-world context to ground the abstract programming concepts. We present the domain of pencil puzzles as a context for a variety of introductory CS topics. Pencil puzzles are puzzles typically found in newspapers and magazines, intended to be solved by the reader through the means of deduction, using only a pencil. A well-known example of a pencil puzzle is Sudoku, which has been widely used as a typical backtracking assignment. However, there are dozens of other well-tried and liked pencil puzzles available that naturally induce computational thinking and can be used as context for many CS topics such as arrays, loops, recursion, GUIs, inheritance and graph traversal. Our contributions in this paper are two-fold. First, we present a few pencil puzzles and map them to introductory CS concepts that the puzzles can target in an assignment, and point the reader to other puzzle repositories which provide the potential to lead to an almost limitless set of introductory CS assignments. Second, we have formally evaluated the effectiveness of such assignments used at our institution over the past three years. Students reported that they have learned the material, believe they can tackle similar problems, and have improved their coding skills. The assignments also led to a significantly higher proportion of unsolicited statements of enjoyment, as well as metacognition, when compared to a traditional assignment for the same topic. Lastly, for all but one assignment, the student's gender or prior programming experience was independent of their grade, their perceptions of and reflection on the assignment.

Problem solving is a powerful teaching methodology for computer science -- giving students a real problem to solve instead of simply discussing abstract concepts can motivate them and give them a path to better understanding. However, it is challenging to create novel example problems that are meaningful and engaging yet can be easily understood by all students. In this workshop, we will introduce participants to the vibrant world of pencil puzzles and show how many different types of puzzles can be used for a variety of topics throughout the introductory CS curriculum. Pencil puzzles are those designed to be solved by hand with pencil and paper (such as Sudoku, but including dozens of new types!) that have clear rules and are made to be solved deductively. As such, they are explicitly designed to be easy to understand and intriguing and naturally inspire algorithmic thought. We will explore a variety of on-line resources, including our own curated repository, to see how assignments throughout the introductory CS curriculum can be easily kept fresh. Participants will also experience a sample problem-solving session and collaboratively develop a new assignment for a topic of the group's choice. This workshop is intended for all teachers (late secondary and post-secondary) of introductory programming courses. Laptops are recommended.

The Model AI Assignments session seeks to gather and disseminate the best assignment designs of the Artificial Intelligence (AI) Education community. Recognizing that assignments form the core of student learning experience, we here present abstracts of five AI assignments from the 2014 session that are easily adoptable, playfully engaging, and flexible for a variety of instructor needs. Assignment specifications and supporting resources may be found at http://modelai.gettysburg.edu.

We report on a study comparing an open-ended freshman-level CS2 project with a fully specified project of similar difficulty. We employed a randomized, controlled trial methodology. The students needed to use similar data structures and algorithms, presented during lectures, for both projects.

Data centers account for a growing percentage of US power consumption. Energy efficiency is now a first-class design constraint for the data centers that support cloud services. Service providers must distribute their data efficiently across multiple data centers. This includes creation of data replicas that provide multiple copies of data for efficient access. However, selecting replicas to maximize performance while minimizing energy waste is an open problem. State of the art replica selection approaches either do not address energy, lack scalability and/or are vulnerable to crashes due to use of a centralized coordinator. Therefore, we propose, develop and evaluate a simple cost-oriented decentralized replica selection system named EDR (Energy-Aware Distributed Running system), implemented with two distributed optimization algorithms. We demonstrate experimentally the cost differences in various replica selection scenarios and show that our novel approach is as fast as the best available decentralized approach DONAR, while additionally considering dynamic energy costs. We show that an average of 12% savings on total system energy costs can be achieved by using EDR for several data intensive applications.

This workshop presents freshman-level projects based on designing and programming player strategies for well-established board games. Unlike modern computerized games, board games are typically discrete, where the game state can be stored in basic data structures, and a variety of search techniques can be used to evaluate possible player moves. Such board games provide a natural context for many introductory Computer Science topics. The strategy component makes the project open-ended, motivating the students to keep improving their code. After appropriate background information is presented, to better understand how the project works from the students' perspective, participants will act as students, brainstorm through a variety of data structures, and develop a small part of a player module.

We present three open-ended freshman projects where students design and implement their own player strategies for well-established board games: Quoridor by Mirko Marchesi (Gigamic), San Francisco Cable Cars by Dirk Henn (Queen Games), and The aMAZEing Labyrinth by Max J. Kobbert (Ravensburger). Unlike modern computer games, most board games are inherently discrete. For example, the board tends to have a fixed number of allowed positions for the game pieces and every player performs a search through a finite number of possible moves to decide which move to take next. As such, designing a player strategy for a board game provides a very natural context for basic data structures, searching algorithms, and other concepts typically covered in a freshman-level computer science sequence. Furthermore, the project allows for continual improvements to one's strategy, targeting both beginners as well as more advanced programmers.

We describe the design for a distributed game-playing environment suitable for student software development of player strategies. The framework has three main components: the game server, which runs as a RESTful web service on the Internet, the game client, which runs on the student's computer, and the graphical interface, which runs inside a web browser on the student's computer. Our earlier framework ran all components locally, and in a single programming language. The new framework supports single-user sessions, in which the student-implemented player plays against another, possibly faculty-supplied, software player, or against a human player. It also supports multi-user sessions, in which student players on two or more separate computers can play against each other in a single game. Supported by the NSF, award ID 1044721.

With the increasing energy cost in data centers, an energy efficient approach to provide data intensive services in the cloud is highly in demand. This paper solves the energy cost reduction problem of data centers by formulating an energy-aware replica selection problem in order to guide the distribution of workload among data centers. The current popular centralized replica selection approaches address such problem but they lack scalability and are vulnerable to a crash of the central coordinator. Also, they do not take total data center energy cost as the primary optimization target. We propose a simple decentralized replica selection system implemented with two distributed optimization algorithms (consensus-based distributed projected subgradient method and Lagrangian dual decomposition method) to work with clients as a decentralized coordinator. We also compare our energy-aware replica selection approach with the replica selection where a round-robin algorithm is implemented. A prototype of the decentralized replica selection system is designed and developed to collect energy consumption information of data centers. The results show that the total energy cost can be effectively reduced by using our decentralized replica selection system comparing with a round-robin method. It also has low calculation and communication overhead and can be easily adapted to the real world cloud environment.

Board games provide a natural context for the use of basic data structures and search algorithms taught in a typical introductory CS sequence. Unlike traditionally used programming assignments where students implement the actual game, we provide the game "engine" and ask the students to implement player strategies. The engine graphically displays the current state of the game and cyclically calls the individual player strategies to perform their moves. The students need to apply the same algorithms as if programming the rule checker for the game. And with the added strategy component, the project becomes open-ended, leaving space for continued improvements and experimentation. The poster describes the game we used last academic year, Quoridor by Mirko Marchesi and published by Gigamic Games. The goal of this game for two or four players is to move a piece from one side of a 9x9 grid board to another side, while placing walls that lengthen the opponents' paths to their destinations. The poster discusses Quoridor's relevance for basic data structures and algorithms, for example, breadth-first search. It then elaborates on the possibilities introduced by adding strategies into the picture, including an end-of-term tournament. Supported by the NSF, award ID 1044721.

We present an improved “cooling schedule” for simulated annealing algorithms for combinatorial counting problems. Under our new schedule the rate of cooling accelerates as the temperature decreases. Thus, fewer intermediate temperatures are needed as the simulated annealing algorithm moves from the high temperature (easy region) to the low temperature (difficult region). We present applications of our technique to colorings and the permanent (perfect matchings of bipartite graphs). Moreover, for the permanent, we improve the analysis of the Markov chain underlying the simulated annealing algorithm. This improved analysis, combined with the faster cooling schedule, results in an $O(n^7\log^4{n})$ time algorithm for approximating the permanent of a $0/1$ matrix.

In recent years, there has been a proliferation of theoretical graph models, e.g., preferential attachment and small-world models, motivated by real-world graphs such as the Internet topology. To address the natural question of which model is best for a particular data set, we propose a model selection criterion for graph models. Since each model is in fact a probability distribution over graphs, we suggest using Maximum Likelihood to compare graph models and select their parameters. Interestingly, for the case of graph models, computing likelihoods is a difficult algorithmic task. However, we design and implement MCMC algorithms for computing the maximum likelihood for four popular models: a power-law random graph model, a preferential attachment model, a small-world model, and a uniform random graph model. We hope that this novel use of ML will objectify comparisons between graph models.