We created an Eclipse plug-in called FrenchPress that offers students feedback on their Java programming style. It is designed not for novices but for students taking their second or third Java course. Advanced beginner students know enough to produce a program with the desired input/output behavior, but fail to understand it could still be poorly written. Large class sizes in introductory courses make it difficult for instructors to give their students individualized attention. FrenchPress automates a small subset of the feedback students might have received from educators. The system diagnoses issues characteristic of programmers who have not yet assimilated the object-oriented paradigm, such as misuse of the public modifier, fields that should have been local variables, and instance variables that should have been class constants. We conducted a classroom trial of the plug-in covering four assignments in data structures and algorithms. Among students whose code triggered one or more diagnostic rules, the percentage who modified their program in response to FrenchPress feedback varied from a high of 59% on the first project to a low of 23% on the second and fourth projects. On the user surveys following each assignment, 56-66% of respondents said they were satisfied with FrenchPress performance.

Routing optimization is used to find a set of routes that minimizes cost (delay, utilization). Previous work has addressed this problem for the case of a known, static end-to-end traffic matrix. In the Internet, it is difficult to accurately estimate a traffic matrix, and the constantly changing nature of Internet traffic makes it costly to maintain optimal routing by responding to traffic changes. Thus, it is of interest to maintain a set of routes that are "good" for a number of different possible traffic scenarios. In this paper, we explore ways to find an optimal set of routes with multiple traffic matrices to minimize expected cost. We focus on two general approaches, source-destination routing and destination routing. In the case of source-destination routing, we extend existing methods with a single traffic matrix to solve the optimization problem with multiple traffic matrices: we extend the convex optimization solution methods for a single traffic matrix to the multiple traffic matrix case; we also extend the gradient-based solution methods for a single traffic matrix to the multiple traffic matrix case. However, the multiple traffic matrix case requires many more control variables. In the case of destination routing, we encounter many more differences from the single traffic matrix case. The loop-free property, which is valid for the single traffic matrix case, is no longer valid for the multiple traffic matrix case, and it is difficult to extend existing methods for a single traffic matrix to solve the optimization problem with multiple traffic matrices. We show that it is NP-complete even to determine the feasibility of multiple traffic matrices. We thus propose and evaluate a heuristic algorithm for this case.

We present examples of hard tautologies in propositional calculus by encoding instances of the assertions made by Ramsey's theorem. We provide evidence that these tautologies are indeed hard by 1. showing that there are no short proofs for these tautologies in certain restricted classes of proof systems; 2. relating a proof of these tautologies to the problem of determining the diagonal Ramsey numbers for graphs.

Let be the set of recursive functions computable by machines using at most t(x) computation steps on argument x, for all but finitely many inputs x. We call t a name for the complexity class . Suppose we allow our machines to run longer, say h(x, t(x)) steps on argument x, where h is some fixed recursive function. One might expect that, for large enough h, permitting our machines to run longer by an amount h will always allow us to compute new functions, i.e., is a proper subset of . This turns out not to be the case: The “gap theorem” ([2], [3]) implies that for every recursive h there exists a recursive t such that . However, if we restrict our attention to names from a certain subclass of the recursive functions, then we can indeed uniformly increase the size of our -classes. Informally, we call a recursive function t “honest” if some machine computes t(x) in roughly t(x) steps for each argument x. (A precise definition is given in Definition 1 below.) Then according to the “compression theorem” [1], there exists a single recursive function h such that, for every honest t, is a proper subset of . Thus the phenomenon of the gap theorem is avoided by restricting attention to honest functions. It is a surprising consequence of the “honesty theorem” of McCreight and Meyer ([4], [5]) that there is no loss of generality in this restriction. Namely, for any recursive function t there is an honest recursive function t′ such that .