Computer science education (CSEd) is a growing interdisciplinary area that continues to gain momentum from students, researchers, and educators. Yet, there are few formal programs or degree options for students interested in pursuing graduate work in CSEd. This article explores the existing state of CSEd in the United States (U.S.) through semi-structured interviews with ( n = 15) faculty engaged in CSEd research. Thematic coding of the transcripts revealed the complexities involved in the development of formal programs, the distinct considerations for faculty, and the value of having strong ties to both computer science and education. The themes described positive aspects of support and cohesion within the larger community and opportunities to expand knowledge across fields. Applying Cornell and Parker’s principles of interdisciplinary science to the field of CSEd, we provide recommendations for ways forward and discuss the potential impact on institutional structures, research capacity, individual and group identities, and teaching and learning. The findings from this investigation not only inform on the present state of CSEd in the U.S., but also offer guidance for CSEd-focused graduate programs.

Opportunities for training CS K-12 pre-service and in-service teachers, research in CS Education, and career pathways for PhDs/EdDs in CS education are happening, but often in an uncoordinated way. We advocate that now is the right time for CS and Education to collaborate on developing new joint degree programs in Computer Science Education and to explore joint faculty appointments. High undergraduate enrollment in computing programs and the increasing interest in CS courses from non-majors represent a unique opportunity for starting successful programs. As more of CS undergraduates are undergraduate TAs and see teaching and learning from a non-learner perspective, their interest in education has also increased. The growing interest in CS education, including the need for effecting CS teaching at both K-12 and the undergraduate level, provide interesting job opportunities for CS education researchers. As CS departments develop new undergraduate degree programs and scale class sizes, research on questions like How do we teach effectively computing to different audiences? How can we assess CS learning? What are culturally responsive pedagogies? is important. To answer many of these and related questions, CS departments should be actively engaged in CS Education research, from training graduate students in interdisciplinary programs to research programs. This BOF will provide a platform for the discussion on what such graduate programs - from certificate to a PhD - can and should look like, what challenges exist to creating them, and how students with different backgrounds should get trained in the relevant foundations of CS and Education.

The current efforts to expand computer science (CS) education in K-12 schools, such as the “CS for All” initiative, highlight the need for all students to get an opportunity to study computing. However, as recent research has shown, diversity in computing at the K-12 level remains problematic, and additional research is needed to look at how computer science learning environments can impact minority student interest and retention in CS. In this article, we report results from an in-depth qualitative study of high school computer science teachers’ perspective on barriers to increasing diversity in their classes. Based on teachers’ experiences, we provide practical recommendations on how to encourage equitable learning environments in K-12 computer science courses.

Computational thinking (CT) is broadly defined as the mental activity for abstracting problems and formulating solutions that can be automated. In an increasingly information-based society, CT is becoming an essential skill for everyone. To ensure that students develop this ability at the K-12 level, it is important to provide teachers with an adequate knowledge about CT and how to incorporate it into their teaching. This article describes a study on designing and introducing computational thinking modules and assessing their impact on preservice teachers’ understanding of CT concepts, as well as their attitude towards computing. Results demonstrate that introducing computational thinking into education courses can effectively influence preservice teachers’ understanding of CT concepts.

As computational thinking becomes a fundamental skill for the 21st century, K-12 teachers should be exposed to computing principles. This paper describes the implementation and evaluation of a computational thinking module in a required course for elementary and secondary education majors. We summarize the results from open-ended and multiple-choice questionnaires given both before and after the module to assess the students' attitudes toward and understanding of computational thinking. The results suggest that given relevant information about computational thinking, education students' attitudes toward computer science becomes more favorable and they will be more likely to integrate computing principles in their future teaching.

The number of undergraduates entering computer science has declined in recent years. This is paralleled by a drop in the number of high school students taking the CS AP exam and the number of high schools offering computer science courses. The declines come at a time when career opportunities in CS continue to grow and computer science graduates are seen as crucial in building a globally competitive workforce for the 21st century. Efforts aimed at reversing the declining interest in computer science include curriculum revisions at the undergraduate level at many institutions, a re-design of computer science AP courses [1], and the inclusion of computational thinking into disciplines outside computer science [3].

No abstract available.

This paper describes the development and initial evaluation of a new course ``Introduction to Computational Thinking'' taken by science majors to fulfill a college computing requirement. The course was developed by computer science faculty in collaboration with science faculty and it focuses on the role of computing and computational principles in scientific inquiry. It uses Python and Python libraries to teach computational thinking via basic programming concepts, data management concepts, simulation, and visualization. Problems with a computational aspect are drawn from different scientific disciplines and are complemented with lectures from faculty in those areas. Our initial evaluation indicates that the problem-driven approach focused on scientific discovery and computational principles increases the student's interest in computing.

This paper describes the implementation and evaluation of a program that uses active recruiting and peer-led team learning to try to increase the participation and success of women and minority students in undergraduate computer science. These strategies were applied at eight universities starting in the fall of 2004. There have been some impressive results: We succeeded in attracting under-represented students who would not otherwise have taken a CS course.Evaluation shows that participation in our program significantly improves retention rates and grades, especially for women.Students in the program, as well as the students who served as peer leaders, are uniformly enthusiastic about their experience.

The inherent uncertainty of data present in numerous applications such as sensor databases, text annotations, and information retrieval motivate the need to handle imprecise data at the database level. Uncertainty can be at the attribute or tuple level and is present in both continuous and discrete data domains. This paper presents a model for handling arbitrary probabilistic uncertain data (both discrete and continuous) natively at the database level. Our approach leads to a natural and efficient representation for probabilistic data. We develop a model that is consistent with possible worlds semantics and closed under basic relational operators. This is the first model that accurately and efficiently handles both continuous and discrete uncertainty. The model is implemented in a real database system (PostgreSQL) and the effectiveness and efficiency of our approach is validated experimentally.

Orion is a state-of-the-art uncertain database management system with built-in support for probabilistic data as first class data types. In contrast to other uncertain databases, Orion supports both attribute and tuple uncertainty with arbitrary correlations. This enables the database engine to handle both discrete and continuous pdfs in a natural and accurate manner. The underlying model is closed under the basic relational operators and is consistent with Possible Worlds Semantics. We demonstrate how Orion simplifies the design and enhances the capabilities of two example applications: managing sensor data (continuous uncertainty) and inferring missing values (discrete uncertainty).

Uncertainty in categorical data is commonplace in many applications, including data cleaning, database integration, and biological annotation. In such domains, the correct value of an attribute is often unknown, but may be selected from a reasonable number of alternatives. Current database management systems do not provide a convenient means for representing or manipulating this type of uncertainty. In this paper we extend traditional systems to explicitly handle uncertainty in data values. We propose two index structures for efficiently searching uncertain categorical data, one based on the R-tree and another based on an inverted index structure. Using these structures, we provide a detailed description of the probabilistic equality queries they support. Experimental results using real and synthetic datasets demonstrate how these index structures can effectively improve the performance of queries through the use of internal probabilistic information.

The emergence of location-aware services calls for new real time spatio-temporal query processing algorithms that deal with large numbers of mobile objects and queries. Online query response is an important characterization of location-aware services. A delay in the answer to a query gives invalid and obsolete results, simply because moving objects can change their locations before the query responds. To handle large numbers of spatio-temporal queries efficiently, we propose the idea of sharing as a means to achieve scalability. In this paper, we introduce several types of sharing in the context of continuous spatio-temporal queries. Examples of sharing in the context of real-time spatio-temporal database systems include sharing the execution, sharing the underlying space, sharing the sliding time windows, and sharing the objects of interest. We demonstrate how sharing can be integrated into query predicates, e.g., selection and spatial join processing. The goal of this paper is to outline research directions and approaches that will lead to scalable and efficient location-aware services.

In this paper, we study a peer-to-peer media streaming system with the following characteristics: (1) its streaming capacity grows dynamically; (2) peers do not exhibit server-like behavior; (3) peers are heterogeneous in their bandwidth contribution; and (4) each streaming session may involve multiple supplying peers. Based on these characteristics, we investigate two problems: (1) how to assign media data to multiple supplying peers in one streaming session and (2) how to quickly amplify the system's total streaming capacity. Our solution to the first problem is an optimal media data assignment algorithm OTS/sub p2p/, which results in minimum buffering delay in the consequent streaming session. Our solution to the second problem is a distributed differentiated admission control protocol DAC/sub p2p/. By differentiating between requesting peers with different outbound bandwidth, DAC/sub p2p/ achieves fast system capacity amplification; benefits all requesting peers in admission rate, waiting time, and buffering delay; and creates an incentive for peers to offer their truly available out-bound bandwidth.

This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms . We describe two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel. Our partitioning strategies create a small number of coarse tasks. This allows for sharing of prefixes and sort orders between different group-by computations. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting. The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array. We have implemented our parallel top-down data cube construction method in C++ with the MPI message passing library for communication and the LEDA library for the required graph algorithms. We tested our code on an eight processor cluster, using a variety of different data sets with a range of sizes, dimensions, density, and skew. Comparison tests were performed on a SunFire 6800. The tests show that our partitioning strategies generate a close to optimal load balance between processors. The actual run times observed show an optimal speedup of p .

Moving object environments are characterized by large numbers of moving objects and numerous concurrent continuous queries over these objects. Efficient evaluation of these queries in response to the movement of the objects is critical for supporting acceptable response times. In such environments, the traditional approach of building an index on the objects (data) suffers from the need for frequent updates and thereby results in poor performance. In fact, a brute force, no-index strategy yields better performance in many cases. Neither the traditional approach nor the brute force strategy achieve reasonable query processing times. This paper develops novel techniques for the efficient and scalable evaluation of multiple continuous queries on moving objects. Our solution leverages two complimentary techniques: Query Indexing and Velocity Constrained Indexing (VCI). Query Indexing relies on 1) incremental evaluation, 2) reversing the role of queries and data, and 3) exploiting the relative locations of objects and queries. VCI takes advantage of the maximum possible speed of objects in order to delay the expensive operation of updating an index to reflect the movement of objects. In contrast to an earlier technique that requires exact knowledge about the movement of the objects, VCI does not rely on such information. While Query Indexing outperforms VCI, it does not efficiently handle the arrival of new queries. Velocity constrained indexing, on the other hand, is unaffected by changes in queries. We demonstrate that a combination of Query Indexing and Velocity Constrained Indexing enables the scalable execution of insertion and deletion of queries in addition to processing ongoing queries. We also develop several optimizations and present a detailed experimental evaluation of our techniques. The experimental results show that the proposed schemes outperform the traditional approaches by almost two orders of magnitude.

This paper explores the use of data replication to improve external searc hing in static tree structures.We present general and eÆcient mappings from the nodes of a tree T to blocks of size B when nodes of T can be replicated.The amount of replication is controlled and block utilization and blocknumber are optimized.We consider total node replication (measuring the total space used) and individual node replication (measuring the replication of indivdual nodes).For an arbitrary tree T of size N and heigh th, w e show that by using at most 3 2 N space one can achiev ea b l o c knumber proportional to the optimal blocknumberofdh=Be.We sho w that when every node can be replicated only a constan tnumber of times, no signi cant reduction in the blocknumber may b e possible.Our w orkalso shows that generating mappings in which all but one block c o n tain exactly B nodes increases the blocknumberby a t m o s t 2 .

In s-to-p broadcasting, s processors in a processor machine contain a message to be broadcast to all the processors, 1/spl les/s/spl les/p. We present a number of different broadcasting algorithms that handle all ranges of s. We show how the performance of each algorithm is influenced by the distribution of the s source processors and by the relationships between the distribution and the characteristics of the interconnection network. For the Intel Paragon we show that for each algorithm and machine dimension there exist ideal distributions and distributions on which the performance degrades. For the Cray T3D we also demonstrate dependencies between distributions and machine sizes. To reduce the dependence of the performance on the distribution of sources, we propose a repositioning approach. In this approach, the initial distribution is turned into an ideal distribution of the target broadcasting algorithm. We report experimental results for the Intel Paragon and Cray T3D and discuss scalability and performance.

We study the broadcasting of messages in the single-port, blocking communication model under edge reductions. Edge reductions model the decrease or elimination of broadcast costs on edges. Let T be an n-vertex tree and B be a target broadcast cost. We present an O(n) time algorithm for determining which edges to reduce (i.e., assign cost 0) such that the number of reduced edges is a minimum and a broadcast initiated at a vertex in a determined center set costs at most B. We present an O(n log n) time algorithm to minimize the cost of a broadcast initiated at an arbitrary vertex.

In the paper we present parallel solutions for performing image contour ranking on coarse-grained machines. In contour ranking, a linear representation of the edge contours is generated from the edge contours of a raw image. We describe solutions that employ different divide-and-conquer approaches and that use different communication patterns. The combining step of the divide-and-conquer solutions uses efficient sequential techniques for merging information about subimages. The proposed solutions are implemented on Intel Delta and Intel Paragon machines. We discuss performance results and present scalability analysis using different image and machine sizes. © 1997 by John Wiley & Sons, Ltd.

We describe a project that integrates applications requirements, parallel algorithm design, models of parallel computing, and software tools in order to improve the ability of applications researchers in the fields of computer vision and image processing (CVIP) to realize the performance potential of high performance parallel computers. This objective is achieved by pursuing four directions of research: the development of efficient and practical scalable algorithms for fundamental CVIP problems; the implementation of realistic CVIP scenarios on high performance computers; the development of a scalable, architecture-independent parallel model and a metric for estimating the performance of an algorithm on an existing parallel machine; and the development of prototype software tools. In this paper we describe work in each of these areas.

We present two asymptotically optimal @(n) time algorithms for labeling the connected components of a gray-scale image on a mesh-connected computer.We assume that the input is an n x n gray-scale image mapped one pixel per processor onto an n x n mesh-connected computer.Our algorithms label the components so that every component is connected, the maximum difference in the gray-scale values of the pixels within any component does not exceed a given value, and no component can be merged with a neighboring component.The first algorithm is based on a divide-and-conquer approach.Although it is simple, this algorithm has the potential drawback of possibly assigning two adjacent pixels with the same gray-scale value to different components.The second algorithm avoids this potential drawback, and exploits the ability of a mesh-connected computer to efficiently determine a maximal independent set of a planar graph.

In this paper the authors consider the one-dimensional compaction problem when the layout area contains forbidden regions and the layout components are allowed to move across these regions. Assuming a feasible layout is given containing k forbidden regions and n layout components where the i-th layout component is a rectilinear polygon consisting of upsilon /sub i/ vertical edges, upsilon = Sigma /sub i=1//sup n/ upsilon /sub i/, the authors present an algorithm that determines the positions of the layout components resulting in minimum area in O( sigma log sigma + sigma nlogn) time with an additional O(( upsilon +k)logk+( upsilon + sigma )log upsilon /sub max/) preprocessing time, where upsilon /sub max/=max/sub 1>

The authors present embeddings of complete binary trees into butterfly networks with or without wrap-around connections. Let m be an even integer and q=m+(log m)-1. The authors show how to embed a 2/sup q+1/-1-node complete binary tree T(q) into a (m+1)2/sup m+1/-node wrap-around butterfly B/sub w/(m+1) with a dilation of 4, and how to embed T(q) into a (m+2)2/sup m+2/-node wrap-around butterfly B/sub w/(m+2) with an optimal dilation of 2. They also present an embedding of a wrap-around butterfly B/sub w/(m) into a (m+1)2/sup m/-node no-wrap-around butterfly B(m) with a dilation of 3. Using this embedding it is shown that T(q) can be embedded into a no-wrap butterfly B(m+1) (resp. B(m+2)) with a dilation of 8 (resp. 5).>

The problem of determining a minimum-cost rectilinear Steiner tree when the input is an n*n binary array, I which is stored in an n*n mesh of processors is discussed. Several heuristic mesh algorithms are presented for this NP-hard problem. A major design criterion of the algorithms is to avoid sorting and routing, which are expensive operations in practice. All of the algorithms have an O(n log k) worst-case running time, where k is the number of connected components formed by the entries of value 1. Two conceptually different methods for connecting components in an image and a method for improving subsolutions by making horizontal and vertical shortcuts are presented.>

In the channel routing problem, a problem arising in the design of layout systems, two rows of terminals which are opposite each other, have to be connected. We study what effect the rotation of one row of terminals has on the cost measures of the routing phase. The cost measures we consider are the density, which is proportional to the width of the channel, the crossing number, which is closely related to the number of crossings between two wires in the channel, and the length of nets, which is related to the wire length needed in the routing. We present algorithms for determining the rotations which minimize each of these cost measures. The algorithms can also be used for solving optimal offset problems.

In this paper we present techniques that result in O(√n) time algorithms for computing many properties and functions of an n-node forest stored in an √n × √n mesh of processors. Our algorithms include computing simple properties like the depth, the height, the number of descendents, the preorder (resp. postorder, inorder) number of every node, and a solution to the more complex problem of computing the Minimax value of a game tree. Our algorithms are asymptotically optimal since any nontrivial computation will require Ω (√n) time on the mesh. All of our algorithms generalize to higher dimensional meshes.

We study VLSI solutions to the connected component problem on networks that have area too small to store all the edges of the graph for the entire computation. We give lower bounds on the time needed to solve this problem on such networks, as well as an optimal algorithm. The lower bounds use a new proof technique combining adversary strategy, information flow, and Kolmogorov complexity arguments. The lower bounds obtained for the connected components problem hold for a number of other undirected graph problems.

We consider routing models that consist of L layers in which each layer can contain horizontal and vertical wires and in which up to k wires on different layers are allowed to run on top of each other. Within this overlap model we study the relationship between the channel width, the number of contact points, and the amount of overlap used for routing n two-terminal nets across a channel. For k ≤ [L/2] - 2 we show how to solve the channel routing problem using [d/k] + 1 tracks, which is only one track more than the optimal channel width. We extend this algorithm to values of k in the range [L/2] - 1 ≤ k ≤ [L/2] +1. We also present algorithms for the 3- and 4-layer model with double overlap that use fewer tracks than our general channel routing algorithm. All algorithms use O(n) contact points and can be implemented to run in O(n) time.

This paper presents algorithms for the connected component problem that are suitable for VLSI implementation and use $o(n^2 )$ area. Two VLSI models, which differ in the number of input/output ports allowed to be placed on the boundary of the chip, are considered. It is shown how to achieve a continuous area-time tradeoff of $AT^2 = O(n^4 )$ in the range $\Omega (n) = A = o(n^2 )$. This tradeoff is optimal for one model, and for the other model continuous tradeoffs of the form $AT = O(n^{5/2} )$ in the range $\Omega (n) = A = O(n^{5/4} )$ and $AT^3 = O(n^5 )$ in the range $\Omega (n^{5/4} ) = A = o(n^2 )$ are exhibited.