The problem of online checkpointing is a classical problem with numerous applications that has been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. Bringmann, Doerr, Neumann, and Sliacan studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k and smaller than ln 4-o(1)≈ 1.39 for the sparse subset of k ’s, which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k . In this article, we solve the main problems left open in the above-mentioned paper by proving that ln 4 is a tight upper and lower bound on the asymptotic discrepancy for all large k and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k ≤ 10. In the last part of the article, we describe some new applications of this online checkpointing problem.

The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this problem, a user has to maintain k memorized checkpoints during a long computation, where the only allowed operation is to move one of the checkpoints from its old time to the current time, and his goal is to keep the checkpoints as evenly spread out as possible at all times. At ICALP'13 Bringmann et al. studied this problem as a special case of an online/offline optimization problem in which the deviation from uniformity is measured by the natural discrepancy metric of the worst case ratio between real and ideal segment lengths. They showed this discrepancy is smaller than 1.59-o(1) for all k, and smaller than ln4-o(1)~~1.39 for the sparse subset of k's which are powers of 2. In addition, they obtained upper bounds on the achievable discrepancy for some small values of k. In this paper we solve the main problems left open in the ICALP'13 paper by proving that ln4 is a tight upper and lower bound on the asymptotic discrepancy for all large k, and by providing tight upper and lower bounds (in the form of provably optimal checkpointing algorithms, some of which are in fact better than those of Bringmann et al.) for all the small values of k <= 10.

We study novel variations of Voronoi games and associated random processes that we call Voronoi choice games. These games provide a rich framework for studying questions regarding the power of small numbers of choices in multi-player, competitive scenarios, and they further lead to many interesting, non-trivial random processes that appear worthy of study. As an example of the type of problem we study, suppose a group of n miners (or players) are staking land claims through the following process: each miner has m associated points independently and uniformly distributed on an underlying space (such as the unit circle, the unit square, or the unit torus), so the kth miner will have associated points p_{k1}, p_{k2}, ..., p_{km}. We generally here think of m as being a small constant, such as 2. Each miner chooses one of these points as the base point for their claim. Each miner obtains mining rights for the area of the square that is closest to their chosen base; that is, they obtain the Voronoi cell corresponding to their chosen point in the Voronoi diagram of the n chosen points. Each player's goal is simply to maximize the amount of land under their control. What can we say about the players’ strategy and the equilibria of such games? In our main result, we derive bounds on the expected number of pure Nash equilibria for a variation of the 1-dimensional game on the circle where a player owns the arc starting from their point and moving clockwise to the next point. This result uses interesting properties of random arc lengths on circles, and demonstrates the challenges in analyzing these kinds of problems. We also provide several other related results. In particular, for the 1-dimensional game on the circle, we show that a pure Nash equilibrium always exists when each player owns the part of the circle nearest to their point, but it is NP-hard to determine whether a pure Nash equilibrium exists in the variant when each player owns the arc starting from their point clockwise to the next point. This last result, in part, motivates our examination of the random setting.

We describe the curriculum, initial experience, and preliminary evaluation of an introductory CS course for students taking CS as their single or double major. The course is taught during the first or second semester of the first year of studies. It is centered around eleven to thirteen topics, offering a wide cover of major CS subjects. Many of these topics are not covered in "traditional" introductory CS courses, and some of them are not even covered through the standard undergraduate curricula. Examples: digital image representation and processing, error correction and detection codes, hashing (including Cuckoo hashing), and text compression.

Moran, Naor, and Segev have asked what is the minimal r=r(n, k) for which there exists an (n,k)-monotone encoding of length r, i.e., a monotone injective function from subsets of size up to k of {1, 2,..., n} to r bits. Monotone encodings are relevant to the study of tamper-proof data structures and arise also in the design of broadcast schemes in certain communication networks. To answer this question, we develop a relaxation of k-superimposed families, which we call alpha-fraction k -multiuser tracing ((k, alpha)-FUT (fraction user-tracing) families). We show that r(n, k) = Theta(k log(n/k)) by proving tight asymptotic lower and upper bounds on the size of (k, alpha)-FUT families and by constructing an (n,k)-monotone encoding of length O(k log(n/k)). We also present an explicit construction of an (n, 2)-monotone encoding of length 2 log n+O(1), which is optimal up to an additive constant.