A simple game is a cooperative game where some coalitions among players or voters became the (monotonic) set of winning coalitions, and the other ones form the set of losing coalitions. It is well-known that weighted voting games form a strict subclass of simple games, where each player has a voting weight so that a coalition wins if and only if the sum of weights of their members exceeds a given quota, otherwise it loses. This work studies how far away a simple game is for being representable as a weighted voting game, which allows for a more compact representation. There are several measures that determine the weightedness of a simple game, such as the dimension, the trade-robustness, the critical threshold value associated with the α -roughly weightedness property, etc. In this work we propose some new weightedness measures, all based on linear programming. In general terms, for a given simple game, a linear program is used to identify its weightedness: (i) the ϵ -roughly value ( μ ϵ ), (ii) the Z + -roughly value ( μ Z + ), (iii) the Δ-roughly value ( μ Δ ), and (iv) the outlier value ( Ψ M ). We show a close relation between the known critical threshold value of weightedness and the new measure μ Δ . Finally, we also present an exhaustive comparison of weightedness measures for simple games with up to six players. • We define new weightedness measures for simple games from inequality systems. • We introduce a new weightedness measure for simple games based on outlier coalitions. • This manuscript provides a comparison of the known α -roughly value with other new weightedness values. • We exhaustively compute some weightedness measures for all simple games up to 7 players.

The verdicts of most online programming judges are, essentially, binary: the submitted codes are either “good enough” or not. Whilst this policy is appropriate for competitive or recruitment platforms, it can hinder the adoption of online judges on educative settings, where it could be adequate to provide better feedback to a student (or instructor) that has submitted a wrong code. An obvious option would be to just show him or her an instance where the code fails. However, that particular instance could be not very significant, and so could induce unreflectively patching the code. The approach considered in this paper is to data mine all the past incorrect submissions by all the users of the judge, so to extract a small subset of private test cases that may be relevant to most future users. Our solution is based on parsing the test files, building a bipartite graph, and solving a Set Cover problem by means of Integer Linear Programming. We have tested our solution with a hundred problems in Jutge.org. Those experiments suggest that our approach is general, efficient, and provides high quality results.

Jutge.org is an open access educational online programming judge where students can try to solve more than 800 problems using 22 programming languages. The verdict of their solutions is computed using exhaustive test sets run under time, memory and security restrictions. By contrast to many popular online judges, Jutge.org is designed for students and instructors: On one hand, the problem repository is mainly aimed to beginners, with a clear organization and gradding. On the other hand, the system is designed as a virtual learning environment where instructors can administer their own courses, manage their roster of students and tutors, add problems, attach documents, create lists of problems, assignments, contests and exams. This paper presents Jutge.org and offers some case studies of courses using it.

This paper presents new theorems to analyze divide-and-conquer recurrences, which improve other similar ones in several aspects. In particular, these theorems provide more information, free us almost completely from technicalities like floors and ceilings, and cover a wider set of toll functions and weight distributions, stochastic recurrences included.

It is well known that the performance of quicksort can be improved by selecting the median of a sample of elements as the pivot of each partitioning stage. For large samples the partitions are better, but the amount of additional comparisons and exchanges to find the median of the sample also increases. We show in this paper that the optimal sample size to minimize the average total cost of quicksort, as a function of the size n of the current subarray size, is $a\cdot \sqrt{n} + o(\sqrt{n}\,)$. We give a closed expression for a, which depends on the selection algorithm and the costs of elementary comparisons and exchanges. Moreover, we show that selecting the medians of the samples as pivots is not the best strategy when exchanges are much more expensive than comparisons. We also apply the same ideas and techniques to the analysis of quickselect and get similar results.

In this paper, we present randomized algorithms over binary search trees such that: (a) the insertion of a set of keys, in any fixed order, into an initially empty tree always produces a random binary search tree; (b) the deletion of any key from a random binary search tree results in a random binary search tree; (c) the random choices made by the algorithms are based upon the sizes of the subtrees of the tree; this implies that we can support accesses by rank without additional storage requirements or modification of the data structures; and (d) the cost of any elementary operation, measured as the number of visited nodes, is the same as the expected cost of its standard deterministic counterpart; hence, all search and update operations have guaranteed expected cost O(log n ), but now irrespective of any assumption on the input distribution.