Early exposure to ethical reasoning and diversity, equity, and inclusion (DEI) concepts is critical for preparing socially responsible computer scientists. To support this goal, we designed and implemented a required non-programming first-year undergraduate computer science course that is taken concurrently with an introductory programming course. This discussion-based course integrates DEI and ethics as foundational themes. The new course adopts a breadth-first structure delivered over a 10-week quarter, with 5 of the 18 sessions focused on DEI and ethics. Over three consecutive academic years, we collected pre- and post-course survey data from 451 students enrolled in the new course. Results show an %statistically significant increase in student's recognition of the importance of DEI and ethics and a substantial increase in understanding how these dimensions intersect with technical practice. In this experience report, we describe the course design, instructional methods, and survey instruments; present key findings; and reflect on lessons learned. This work contributes a model for embedding DEI and ethics into the early undergraduate computing curriculum.

Increasing gender inclusion in computer science programs is an important step in addressing the systemic biases in our discipline. We present the results of using Interactive Theatre Scenarios as an intervention to help students engage in critical thinking about gender bias issues. The scenarios are run by a professional theater group who presents a scenario displaying gender bias on a first iteration, then discusses the scenario with students, and an additional iterations allows students to participate as protagonists to alter the outcome. Using surveys after the scenarios, the results suggest the use of interactive theater intervention to be successful, with most of the students believing the scenarios helped them be cognizant that they need to be aware of and address bias issues in computer science.

The goal of the Partnership For Equity project is to build inclusive computing and engineering professional mindsets, which describes attitudes and identities of students who value knowledge in both technical and diversity, equity, and inclusion (DEI) areas of computer science. In this paper we present results from an intervention we piloted in a text mining special topics class. This intervention is directly applicable to any data mining class. Students applied naive Bayes classification to a survey result dataset and classified responses as "technical" or "equity", where technical meant the survey question response was focused on technical issues, whereas "equity" meant the response was focused on DEI issues. The survey data came from another course where students watched Ms. Joy Buolamwini's 2016 "How I'm fighting bias in algorithms" TedX talk and then answered several survey questions about the talk. In our text mining course students were first asked to watch the same TedX talk and answer several of the same survey questions. Their answers were added to the original data set. Students were then asked to apply naive Bayes classification to the combined survey results for one question. At the end of the course students took an end of class survey and answered more open-ended questions about whether the assignment influenced their thinking about DEI in computing. Results from this intervention indicate that including a DEI focus in technical programming assignments can positively impact students' views on the importance of DEI and contribute to the development of computing and engineering professional mindsets.

As the computing education community grapples with integrating computing into K-12 curriculum, the focus remains primarily on identifying appropriate grade level content and skills[3]. Two problems articulated by Margolis et al.[5], are (1) how to bring computing into an already over-burdened curriculum, (2) how to provide substantive professional development for teachers. We need to look beyond teaching computing concepts as isolated from other disciplines. The power of computing lies in its broad applicability to facilitate creativity in other domains. The panelists will report on using Scratch (http://scratch.mit.edu) in language arts, science and social studies curricula. Our programs demonstrate to middle and high school students and teachers how computational thinking, computing concepts and programming are essential to their course of study. We emphasize active learning where computing is a tool for creativity. We demonstrate how learning 21st century computing skills in the classroom can be fun. This panel will present three perspectives on using Scratch for humane games, scientific modeling and interactive storytelling. There will be significant time for the audience to participate in discussion of broad applicability of our approaches and whether this pedagogy can work at the undergraduate level.

In this paper we describe a two-week residential summer game camp for rising 9th and 10th grade students and a four-week high school teacher professional development course. We present survey results that indicate our approach results in increased computer programming knowledge and self-confidence for both students and teachers. Our project aims to use a holistic game creation approach to increase student interest in computer science by directly teaching to students in a summer camp, instructing the teachers during a 4-week professional development course, and finally by supporting teachers as they use our curriculum in their high schools.

No abstract available.

In this special session we present arguments for and against a game-centric computing curriculum. To highlight the issues and ensure equal time for arguments on either side, our session is staged as a debate with three speakers on each side. Our audience is educators and educational researchers interested in the role of game development in the CS curriculum.

Many Geographic Information Systems (GIS) handle large geospatial datasets stored in raster representation. Spatial joins over raster data are important queries in GIS for data analysis and decision support. However, evaluating spatial joins can be very time intensive due to the size of these datasets. In this paper we propose a new interactive framework that allows users to get approximate answers in near instantaneous time, thus allowing for truly interactive data exploration. Our method utilizes two proposed statistical approaches: probabilistic join and sampling based join. Our probabilistic join method provides speedup of two orders of magnitude with no correctness guarantee, while our sampling based method provides an order of magnitude improvement over the full quad-tree join and also provides running confidence intervals. We propose a framework that combines the two approaches to allow end users to tradeoff speed versus bounded accuracy. The two approaches are evaluated empirically with real and synthetic datasets.

In this paper we argue for using a "Game First" approach to teaching introductory programming. We believe that concerns over whether an OO approach or a procedural approach should be used first are secondary to the course assignment and example content. If examples are not compelling, student interest often lags thus making the OO versus procedural argument moot. We believe that game programming motivates most new programmers. Compelling assignments mean that students are far more likely to learn because they are interested, and the visual component allows students to see mistakes in their code as manifested in the resultant graphics. We describe our experiences after redesigning and offering a new introductory computer science sequence using 2D game development as a unifying theme. We teach fundamental programming concepts via two dimensional game development in Flash and ActionScript during the first quarter, transition to C++ to solidify concepts and add pointers during the second quarter, then teach a multi-phase project based game approach using C++ and openGL (2D graphics only) during the third quarter. Our surveys show that this approach improved student understanding of all seven basic topics examined.

We present a new approach for approximate nearest neighbor queries for sets of high dimensional points under any L/sub t/-metric, t=1,...,/spl infin/. The proposed algorithm is efficient and simple to implement. The algorithm uses multiple shifted copies of the data points and stores them in up to (d+1) B-trees where d is the dimensionality of the data, sorted according to their position along a space filling curve. This is done in a way that allows us to guarantee that a neighbor within an O(d/sup 1+1/t/) factor of the exact nearest, can be returned with at most (d+1)log, n page accesses, where p is the branching factor of the B-trees. In practice, for real data sets, our approximate technique finds the exact nearest neighbor between 87% and 99% of the time and a point no farther than the third nearest neighbor between 98% and 100% of the time. Our solution is dynamic, allowing insertion or deletion of points in O(d log/sub p/ n) page accesses and generalizes easily to find approximate k-nearest neighbors.

Opportunistic scheduling utilizes idle workstations to execute batch jobs. Other than ensuring that each batch user receives a fair allocation of service, no work addressing opportunistic scheduling of batch jobs has been done. The authors propose two simple scheduling policies to be used in conjunction with the Condor Up-Down scheduling algorithm. We show that an order of magnitude reduction in mean job slowdown can be achieved by rotating a user's batch jobs within their queue. Furthermore, this improved slowdown can be achieved without a significant loss of throughput. The reduced slowdowns result in a more interactive nature of the system, thus increasing its appeal. Our proposed modifications to the algorithms would require very little effort to implement.

The coming years will witness dramatic advances in wireless communications as well as positioning technologies. As a result, tracking the changing positions of objects capable of continuous movement is becoming increasingly feasible and necessary. The present paper proposes a novel, R*-tree based indexing technique that supports the efficient querying of the current and projected future positions of such moving objects. The technique is capable of indexing objects moving in one-, two-, and three-dimensional space. Update algorithms enable the index to accommodate a dynamic data set, where objects may appear and disappear, and where changes occur in the anticipated positions of existing objects. A comprehensive performance study is reported.

Past R-tree studies have focused on the number of nodes visited as a metric of query performance. Since database systems usually include a buffering mechanism, we propose that the number of disk accesses is a more realistic measure of performance. We develop a buffer model to analyze the number of disk accesses required for spatial queries using R-trees. The model can be used to evaluate the quality of R-tree update operations, such as various node splitting and tree restructuring policies, as measured by query performance on the resulting tree. We use our model to study the performance of three well-known R-tree loading algorithms. We show that ignoring buffer behavior and using number of nodes accessed as a performance metric can lead to incorrect conclusions, not only quantitatively, but also qualitatively. In addition, we consider the problem of how many levels of the R-tree should be pinned in the buffer.

Scientific databases must be able to efficiently run subset retrievals of multidimensional data sets. If the data sets are very large, significant retrieval speedups can be obtained via parallelism. In this paper, we present a new parallel distributed shared-nothing R-tree architecture. We provide experimental results demonstrating actual speedups for several synthetic and real data sets. In addition, we conduct experimental studies to investigate the effect of several declustering strategies and communication parameters.

Past R tree studies have focused on the number of nodes visited as a metric of query performance. Since database systems usually include a buffering mechanism, we propose that the number of disk accesses is a more realistic measure of performance. We develop a buffer model to analyze the number of disk accesses required for spatial queries using R trees. The model can be used to evaluate the quality of R tree update operations, such as various node splitting and tree restructuring policies, as measured by query performance on the resulting tree. We use our model to study the performance of three well known R tree packing algorithms. We show that ignoring buffer behavior and using number of nodes accessed as a performance metric can lead to incorrect conclusions, not only quantitatively, but also qualitatively. In addition, we consider the problem of how many levels of the R tree should be pinned in the buffer.

Presents the results from an extensive comparison study of three R-tree packing algorithms: the Hilbert and nearest-X packing algorithms, and an algorithm which is very simple to implement, called the STR (Sort-Tile-Recursive) algorithm. The algorithms are evaluated using both synthetic and actual data from various application domains including VLSI design, GIS (Tiger files), and computational fluid dynamics. Our studies also consider the impact that various degrees of buffering have on query performance. Experimental results indicate that none of the algorithms as best for all types of data. In general, our new algorithm requires up to 50% fewer disk accesses than the best previously proposed algorithm for point and region queries on uniformly distributed or mildly skewed point and region data, and approximately the same for highly skewed point and region data.

This paper considers the problem of bulk-loading large data sets for the gridfile multiattribute indexing technique. We propose a rectilinear partitioning algorithm that heuristically seeks to minimize the size of the gridfile needed to ensure no bucket overflows. Empirical studies on both synthetic data sets and on data sets drawn from computational fluid dynamics applications demonstrate that our algorithm is very efficient, and is able to handle large data sets. In addition, we present an algorithm for bulk-loading data sets too large to fit in main memory. Utilizing a sort of the entire data set it creates a gridfile without incurring any overflows.

No abstract available.

Traditionally, allocation of data in distributed database management systems has been determined by off-line anidysis and optimization.This technique works well for static database access patterns, but is often inadequate for frequently changing workloads.This paper addresses the problem of dynamically reallocating data in a partionable distributed database with changing access patterns.Rather than complicated and expensive optimization algorithms, a simple heuristic is presented and shown, via an implementation study, to improve system throughput by 3070 in a local area net work based system.For a wide area network the performance gain is expected to be even larger.It is also shown that individual site load must be taken into consideration when reallocating data.A a simple policy that incorporates load in the reallocation decision is provided.1

A new iterative algorithm, the multi-level algorithm, for the numerical solution of steady state Markov chains is presented. The method utilizes a set of recursively coarsened representations of the original system to achieve accelerated convergence. It is motivated by multigrid methods, which are widely used for fast solution of partial differential equations. Initial results of numerical experiments are reported, showing significant reductions in computation time, often an order of magnitude or more, relative to the Gauss-Seidel and optimal SOR algorithms for a variety of test problems. It is shown how the well-known iterative aggregation-disaggregation algorithm of Takahashi can be interpreted as a special case of the new method. 1. Introduction Markov systems generated by computer modeling tools such as queueing networks, Petri nets, or reliability modeling packages may contain hundreds of thousands of states. The resulting sparse linear systems of equations have a correspondingl...

The low cost and availability of clusters of workstations have lead researchers to re-explore distributed computing using independent workstations.This approach may provide better cost/performance than tightly coupled multiprocessors.In practice, this approach oflen utilizes wasted cycles to run parallel jobs.In this paper we address the feasibility of such a nondedicated parallel processing environment assuming workstation processes have preemptive priority over parallel tasks.We develop an analytical model to predict parallel job response times.Our model provides insight into how significantly workstation owner interference degrades parallel program performance.A new term task ratio, which relates the parallel task demand to the mean service demand of non parallel workstation processes, is introduced.We propose that task ratio is a useful metric for determining how large the demand of a parallel applications must be in order to make eficient use of a non-dedicated distributed system.

The TPC-C benchmark is a new benchmark approved by the TPC council intended for comparing database platforms running a medium complexity transaction processing workload. Some key aspects in which this new benchmark differs from the TPC-A benchmark are in having several transaction types, some of which are more complex than that in TPC-A, and in having data access skew. In this paper we present results from a modelling study of the TPC-C benchmark for both single node and distributed database management systems. We simulate the TPC-C workload to determine expected buffer miss rates assuming an LRU buffer management policy. These miss rates are then used as inputs to a throughput model. From these models we show the following: (i) We quantify the data access skew as specified in the benchmark and show what fraction of the accesses go to what fraction of the data. (ii) We quantify the resulting buffer hit ratios for each relation as a function of buffer size. (iii) We show that close to linear scale-up (about 3% from the ideal) can be achieved in a distributed system, assuming replication of a read-only table. (iv) We examine the effect of packing hot tuples into pages and show that significant price/performance benefit can be thus achieved. (v) Finally, by coupling the buffer simulations with the throughput model, we examine typical disk/memory configurations that maximize the overall price/performance.

Scheduling policies for general purpose multiprogrammed multiprocessors are not well understood. This paper examines various policies to determine which properties of a scheduling policy are the most significant determinants of performance. We compare a more comprehensive set of policies than previous work, including one important scheduling policy that has not previously been examined. We also compare the policies under workloads that we feel are more realistic than previous studies have used. Using these new workloads, we arrive at different conclusions than reported in earlier work. In particular, we find that the “smallest number of processes first” (SNPF) scheduling discipline performs poorly, even when the number of processes in a job is positively correlated with the total service demand of the job. We also find that policies that allocate an equal fraction of the processing power to each job in the system perform better, on the whole, than policies that allocate processing power unequally. Finally, we find that for lock access synchronization, dividing processing power equally among all jobs in the system is a more effective property of a scheduling policy than the property of minimizing synchronization spin-waiting, unless demand for synchronization is extremely high. (The latter property is implemented by coscheduling processes within a job, or by using a thread management package that avoids preemption of processes that hold spinlocks.) Our studies are done by simulating abstract models of the system and the workloads.

This paper presents a preliminary performance analysis of a new large-scale multiprocessor: the Wisconsin Multicube. A key characteristic of the machine is that it is based on shared buses and a snooping cache coherence protocol. The organization of the shared buses and shared memory is unique and non-hierarchical. The two-dimensional version of the architecture is envisioned as scaling to 1024 processors.