Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Selected Works

Discipline
Keyword
Publication Year
Publication
File Type

Articles 2911 - 2940 of 16838

Full-Text Articles in Physical Sciences and Mathematics

The Impact Of Meaningful High School Computer Science Experiences In The Chicago Public Schools, Ronald I. Greenberg Jan 2018

The Impact Of Meaningful High School Computer Science Experiences In The Chicago Public Schools, Ronald I. Greenberg

Ronald Greenberg

We report on initial outcomes of the Taste of Computing project, under which a meaningful computer science course has been initiated in many high schools of the Chicago Public Schools system. Surveys of students have shown that they attribute high value to the course and have experienced increases in their understanding and interest regarding the computing field. Data was also collected from teachers participating in professional development regarding their preparation and confidence in teaching the new course. We report on the strengths of various survey responses and their relationships, and we compare student responses by race and gender. The data …

Go to article

Tools For Outreach Presentations, Ronald I. Greenberg, Dale Reed Jan 2018

Tools For Outreach Presentations, Ronald I. Greenberg, Dale Reed

Ronald Greenberg

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.

Go to article

The Impact Of The Exploring Computer Science Instructional Model In Chicago Public Schools, Ronald I. Greenberg Jan 2018

The Impact Of The Exploring Computer Science Instructional Model In Chicago Public Schools, Ronald I. Greenberg

Ronald Greenberg

As part of the Taste of Computing project, the Exploring Computer Science (ECS) instructional model has been expanded to many high schools in the Chicago Public Schools system. We report on initial outcomes showing that students value the ECS course experience, resulting in increased awareness of and interest in the field of computer science. We compare these results by race and gender. The data provide a good basis for exploring the impact of meaningful computer science instruction on students from groups underrepresented in computing; of several hundred students surveyed, nearly half were female, and over half were Hispanic or African-American.

Go to article

Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle Jan 2018

Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle

Ronald Greenberg

In a target detection communication system, apparatus and method for determining the presence of probable targets based on contacts (which can indicate the presence of a target, noise, chatter, or objects not of interest) detected within a predefined position sector or sectors over a specified number of scans. The position of each detected contact, as a contact of interest, is compared with the positions of contacts detected at previous times or scans. Velocity profiles indicate which previous contacts support the likelihood that the contact of interest represents a target having a velocity within a defined band. The likelihood, which can …

Go to article

Open Source Classroom Polling (Interactive Response) Facility, Ronald I. Greenberg Jan 2018

Open Source Classroom Polling (Interactive Response) Facility, Ronald I. Greenberg

Ronald Greenberg

The contents of the UNIX directory resulting from unzipping the .zip file provide a demonstration of a simple polling facililty that instructors can use in class any time that students have access to a web browser. This is a good way to have students work problems and see to what extent they are converging towards correct answers. Unlike other polling facilities, this one is completely free without any restrictions on number of simultaneous users, etc. It also allows a feature most polling facilities do not in that it may be used for completely free-form answers, and the instructor can still …

Go to article

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy Jan 2018

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Ronald Greenberg

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

Go to article

On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan Jan 2018

On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan

Ronald Greenberg

This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a …

Go to article

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley Jan 2018

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Ronald Greenberg

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Go to article

Pythagorean Approximations For Lego: Merging Educational Robot Construction With Programming And Data Analysis, Ronald I. Greenberg Jan 2018

Pythagorean Approximations For Lego: Merging Educational Robot Construction With Programming And Data Analysis, Ronald I. Greenberg

Ronald Greenberg

Abstract. This paper can be used in two ways. It can provide reference information for incorporating diagonal elements (for bracing or gear meshing) in educational robots built from standard LEGO kits. Alternatively, it can be used as the basis for an assignment for high school or college students to recreate this information; in the process, students will exercise skills in both computer programming and data analysis. Using the paper in the second way can be an excellent integrative experience to add to an existing course; for example, the Exploring Computer Science high school curriculum concludes with the units “Introduction to …

Go to article

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli Jan 2018

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

Ronald Greenberg

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 …

Go to article

My Materials Supporting The Exploring Computer Science Curriculum, Ronald I. Greenberg Jan 2018

My Materials Supporting The Exploring Computer Science Curriculum, Ronald I. Greenberg

Ronald Greenberg

Ready-made handouts and other resources supporting the Exploring Computer Science (introductory high school) curriculum are provided for Units 1 through 3. These materials were based on version 4 of the ECS curriculum but should remain relevant in later versions as well.

Go to article

Motion Planning For Educational Robots, Ronald I. Greenberg, Jeffery M. Karp Jan 2018

Motion Planning For Educational Robots, Ronald I. Greenberg, Jeffery M. Karp

Ronald Greenberg

This paper considers various simple ways of navigating in a 2-dimensional territory with a two-wheeled robot of a type typical in educational robotics. We determine shortest paths under various modes of operation and compare.

Go to article

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. 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.

Go to article

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. 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, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

Go to article

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih Jan 2018

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Ronald Greenberg

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the ``river-routing'' context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN/lglgN) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of …

Go to article

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih Jan 2018

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Ronald Greenberg

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear- time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN / lglgN) time on a (common) CRCW PRAM, both with optimal work (processor- time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor …

Go to article

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh Jan 2018

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh

Ronald Greenberg

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ϵ > 0, a randomized on-line algorithm for routing any set of Npackets in O((C lgϵ(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into …

Go to article

Motion Planning For Simple Two-Wheeled Robots, Ronald I. Greenberg, Jeffery M. Karp Jan 2018

Motion Planning For Simple Two-Wheeled Robots, Ronald I. Greenberg, Jeffery M. Karp

Ronald Greenberg

This paper considers various simple ways of navigating in a 2-dimensianal territory with a two-wheeled robot of a type typical in educational robotics. We determine shortest paths under various modes of operation and compare.

Go to article

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg Jan 2018

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg

Ronald Greenberg

This 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 this 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 Omega(n lg n) time. We also show that on a restricted version of the architecture, any algorithm requires Omega(n lg n) time in the worst case.

Go to article

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior 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), one can solve the problem 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 …

Go to article

Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg Jan 2018

Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg

Ronald Greenberg

This paper considers several variations of an optimization problem with potential applications in such areas as biomolecular sequence analysis and image processing. Given a sequence of items, each with a weight and a length, the goal is to find a subsequence of consecutive items of optimal value, where value is either total weight or total weight divided by total length. There may also be a specified lower and/or upper bound on the acceptable length of subsequences. This paper shows that all the variations of the problem are solvable in linear time and space even with non-uniform item lengths and divisible …

Go to article

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg Jan 2018

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Ronald Greenberg

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Go to article

Efficient Multi-Layer Channel Routing, Ronald I. Greenberg Jan 2018

Efficient Multi-Layer Channel Routing, Ronald I. Greenberg

Ronald Greenberg

No abstract provided.

Go to article

Ecs Evaluation Survey Instruments, Ronald I. Greenberg, Steven Mcgee Jan 2018

Ecs Evaluation Survey Instruments, Ronald I. Greenberg, Steven Mcgee

Ronald Greenberg

This is a compilation of several surveys used in conjunction with a large-scale implementation of the Exploring Computer Science Curriculum in high schools in the Chicago Public Schools: ECS student presurvey pp. 1--2, ECS student postsurvey pp. 3--4, teacher background survey pp. 5--11, teacher ECS workshop feedback form pp. 12--13, teacher ECS implementation survey pp. 14--24

Go to article

Evaluation Of The Impacts Computer Science Presentations, Ronald I. Greenberg Jan 2018

Evaluation Of The Impacts Computer Science Presentations, Ronald I. Greenberg

Ronald Greenberg

Recent computer science enrollments have shown positive trends. However, these trends are not evenly distributed by gender and race. Efforts to recruit underrepresented students should focus on providing information that demystifies the field of computer science. This paper reports on such an effort to inform underrepresented high school students about the field and its diversity. The results suggest that increasing awareness in an enjoyable format can increase student interest in pursuing computer science. These results can provide guidance about ways to encourage students to take high school computer science classes as motivation and preparation for college-level computer science.

Go to article

Finding A Maximum-Denisty Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Finding A Maximum-Denisty Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case …

Go to article

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg Jan 2018

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Ronald Greenberg

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.

Go to article

Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg Jan 2018

Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg

Ronald Greenberg

This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …

Go to article

Feasible Offset And Optimal Offset For General Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Feasible Offset And Optimal Offset For General Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

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 …

Go to article

An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan Jan 2018

An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan

Ronald Greenberg

This paper provides empirical comparison of the communication capabilities of two area-universal networks, the fat-tree and the fat-pyramid, to the popular mesh and hypercube networks for parallel computation. While area-universal networks have been proven capable of simulating, with modest slowdown, any computation of any other network of comparable area, prior work has generally left open the question of how area-universal networks compare to other networks in practice. Comparisons are performed using techniques of throughput and latency analysis that have previously been applied to k-ary n-cube networks and using various existing models to equate the hardware cost of the networks being …

Go to article

First Prev Next Last