Physical Sciences and Mathematics Commons^™

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 …

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.

Efficient Multi-Layer Channel Routing, Ronald I. Greenberg

Ronald Greenberg

No abstract provided.

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

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.

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 …

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.

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 …

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 …

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 …

An Improved Analytical Model For Wormhole Routed Networks With Application To Butterfly Fat-Trees, Ronald I. Greenberg, Lee Guan

Ronald Greenberg

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.

Does A Taste Of Computing Increase Computer Science Enrollment?, Steven Mcgee, Randi Mcgee-Tekula, Jennifer Duck, Ronald I. Greenberg, Lucia Dettori, Dale F. Reed, Brenda Wilkerson, Don Yanek, Andrew Rasmussen, Gail Chapman

Ronald Greenberg

The Exploring Computer Science (ECS) high school curriculum is designed to foster deep engagement through equitable inquiry around computer science concepts. We have shown that students find ECS courses personally relevant, are increasing their expectancies of success and perceived value for the field of computer science, and are more likely to take another computing course.

An Empirical Comparison Of Networks And Routing Strategies For Parallel Computation, Ronald I. Greenberg, Lee Guan

Ronald Greenberg

This paper compares message routing capabilities of important networks proposed for general-purpose parallel computing. All the networks have been proven to have some type of universality property, i.e., an ability to simulate other networks of comparable cost with modest slowdown, using appropriate cost and communication models. But in this paper we seek an empirical comparison of communication capability under typical direct use rather than an analysis of worst-case results for simulating message traffic of another network.

An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg

Ronald Greenberg

I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.

A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh

Ronald Greenberg

This paper presents a CAD tool, SystSim, to ease the design of systolic systems. Given a high-level, functional description of processors, and a high-level description of their interconnection, SystSim will perform simulations and provide graphical output. SystSim will also perform transformations such as retiming, which eases use of the methodology of Leiserson and Saxe of designing a system with broadcasting and then obtaining a systolic system through retiming.

Does A Taste Of Computing Increase Computer Science Enrollment?, Steven Mcgee, Randi Mcgee-Tekula, Jennifer Duck, Taylor White, Ronald I. Greenberg, Lucia Dettori, Dale F. Reed, Brenda Wilkerson, Don Yanek, Andrew Rasmussen, Gail Chapman

Ronald Greenberg

This study investigated the impact of the Exploring Computer Science (ECS) program on the likelihood that students of all races and gender would pursue further computer science coursework in high school. ECS is designed to foster deep engagement through equitable inquiry around computer science concepts. If the course provides a meaningful and relevant experience, it will increase students' expectancies of success as well as increase their perceived value for the field of computer science. Using survey research, we sought to measure whether the relevance of students' course experiences influenced their expectancies and value and whether those attitudes predicted whether students …

An Interval Arithmetic Newton Method For Solving Systems Of Nonlinear Equations, Ronald I. Greenberg, Eldon R. Hansen

Ronald Greenberg

We introduce an interval Newton method for bounding solutions of systems of nonlinear equations. It entails three sub-algorithms. The first is a Gauss-Seidel type step. The second is a real (non-interval) Newton iteration. The third solves the linearized equations by elimination. We explain why each sub-algorithm is desirable and how they fit together to provide solutions in as little as 1/3 to 1/4 the time required by a commonly used method due to Krawczyk.

The Graph Database: Jack Of All Trades Or Just Not Sql?, George F. Hurlburt, Maria R. Lee, George K. Thiruvathukal

George K. Thiruvathukal

This special issue of IT Professional focuses on the graph database. The graph database, a relatively new phenomenon, is well suited to the burgeoning information era in which we are increasingly becoming immersed. Here, the guest editors briefly explain how a graph database works, its relation to the relational database management system (RDBMS), and its quantitative and qualitative pros and cons, including how graph databases can be harnessed in a hybrid environment. They also survey the excellent articles submitted for this special issue.

Examining The Use Of Amazon’S Mechanical Turk For Edge Extraction Of The Occlusal Surface Of Fossilized Bovid Teeth, George K. Thiruvathukal, Gregory J. Matthews, Maxwell P. Luetkemeier, Juliet K. Brophy

George K. Thiruvathukal

In order to reconstruct environments associated with Plio-Pleistocene hominins in southern Africa, researchers frequently rely upon the animals associated with the hominins, in particular, animals in the Family Bovidae. Bovids in southern Africa are typically identified by their teeth. However, identifying the taxon of a bovid tooth is challenging due to various biasing factors. Furthermore, inaccurate identification of fossil bovids can have significant consequences on the reconstructed paleoenvironment. Recent research on the classification of bovid fossil teeth has relied on using elliptical Fourier analysis to summarize the shape of the outline of the occlusal surface of the tooth and the …

Reproducible Research For Computing In Science & Engineering, Lorena A. Barba, George K. Thiruvathukal

George K. Thiruvathukal

The editors of the new track for reproducible research outline the parameters for future peer review, submission, and access, highlighting the magazine’s previous work in this field and some of the challenges still to come.

Computer Science And Cultural History: A Dialogue, David B. Dennis, George K. Thiruvathukal

George K. Thiruvathukal

No abstract provided.

Segmenting Human Trajectory Data By Movement States While Addressing Signal Loss And Signal Noise, Sungsoon Hwang, Cynthia Vandemark, Navdeep Dhatt, Sai Yalla, Ryan Crews

Sungsoon Hwang

The Evolution Of Requirements Practices In Software Startups, Catarina Gralha, Daniela Damian, Anthony Wasserman, Miguel Goulão, João Araújo

Tony Wasserman

Stacked Generalization: An Introduction To Super Learning, Ashley Naimi, Laura Balzer

Laura B. Balzer

Informing Students About Academic Integrity In Programming., Simple Simon, Judy Sheard, Michael Morgan, Andrew Petersen, Amber Settle, Jane Sinclair

Amber Settle

Artificial Intelligence And Role-Reversible Judgment, Stephen E. Henderson, Kiel Brennan-Marquez

Stephen E Henderson

Amilcar Aponte.Jpg, Amilcar Aponte

Amilcar Aponte

Blockchain And Smart Contracts: The Missing Link In Copyright Licensing?, Balazs Bodo, Daniel Gervais, Joao Pedro Quintais

Daniel J Gervais

Tactful Inattention: Erving Goffman, Privacy In The Digital Age, And The Virtue Of Averting One's Eyes, Elizabeth De Armond

Elizabeth De Armond

No abstract provided.