Over the last ten years, our department's breadth-first introductory course has evolved independently of other survey courses in computer science. Due to its success, we duplicated the ideas into our course for non-majors, and this has also proven successful. None of the published resources match our vision for these courses, and so the department has developed its own. In this paper, we describe the design of the majors course, and we introduce a variety of resources developed for both courses. These resources, which could be useful in many other courses also, are freely available through the Web.

Logisim enables students in introductory courses to design and simulate logic circuits. The program's design emphasizes simplicity of use, with a secondary goal of enabling design of sophisticated circuits. This motivates a two-tiered system, where users can move to the second tier by selecting a menu option.Users draw circuits of logic gates using the toolbox model popular in drawing programs. The circuit automatically propagates circuit values through the circuit; by selecting the appropriate tool, users can toggle switches to see how the circuit behaves in other situations. In the advanced tier, the user can treat circuits as black boxes within larger circuits, enabling the simulation of hierarchical designs. The author has successfully drawn and tested a simple 8 bit CPU using the program.The program has proven useful in a variety of introductory courses, from a nonmajors survey course to a sophomore-level systems course. Students find Logisim simple to follow, and find the laboratories designed around it useful in reinforcing the circuit concepts from class.In this article, we identify and compare a variety of systems similar to Logisim, we explore Logisim's features in detail, and we examine its use in class assignments.

We construct an online algorithm for paging that achieves an O(r+log k) competitive ratio when compared to an offline strategy that is allowed the additional ability to "rent" pages at a cost of 1/r. In contrast, the competitive ratio of the Marking algorithm for this scenario is O(r log k). Our algorithm can be thought of in the standard setting as having a "fine-grained" competitive ratio, achieving an O(1) ratio when the request sequence consists of a small number of working sets, gracefully decaying to O(log k) as this number increases. Our result is a generalization of the result by Y. Bartal et al. (1997) that one can achieve an O(r+log n) ratio for the unfair n-state uniform-space Metrical Task System problem. That result was a key component of the polylog(n) competitive randomized algorithm given in that paper for the general Metrical Task System problem. One motivation of this work is that it may be a first step toward achieving a polylog(k) randomized competitive ratio for the much more difficult k-server problem.

We consider the problem of learning monotone Boolean functions over {0, 1}/sup n/ under the uniform distribution. Specifically, given a polynomial number of uniform random samples for an unknown monotone Boolean function f, and given polynomial completing time, we would like to approximate f as well as possible. We describe a simple algorithm that we prove achieves error at most 1/2-/spl Omega/(1//spl radic/n), improving on the previous best bound of 1/2-/spl Omega/((log/sup 2/ n)/n). We also prove that no algorithm, given a polynomial number of samples, can guarantee error 1/2-/spl omega/((log n)//spl radic/n), improving on the previous best hardness bound of O(1//spl radic/n). These lower bounds hold even if the learning algorithm is allowed membership queries. Thus this paper settles to an O(log n) factor the question of the best achievable error for learning the class of monotone Boolean functions with respect to the uniform distribution.

We relate two problems that have been explored in two distinct communities.The first is the problem of combining expert advice, studied extensively in the computational learning theory literature, and in particular the problem of tracking the best expert in the clean "decision-theoretic" setting.The second is the Metrical Task System (MTS) problem, studied extensively in the On-line Algorithms literature, and in particular, variations on the setting of the uniform metric space.We show that these problems contain several interesting similarities and demonstrate how algorithms designed for each can be used to achieve good bounds and new approaches for solving the other. Specific contributions of this paper include:An analysis showing how two recent algorithms for the MTS problem can be applied to the setting of tracking the best expert, providing good bounds with an approach of a much different flavor than the well-known multiplicative weighted-expert algorithms.A version of Herbster and Warmuth's weightsharing algorithm for tracking the best expert that works in the decision-theoretic setting, and an application of this to the Metrical Task System problem.A new simpler algorithm for tracking experts, which does not carry over to the MTS problem.Finally, we present an experimental comparison of how these algorithms perform on a process migration problem.

While many dynamic branch prediction schemes have been proposed and studied, few have been compared to static branch prediction. Fewer yet have been implemented side-by-side on the same machine to allow full performance evaluation. The Hewlett-Packard PA-8000 microprocessor implements both a simple dynamic prediction scheme and static prediction, selectable by the application programmer. This paper studies the PA-8000's trade-off between static and dynamic prediction, and the compiler optimizations needed to support an innovative static branch prediction convention while maintaining object code compatibility with earlier revisions of the PA-RISC architecture.

We present a randomized on-line algorithm for the Metrical Tti System problem that achieves a competitive ratio of O(log6 n) for arbitrary metric spaces, against art oblivious adversary.This is the first algorithm to achieve a sublinear competitive ratio for all mernc spaces.Our algorithm uses a recent result of Bart.al[Bar96] thatan arbitrarymetric space can be probabilistically approximated by a set of metric spaces called "k-hierarchical well-separated trees" (k-HST'S).Indeed, the main technical result of this paper is an 0(}og2 n)-competitive algorithm for fl(log2 n)-HST spaces.This, combined with the result of [Bar96], yields the general bound.Note that for the k-server problem on metric spaces of k + c points our result implies a competitive ratio of O(C6 log6 k).