Websheets is an online exercise system providing rigorous "fill-in-the-blank" programming exercises. It allows an instructor to quickly create exercises by writing a correct reference solution and indicating the parts to be blanked out. It is open-source and has been used successfully in Java and C++ by a half-dozen instructors and over 1000 students.

A coloring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each color; the polychromatic number is the maximum number of colors in such a coloring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded Vapnik--Chervonenkis (VC)-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.

In this paper we prove new properties of hypergraphic linear programming relaxations for the Steiner tree problem. In particular, we show that a partition-based relaxation has the same value as other relaxations based on subtours and directed cuts. Additionally, we establish structural properties of basic solutions by using uncrossing methods. For quasi-bipartite instances we show that these hypergraphic relaxations have the same value as the well-studied graphic bidirected cut relaxation. We show how to analyze several approximation algorithms relative to the hypergraphic linear programs; one gives an approximation ratio and integrality gap of at most $\sqrt{3} \simeq 1.729$ for the Steiner tree problem when the full components arrive online.

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph ( V , E ), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space identifies the cuts of a graph. This leads to simple new linear-time sequential algorithms for finding all cut edges and cut pairs (a set of 2 edges that form a cut) of a graph. In the model of distributed computing in a graph G = ( V , E ) with O (log | V |)-bit messages, our approach yields faster algorithms for several problems. The diameter of G is denoted by D , and the maximum degree by Δ. We obtain simple O ( D )-time distributed algorithms to find all cut edges, 2-edge-connected components, and cut pairs, matching or improving upon previous time bounds. Under natural conditions these new algorithms are universally optimal—that is, a Ω( D )-time lower bound holds on every graph. We obtain a O ( D +Δ/log |V|)-time distributed algorithm for finding cut vertices; this is faster than the best previous algorithm when Δ, D = O (√| V |). A simple extension of our work yields the first distributed algorithm with sub-linear time for 3-edge-connected components. The basic distributed algorithms are Monte Carlo, but they can be made Las Vegas without increasing the asymptotic complexity. In the model of parallel computing on the EREW PRAM, our approach yields a simple algorithm with optimal time complexity O (log V ) for finding cut pairs and 3-edge-connected components.

We introduce a simple new model of distributed computation -- finite-state symmetric graph automata (FSSGA) -- which captures the qualitative properties common to fault-tolerant distributed algorithms. Roughly speaking, the computation evolves homogeneously in the entire network, with each node acting symmetrically and with limited resources. As a building block, we demonstrate the equivalence of two automaton models for computing symmetric multi-input functions. We give FSSGA algorithms for several well-known problems.