We usually teach our children not to be greedy. Many of the ethical principles ingrained in cultures worldwide emphasize the importance of one’s place in a larger community. However, there is need for some greed to prevent needless self-sacrifice. We explore this balancing act between caring for the broader community and caring for one’s own needs and desires through the lens of artificial decisionmaking agents. Using our modern reimplementation of the societal simulation Sugarscape, we explore the outcomes of societies where the agents employ varying amounts of greed. We show that entirely selfless and entirely selfish societies are doomed to collapse in most instances. We also show that societies that are 10% to 80% greedy have high wellbeing across a variety of commonsense metrics. These results highlight the exciting promise of developing computationally-derived guidelines for ethical behavior for individual agents which correspond to significant societal impacts.

Code tracing (or program sketching) is a useful technique for both students and professionals to understand syntactic and semantic details of code. Emphasizing and exploring this skill leads students to a deep understanding of their code in the short term and ultimately, their evolution into competent programmers in the future. In this paper, we provide evidence that a careful incorporation of the concept of scoping into code tracing techniques is fundamental to achieving this successful student transition. To this end, we present a formalized pencil-and-paper code tracing strategy for CS1 called Visualized Scope Tracing (VST), with scoping as a key underlying theme that elegantly addresses code blocks, function stacks, recursive structures, pass-by-reference, arrays, pointers, and parallel code.

Current data structures for searching large string collections either fail to achieve minimum space or cause too many cache misses. In this paper we discuss some edge linearizations of the classic trie data structure that are simultaneously cache-friendly and compressed. We provide new insights on front coding [24], introduce other novel linearizations, and study how close their space occupancy is to the information-theoretic minimum. The moral is that they are not just heuristics. Our second contribution is a novel dictionary encoding scheme that builds upon such linearizations and achieves nearly optimal space, offers competitive I/O-search time, and is also conscious of the query distribution. Finally, we combine those data structures with cache-oblivious tries [2, 5] and obtain a succinct variant whose space is close to the information-theoretic minimum.

We propose measures for compressed data structures, in which space usage is measured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data, where the task is to construct a data structure to represent a set S of n items out of a universe U = {0,..., u $1} and support various queries on S. We use a well-known data-aware measure for set data called gap to bound the space of our data structures. We describe a novel dictionary structure taking gap+O(n log(u/n)/ log n)+O(n log log(u/n)) bits. Under the RAM model, our dictionary supports membership, rank, select, and predecessor queries in nearly optimal time, matching the time bound of Andersson and Thorup's predecessor structure (2000), while simultaneously improving upon their space usage. Our dictionary structure uses exactly gap bits in the leading term (i.e., the constant factor is 1) and answers queries in near-optimal time. When seen from the worst case perspective, we present the first O(n log(u/n))-bit dictionary structure which supports these queries in near-optimal time under RAM model. We also build a dictionary which requires the same space and supports membership, select, and partial rank queries even more quickly in O(loglogn) time. To the best of our knowledge, this is the first of a kind result which achieves data-aware space usage and retains near-optimal time.

We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previous work and represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20% of the original text size---without requiring a separate instance of the text. We can additionally use a simple notion to encode and decode block-sorting transforms (such as the Burrows--Wheeler transform), achieving a compression ratio comparable to that of bzip2. We also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.

We report on a simple encoding format called wzip for decompressing block-sorting transforms, such as the Burrows-Wheeler transform (BWT). Our compressor uses the simple notions of gamma encoding and RLE, organized with a wavelet tree, to achieve a slightly better compression ratio than bzip2 in less time. In fact, our compression/decompression time is dependent on H/sub h/, the hth order empirical entropy. This relationship of performance to the compressibility of data is a key new idea among compression algorithms. Another key contribution of our compressor is its simplicity. Our compressor can also operate as a full-text index with a small amount of data, while still preserving backward compatibility with just the compressor.