Despite their power and simplicity, randomized algorithms are often under-emphasized in the classroom (and as a consequence, ultimately in practice) since they can be more challenging to analyze than their deterministic counterparts. In this paper, we describe a simplified framework that streamlines the analysis of dozens of common randomized algorithms and data structures. The key component of this framework, which we call the randomized reduction lemma, builds on intuition that is already commonly held by most students based on their experience with deterministic algorithms, and reduces the necessary prerequisites one must know from probability theory to a minimal subset. For example, one can prove that randomized quicksort runs in O(n log n) time with high probability in two paragraphs, without knowledge of random variables or Chernoff bounds. This paper is intended to be self-contained and written in a sufficiently student-friendly fashion so that it may serve as a classroom handout.

This paper describes a novel intelligent tutoring system called beSocratic, which targets question types that allow students to respond with free-form input but are able to be automatically evaluated and analyzed. Using beSocratic's GraphPad module, students are able to draw data structures using a mouse, touch, or a stylus. Once a student has completed a question, their final answer and a replay of their actions is uploaded to beSocratic's database. This allows teachers to replay student answers and identify common mistakes. In addition, beSocratic contains a set of post-analysis tools that utilize hidden Markov modeling to cluster student submissions with similar sequences of actions. Along with the modeling, beSocratic generates several visualizations to help teachers interpret the results. This can potentially help teachers identify students who are using the same strategies to answer questions. We have begun pilot-testing its use in computer science classrooms to teach student to properly construct splay trees. The splay tree activity teaches students to construct data structures using free-form drawing and the rotations needed for the splay operation. The activity concludes with an extended example where students must construct a splay tree from scratch. At each step, GraphPad evaluates how the students are performing and provides feedback. Students responded positively to the initial pilot study and we believe this warrants further investigation. beSocratic is free to use at beSocratic.clemson.edu.

Data structures are one of the fundamental concepts that all computer scientist students must learn if they are to succeed in their careers. Therefore, it is important to develop and assess questions targeted at improving the teaching of data structures. Unfortunately, research suggests that multiple choice or matching questions cannot be used to properly assess deep knowledge on a subject [1,2,3,4]. Students can often guess their way to the correct answer. We believe that students must construct these structures instead of simply identifying them. However, analyzing many hand-drawn data structures is time-consuming for large class sizes. This poster describes a web-based software tool, BeSocratic, designed to facilitate interactivity in a data structures course. BeSocratic allows students to build data structures intuitively using a combination of handwriting recognition and gestures. Using BeSocratic, instructors can create intelligent tutors that teach students to construct various data structures. These tutors are able to identify problems and provide multi-tiered feedback to students. Furthermore, BeSocratic records each action a student makes, so it may be replayed and visualized to gain deeper insights into how students construct data structures and complete algorithms. We have created and pilot-tested a BeSocratic activity, which teaches students how to construct splay trees.

The use of mobile app development in pre-college computing education is rapidly gaining momentum due to the increasingly widespread use of mobile devices. To fully realize the learning potential of this technology in the classroom, however, one may need to re-examine traditional curricular approaches originating from desktop computing environments. In this work, we describe our experience with a new high-school computing camp designed from the ground up to engage students by taking full advantage of the specific benefits of mobile devices, such as built-in cameras, GPS, networking, and sensors measuring touch, sound, acceleration, and orientation. We describe the design of our camp including materials and examples used. We assess the effectiveness of this instructional approach by demonstrating a statistically significant increase in interest in future computing endeavors. We also comment on the use of MIT App Inventor to ease the transition, particularly for novice programmers, to more sophisticated Java-based apps.

In this paper, we address the problem of localizing faults by analyzing execution traces of successful and unsuccessful invocations of the application when run against a suite of tests. We present a new algorithm, based on a linear programming model, which is designed to be particularly effective for the case where multiple faults are present in the application under investigation. Through an extensive empirical study, we show that in the case of both single and multiple faults, our approach outperforms a host of prominent fault localization methods from the literature.

Abstract The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power p at vertex v is capable of dominating (broadcasting to) all vertices within distance p from v. Our goal is to assign a broadcast power f(v) to every vertex v in a graph such that ΣvεVf(v) is minimized, and such that every vertex u with f(u) = 0 is within distance f(v) of some vertex v with f(v)> 0. The problem is solvable in polynomial time on a general graph (Heggernes and Lokshtanov, Disc Math (2006), 3267–3280) and Blair et al. (Congr. Num. (2004), 55–77.) gave an O(n2) algorithm for trees. In this article, we provide an O(n) algorithm for trees. Our algorithm is notable due to the fact that it makes decisions for each vertex v based on “nonlocal” information from vertices far away from v, whereas almost all other linear‐time algorithms for trees only make use of local information. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

We consider a stochastic variant of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution "policy" that maximizes the expected value of items placed in the knapsack, and we consider both non-adaptive policies (that designate a priori a fixed sequence of items to insert) and adaptive policies (that can make dynamic choices based on the instantiated sizes of items placed in the knapsack thus far). We show that adaptivity provides only a constant-factor improvement by demonstrating a greedy non-adaptive algorithm that approximates the optimal adaptive policy within a factor of 7. We also design an adaptive polynomial-time algorithm which approximates the optimal adaptive policy within a factor of 5 + /spl epsiv/, for any constant /spl epsiv/ > 0.

Abstract We study the problem of computing minimum‐cost paths through a time‐varying network, in which the travel time and travel cost of each arc are known functions of one's departure time along the arc. For some problem instances, the ability to wait at nodes may allow for less costly paths through the network. When waiting is allowed, it is constrained by a (potentially time‐varying) waiting policy that describes the length of time one may wait and the cost of waiting at every node. In discrete time, time‐dependent shortest path problems with waiting constraints can be optimally solved by straightforward dynamic programming algorithms; however, for some waiting policies these algorithms can be computationally impractical. In this article, we survey several broad classes of waiting policies and show how techniques for speeding up dynamic programming can be effectively applied to obtain practical algorithms for these different problem variants. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 41–46 2004