The past thirty years have seen many advances in our understanding of issues that impede diversity, as well as interventions that can remove or mitigate those impediments. The advances are generally presented in psychology journals and are under-consumed by computing educators, leading to the need for diversity training tailored to said educators. We have hundreds of hours of experience providing diversity training to computing educators, and have learned many lessons about how training should and should not be delivered to engage participants in understanding diversity-impeding forces and implementing interventions to improve the attraction and retention of diverse students. This paper is a collection of those lessons learned. We focus on concrete approaches to presenting material rather than on training organization or content, including a dozen specific practices that have proven particularly effective or ineffective in reaching diverse audiences. Examples include how how to avoid offending participants, how to help experts not lose their audience, how to pace and organize material for maximum impact, how we tie many topics into a single cognitive framework, and how we've learned to handle participant-raised objections. We also include commentary as to why we believe they did or did not work. We also describe possible future research to validate and expand on our observations and a few open questions for diversity training.

This Research Full Paper reports the results of a 30-item survey of students in three large-enrollment introductory CS courses in the Fall semester of 2017. This survey was designed to provide insight into the perceptions and motivation differences between students from underrepresented minorities in the field of computing (CS-URMs) and CS non-URMs in large-enrollment introductory computer science (CS) courses. Its focus is on how diverse learners engage in the course and how students from diverse backgrounds (e.g., gender, race/ethnicity) perceive large-enrollment college introductory CS courses that incorporate collaborative learning activities. Survey items were adapted from four validated instruments. Survey responses from 517 students suggest significant differences between CS-URM and CS non-URM students in their perceptions of collaborative learning and instructor support. CS-URMs students' motivation was significantly higher than CS non-URMs. The study findings have implications for how to engage diverse learners in introductory computing courses. The paper provides suggestions for designing CS introductory courses to be more inclusive learning environments for all.

Although computing occupations increasingly dominate the workforce, the computing discipline does not attract sufficient and diverse students to meet societal workforce needs. LIGHTHOUSE FOR CS is a collection of professional development efforts seeking to increase computing diversity through faculty education. LIGHTHOUSE CC provides an open online course extending a decade of successful face-to-face TAPESTRY workshops. LIGHTHOUSE CC targets community college computing faculty, building off of research suggesting that online professional development can be as effective as in-person professional development. We believe it is one of the first attempts to validate that finding for community college computing faculty. The paper examines participant motivations and perceptions of online and face-to-face diversity-focused professional development for community college computing educators. To meet the needs of the community college computing faculty, we began with a needs assessment survey. Its feedback and prior face-to-face workshop experiences were integrated with several instructional design principles and theories to engage community college faculty, notably the ARCS motivational design model (Keller, 1987) and the Community of Practice model (Wenger, 1998). Project analyses involved both surveys and focus group interviews. The paper also provides directions for future improvements and suggestions for others who are considering online or diversity-focused professional development.

Computing occupations increasingly dominate the workforce, but the discipline fails to attract sufficient and diverse students (i.e., women, underrepresented minorities) to meet workforce needs. To address this issue, LIGHTHOUSE projects provide computer science instructors with professional development MOOCs to recruit and retain more and diverse students in computing. We present how a professional development MOOC has been designed with relevant instructional design principles and theories to suit community college computer science instructors' learning needs. In this paper we share results from a needs assessment survey that, along with the relevant instructional theories and design principles, guided the design of an innovative diversity-focused online professional development learning environment.

The goal of this panel is to engage the computing education community in perspectives on developing and delivering diversity-focused faculty professional development. Panel session attendees will gain an understanding of the role and importance of diversity-focused professional development and knowledge about the critical instructional components that affect successful online and face-to-face professional development available to them and their colleagues. The panel is comprised of scholars who are both researchers and educators. They provide a range of experience developing and delivering professional development to high school, community college, undergraduate and graduate school computing faculty.

Women of all colors are underrepresented in most technical disciplines. For example, electrical engineering college graduates have comprised only about ten percent women for many years, and computing graduates only about eighteen percent women, down from about thirty-five percent in the mid-1980s. Gender stereotypes and stereotypes about creators of technology contribute to this underrepresentation. Nevertheless, these prevailing conditions can be overcome to a substantial degree by actively recruiting diverse female students. This panel session will provide an introduction to the reasons for active recruiting, methods for successful active recruiting, examples of effective applications of the recommended methods, and resources to help participants as they attempt to actively recruit underrepresented students to their courses. The panel's focus will be on computing disciplines, but the information applies to other technical disciplines as well.

Four research-supported teaching methods can make your computing courses more effective through improved student learning, comprehension, and motivation.

Traditional introductory programming classes teach sequential programming using a single-threaded programming model. It is typical to wait until a student has developed proficiency in sequential programming before teaching parallel programming. As computer hardware becomes increasingly parallel, there is a greater need for software engineers who are proficient in designing parallel programs, and not just by "parallelizing" sequential designs. Teaching parallelism first is an important step towards educating tomorrow's programmers.

This mini-workshop will follow a “train-the-trainer” model. Experts will provide guidance and resources for college computing faculty who wish to organize workshops for high school computer science teachers. These workshops will enable the teachers to attract more and diverse students to their computer science classes, which will add to the college-bound population of students prepared for and interested in a computing major.

An effective workshop has been developed for promoting a positive impact on high school teachers' recruitment of students, particularly women and minority students, into their CS classes. All past workshop attendees indicate they now are actively try to recruit girls and minority students into their computing classes and are successful in doing so.

An effective CS1 approach has been developed for encouraging diverse students without prior computer science experiences to select computing majors. Separation of CS1 sections by prior experience level concentrates diverse students in the inexperienced section. Within that section we use several techniques to increase student comprehension and participation, including an integrated lecture/lab, many small examples and assignments, student participation, etc. We discuss the approach and evaluate its performance over a four-year time period.

We report on a pilot section of an introductory computing course offered at a top tier university through its engineering school. Although targeted for students with no prior programming experience, its goals were same as the goals of the other sections. The course enrolled 43 students. They were 49% female, 23% black, and 12% Hispanic. The demographics are different from the typical 1st year class at the school, which is 26% female, 6% black, and 3% Hispanic. Two important pedagogies differentiated the pilot section from other sections: computer availability at all class meetings and the methodology for selecting motivating examples. A priori only one student in the section intended a computing major, but upon completion the students chose a computing major at a higher rate than the rates for other sections: 19% versus 13%. More striking is that 33% of the pilot section women and 27% of its minority students chose a computing major. All students completed the course and no student left the school. These outcomes compare favorably to a school course withdrawal rate of 12% and a school attrition rate of 10%, a female attrition rate of 12%, and a minority rate attrition of 25%.

We present the concept of "problem perturbation", give the specifications of an application to the travelling salesperson problem (TSP), then discuss an empirical study of the fitness landscape induced by the variation operators in that application.

FPGAs are a useful and flexible alternative to custom design chips, but can suffer from severe interconnection delay. The 3D-FPGA is an alternative to the two-dimensional architecture that has been proposed to reduce these delay problems. Here we present Spiffy-the first tool specifically designed for the placement and global routing of 3D-FPGAs. Spiffy produces some of the best results in the literature, and using Spiffy we can show that when mapped to the 3D-FPGA architecture, circuits tend to have considerably shorter net-length, making this new chip an improvement over the standard architecture.

The minimum-congestion hypergraph embedding in a cycle (MCHEC) problem is to embed the n edges in an m-vertex hypergraph as paths in a cycle on the same number of vertices, such that congestion-the maximum number of paths that use any single edge in the cycle-is minimized. The MCHEC problem has applications in electronic design automation and parallel computing. In this paper, it is proven that the MCHEC problem is NP-complete. An O((nm)/sup k+1/) algorithm is described that computes an embedding with congestion k or determines that such an embedding does not exist. Finally, a linear-time approximation algorithm for arbitrary instances is presented that computes an embedding whose congestion is at most three times optimal.

Moat routing is the routing of nets between the input/output pads and the core circuit. In this paper, it is proved that moat routing is NP-complete under the routing model in which there are no vertical conflicts and doglegs are disallowed (i.e., every net is routed within a single track). This contrasts with the fact that channel routing is efficiently solvable under these restrictions. The paper then presents an approximation algorithm for moat routing that computes moat routing solutions that are guaranteed to use at most four times the optimal number of tracks. Empirical results are presented indicating that for a number of industrial benchmarks, the algorithm produces solutions that are near optimal and that use significantly fewer tracks than previous moat routing strategies.

The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the thumbnail rectilinear Steiner tree problem, where the input points are drawn from a small integer grid. Specifically, we devise a fully-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing the performance of this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms, based on geometric partitioning, global routing of field-programmable gate arrays, and routing estimation during floorplanning.

The rectilinear Steiner tree problem is to find a minimum-length set of horizontal and vertical line segments that interconnect a given set of points in the plane. Here we study the thumbnail rectilinear Steiner tree problem, where the input points are drawn from a small integer grid. Specifically, we devise a full-set decomposition algorithm for computing optimal thumbnail rectilinear Steiner trees. We then present experimental results comparing this algorithm with two existing algorithms for computing optimal rectilinear Steiner trees. The thumbnail rectilinear Steiner tree problem has applications in VLSI placement algorithms based on geometric partitioning and in global routing of field-programmable gate arrays.

We propose a two-stage simulated annealing method. While most previous work has focused on ad hoc constant starting temperatures for the low temperature annealing phase, this paper presents a more formal method for starting temperature determination in two-stage simulated annealing systems. We have successfully applied our method to three optimization problems using both classic and adaptive schedules. We also briefly discuss an alternative stop criterion that experimentally reduces the running time up to an additional ten percent in our problem suite.

An exact rectilinear Steiner minimal tree algorithm is presented that improves upon the time and space complexity of previous guarantees and is easy to implement. Experimental evidence is presented that demonstrates that the algorithm also works well in practice.>

This paper presents a new model for VLSI routing in the presence of obstacles, that transforms any routing instance from a geometric problem into a graph problem. It is the first model that allows computation of optimal obstacle-avoiding rectilinear Steiner trees in time corresponding to the instance size (the number of terminals and obstacle border segments) rather than the size of the routing area. For the most common multi-terminal critical nets-those with three or four terminals-we observe that optimal trees can be computed as efficiently as good heuristic trees, and present algorithms that do so. For nets with five or more terminals, we present algorithms that heuristically compute obstacle-avoiding Steiner trees. Analysis and experiments demonstrate that the model and algorithms work well in both theory and practice.>

A visualization tool, Examine, is presented to aid router development. Examine has the ability to display routing operations in a variety of ways (e.g., selective display of layers and nets). In addition, Examine has rudimentary animation facilities that enable a router developer to view a sequence of routing frames or a routing frame composite.>

A critical net has been routed traditionally by interconnecting its terminals with a minimum length rectilinear Steiner tree (MRST). A novel interconnection form, the maximum performance tree (MPT), that better approximates an interconnection with optimal circuit performance is proposed. In addition, a heuristic approach is presented that quickly generates MPTs, and the quality of these trees is compared with MRSTs for several net instances.>

Designing a VLSI floorplan calls for arranging a given set of modules in the plane to minimize the weighted sum of area and wire-length measures. A method of solving the floorplan design problem using distributed genetic algorithms is presented. Distributed genetic algorithms, based on the paleontological theory of punctuated equilibria, offer a conceptual modification to the traditional genetic algorithms. Experimental results on several problem instances demonstrate the efficacy of this method and indicate the advantages of this method over other methods, such as simulated annealing. The method has performed better than the simulated annealing approach, both in terms of the average cost of the solutions found and the best-found solution, in almost all the problem instances tried.>

A technique using genetic algorithms is presented for the generation of compact test sets for combinational VLSI circuits. The technique combines a previously proven method for random test pattern generation with adaptive searching capabilities to produce high-quality test sets. A series of experiments demonstrated that the technique performed consistently better than the traditional method. On average, the method is able to produce test sets that are approximately 20% smaller than the starting configuration. To place this in perspective, its solutions are on average 13% more compact than those produced by a traditional method with no loss in fault coverage.>

Given a set of input points, the rectilinear Steiner tree problem is to find a minimal-length tree consisting of vertical and horizontal line segments that connects the input points, where it is possible to add new points to minimize the length of the tree. The restricted Steiner tree problem in which all the input points lie on the boundary of a rectangle frequently occurs in VLSI physical design. Since the fastest published algorithm is cubic in the size of the point set, VLSI designers have been forced to use heuristic approximations to the length of the Steiner tree for this problem. A simple, practical, linear-time exact algorithm for finding the Steiner tree for points lying on the boundary of a rectangle which obviates the need for some heuristic algorithms in VLSI design is presented. The analysis of the algorithm is based on the use of a tie-breaking rule that should prove useful for other Steiner tree problems.>

A distributed algorithm for solving the floorplan design problem, called a genetic algorithm with punctuated equilibria (GAPE), is presented. Implementation details and the results of empirical studies are presented. The experiments have demonstrated that GAPE performs consistently better than a recently published simulated annealing approach, with respect to both the average cost of the solutions found and the best solution found.>

The problem of finding the minimum-length rectilinear Steiner tree that connects a set of points on the boundary of a rectangle is considered. A linear time algorithm for this problem is presented. The algorithm was implemented in C and executed on a Sun3 workstation. Many examples were solved in a fraction of a second. An example with over 250 terminals took 6.5 s.>

BEAVER combines a delayed layering scheme with computational geometry techniques to heuristically produce a switchbox solution that minimizes both via and usage and wire length, and maximizes the use of a preferred routing layer. Other important features are its use of priority queues to determine the order in which nets are routed, and its prioritized control of individual track and column usage to prevent routing conflicts. BEAVER consists of four tools that are run successively: a corner router, a line sweep router, a thread router, and a layerer. The corner router makes single-bend terminal-to-terminal connections. The line sweep router makes straight-line connections, single-bend connections, and two-bend connections. The thread router makes connections of arbitrary form. The layerer completes the switchbox by layering wires that have been assigned a location but not yet a layer. BEAVER has successfully routed all of the classic switchboxes. Its solution quality with respect to wire length was better than, or comparable to, the best previous solutions and its via usage was consistently the minimum.>

A placement algorithm, Genie, is presented for the assignment of modules to locations on chips. Genie is an adaptation of the genetic algorithm technique that has traditionally been a tool of the artificial intelligence community. The technique is a paradigm for examining a state space. It produces its solutions through the simultaneous consideration and manipulation of a set of possible solutions. The manipulations resemble the mechanics of natural evolution. For example, solutions are "mated" to produce "offspring" solutions. Genie has been extensively run on a variety of small test instances. Its solutions were observed to be quite good and in several cases optimal.