We discuss the design, effectiveness, and curricular impacts of an introductory data science course that uniquely meets a number of competing constraints. Student needs range from an initial exploration for future data scientists to the only computing course for some science students. Initially, associated research labs, departments, and industries provided differing perspectives on skills and preferred programming languages. The focus was on practical programming skills and learning through demos to develop useful skills quickly. The task-driven nature also enabled the mutual development of resources for each of the top three requested languages, Python, R, and MATLAB, allowing students to concurrently complete the course in any of the three languages. Tutorials in all three languages were produced to prepare students for the language-independent task-driven assignments given each day. For consistency all tutorials and assignments use the Jupyter notebook cell-based workflow. Feedback and performance measures of three student cohorts (Spring 2018, Fall 2018, and Spring 2019) are analyzed. Feedback included an average rating that met or exceeded 4 ("substantial progress") out of 5 for each separate cohort on all four general educational objectives (Basic Understanding, Developing Skills, Application, and Numeric Methods). 75% of responding students indicated a preference for the multi-language course design. The course also attracted a majority of women every semester (63% female, average). Because of these benefits, this course became the recommended first programming course for a newly developed and approved undergraduate data science major. All material is online and available at https://sites.google.com/view/comp-180

Most U.S. states support college-readiness and access through dual enrollment, in which high school students enroll in college courses. Concurrent enrollment (CE) allows students to take college courses in their own high school, taught by high school teachers approved by the partner college. CE has positive effects on students' education, but rarely is CS available through CE. Unlike AP, CE provides college credit to students who are assessed throughout the course rather than by a single high-stakes exam/project. This panel will showcase four different types of post-secondary institutions' experiences offering CS-through-CE and discuss its potential as an entry point into CS for students underrepresented in computing, including those in urban and rural settings. Panelists will share challenges (such as teacher credentialing) and benefits of CS-through-CE. The audience will understand supports and barriers to creating CS-through-CE courses, will be provided with resources, and will crowd-source possible next steps in implementing CE as a model for broadening participation.

With the CS for All movement increasingly gaining traction nationally, students entering colleges and universities are arriving with deeper and broader CS experiences. This in turn can change students' higher education starting point. This panel of CS faculty with expertise in this area will present perspectives and models to describe how higher education choices for placement, credit, and curriculum design affect the efforts to broaden participation in student pathways into computing and related studies.

This study compares the characteristics and professional development (PD) experiences between teachers who began teaching Exploring Computer Science before and after the enactment of a CS graduation requirement in the Chicago Public Schools. The post-requirement teachers were less likely to have a CS background, but their experience in the ECS PD and their level of confidence at the end of the PD were equivalent to the early adopters.

This Innovative Practice Work in Progress presents progress in developing exercises for high school students incorporating level-appropriate mathematics into robotics activities. We assume mathematical foundations ranging from algebra to precalculus, whereas most prior work on integrating mathematics into robotics uses only very elementary mathematical reasoning or, at the other extreme, is comprised of technical papers or books using calculus and other advanced mathematics. The exercises suggested are relevant to any differential-drive robot, which is an appropriate model for many different varieties of educational robots. They guide students towards comparing a variety of natural navigational strategies making use of typical movement primitives. The exercises align with Common Core State Standards for Mathematics.

This study investigated patterns in the development of computational thinking and programming expertise in the context of the Exploring Computer Science (ECS) program, a high school introductory CS course and professional development program designed to foster deep engagement through equitable inquiry around CS concepts. Prior research on programming expertise has identified three general areas of development --- program comprehension, program planning, and program generation. The pedagogical practices in ECS are consistent with problem solving approaches that support the development of programming expertise. The study took place in a large urban district during the 2016--17 school year with 28 ECS teachers and 1,931 students. A validated external assessment was used to measure the development of programming expertise. The results indicate that there were medium-sized, statistically significant increases from pretest to posttest, and there were no statistically significant differences by gender or race/ethnicity. After controlling for prior academic achievement, performance in the ECS course correlated with performance on the posttest. With respect to specific programming concepts, the results also provide evidence on the progression of the development of programming expertise. Students seem to develop comprehension and planning expertise prior to expertise in program generation. In addition, students seem to develop expertise with concrete tasks prior to abstract tasks.

This special session explores the use of magic tricks based on computer science ideas; magic tricks help grab students' attention and can motivate them to invest more deeply in underlying CS concepts. Error detection ideas long used by computer scientists provide a particularly rich basis for working such “magic”, with a CS Unplugged parity check activity being a notable example. Prior work has shown that one can perform much more sophisticated tricks than the relatively well-known CS Unplugged activity, and these tricks can motivate analyses across a wide variety of computer science concepts and are relevant to learning objectives across grade levels from 2nd grade through graduate school. These tricks have piqued the interest of past audiences and have been performed with the aid of online implementations; this conference session will demonstrate enhanced implementations used to illuminate the underlying concepts rather than just to perform the tricks. The audience will participate in puzzling out how to apply relevant concepts as we work through a scaffolded series of tricks centering on error detection and correction. The implementations also provide a useful model for incorporating greater interaction than is typically found in current innovative online interactive textbooks. In addition, they are samples for possible programming assignments that can motivate students using CS Unplugged activities to actively pursue deep programming experiences.

Since President Obama's announcement of the Computer Science for All Initiative in 2016, there has been a surge in the number of districts that are planning for or newly implementing computer science (CS) offerings at their schools. Chicago Public Schools (CPS) is the first large school district to have adopted Computer Science as a high school graduation requirement, taking this significant step along the path towards systemic change. The foundation was laid eight years ago when an informal alliance was formed between a CPS high school CS teacher, a CPS administrator, and three university computer scientists.

This study investigated patterns in the development of computational thinking practices in the context of the Exploring Computer Science (ECS) program, a high school introductory CS course and professional development program designed to foster deep engagement through equitable inquiry around CS concepts. Past research indicates that the personal relevance of the ECS experience influences students' expectancy-value towards computer science. Expectancy-value is a construct that is predictive of career choices. We extended our research to examine whether expectancy-value influences the development of computational thinking practices. This study took place in the context of two ECS implementation projects across two states. Twenty teachers, who implemented ECS in 2016-17, participated in the research. There were 906 students who completed beginning and end of year surveys and assessments. The surveys included demographic questions, a validated expectancy-value scale, and questions about students' course experiences. The assessments were developed and validated by SRI International as a companion to the ECS course. Overall, student performance statistically increased from pretest to posttest with effect size of 0.74. There were no statistically significant differences in performance by gender or race/ethnicity. These results are consistent with earlier findings that a personally relevant course experience positively influences students' expectancy for success. These results expanded on prior research by indicating that students' expectancy-value for computer science positively influenced student learning.

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.

We present resources we have constructed and culled from the internet that can be used in computing outreach visits in K--12 classrooms, especially high schools. We have used such tools at about 100 schools, reaching several thousand students, and achieving positive attitudinal responses in surveys of several hundred of these students.

A performance model for wormhole routed interconnection networks is presented and applied to the butterfly fat-tree network. Experimental results agree very closely over a wide range of load rate. Novel aspects of the model, leading to accurate and simple performance predictions, include: (1) use of multiple-server queues, and (2) a general method of correcting queuing results based on Poisson arrivals to apply to wormhole routing. These ideas can also be applied to other networks.

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cd/spl eta/+d/spl eta/ log P) time with high probability, where L is the number of flits in a packet, and /spl eta/=min {d, L}; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat tree network of area /spl ominus/(A) can simulate wormhole routing on any network of comparable area with O(log/sup 3/ A) slowdown, when all worms have the same length. Variable length worms are also considered. We run some simulations on the fat tree which show that not only does wormhole routing tend to perform better than the more heavily studied store and forward routing in this context, but that performance superior to our provable bound is attainable in practice.

Processor Thk paper provides a new approach to labeling the connected components of an n x n image on a scan line array processor (comprised of n processing elements).Variations of thk approach yield an algorithm guaranteed to complete in o(n lg n) time as well as algorithms likely to approach O(n) time for all or most images.The best previous solutions require using a more complicated architecture or require Q (n lg n) time.We also show that on a restricted version of the archkect ure, any algorithm requires Q(n lg n) time in the worst case.

This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from $\Theta ( n )$ to $\Omega ( n^2 )$, where n is the number of nets. But if the number of columns c is $O( n )$, the problem can be solved in time $O( n^{1.5} \lg n )$, which improves upon a “naive” $O( cn )$ approach. As a corollary of this result, the same time bound suffices to find the optimal offset (the one that minimizes separation). Better running times result when there are no two-sided nets or all single-sided nets are on one side of the channel. This paper also gives improvements upon the naive approach for $c \ne O( n )$, including an algorithm with running time independent of c. An interesting algorithmic aspect of the paper is a connection to discrete convolution.

This paper shows that a fat-pyramid of area /spl Theta/(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more untenable as the size of parallel systems increases. This paper concentrates on simulation using transmission lines (wires along which bits can be pipelined) with the message routing schedule set up off line, but it also discusses the extension to on-line simulation. This paper also examines the capabilities of a fat-pyramid when matched against a substantially larger network and points out the surprising difficulty of doing such a comparison without the unit wire delay assumption.>

Algorithms to minimize density for channels with terminals that are movable subject to certain constraints are given. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L, respectively, where L is the channel length and n is the number of terminals.>

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels with any number of layers and automatically chooses a good assignment of wiring strategies to the different layers. In test cases, MulCh shows significant improvement over Chameleon in terms of channel width, net length, and number of vias.>

Fat-trees are a class of routing networks for hardwareefficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor λ = Ω(lg n lg lg n) on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(λ) with probability 1-O(1/n). The best previous bound was O(λ lg n) for the off-line problem where switch settings can be determined in advance. In a VLSI-like model where hardware cost is equated with physical volume, we use the routing algorithm to demonstrate that fat-trees are universal routing networks in the sense that any routing network can be efficiently simulated by a fat-tree of comparable hardware cost.