DNA fragment assembly using a grid-based genetic algorithm

In this paper we propose a genetic algorithm (GA) for solving the DNA fragment assembly problem in a computational grid. The algorithm, which is named GrEA, is a steady-state GA which uses a panmitic population, and it is based on computing parallel function evaluations in an asynchronous way. We have implemented GrEA on top of the Condor system, and we have used it to solve the DNA assembly problem. This is an NP-hard combinatorial optimization problem which is growing in importance and complexity as more research centers become involved on sequencing new genomes. While previous works on this problem have usually faced 30 K base pairs (bps) long instances, we have tackled here a 77 K bps long one to show how a grid system can move research forward. After analyzing the basic grid algorithm, we have studied the use of an improvement method to still enhance its scalability. Then, by using a grid composed of up to 150 computers, we have achieved time reductions from tens of days down to a few hours, and we have obtained near optimal solutions when solving the 77 K bps long instance (773 fragments). We conclude that our proposal is a promising approach to take advantage of a grid system to solve large DNA fragment assembly problem instances and also to learn more about grid metaheuristics as a new class of algorithms for really challenging problems.     

Electronic Security is a Continuous Process

The use of email and the Internet has added a new conduit to market for business, and some organizations have gained significant commercial advantage from using the Internet. Before computers were connected to the Internet, it was relatively easy to have effective security measures in place to protect the electronic files on individual computers or systems. However, now computers have become communication systems as well as working tools, the risks attendant upon this new breed of ‘communications working platform’ have increased substantially.     

Challenging minds? Students’ perceptions of computer-based World Class Tests of problem solving

World Class Arena is a British government initiative to assess and develop the skills of gifted and talented children. Part of the strategy is to use computer-based tests. Students attempt tasks that require them to engage in higher-order problem solving, often in interactive, realistic, contexts. This study reports observations and interviews in schools. Students found tasks engaging and motivating, despite the unfamiliarity of the problem types and the challenging nature of the items. Students had no problems working with computers. They were sometimes distracted by attractive graphics, and sometimes used poor heuristics when attempting tasks. The study provides evidence that a computer environment can provide new ways to assess the problem solving skills of highly able students.     

The strategies and interactions of young children in LOGO tasks

Abstract  The present study analysed the strategies and interactions of 60 7-year-old children working on LOGO tasks in gender pairs (girls, boys and boy/ girls). The results revealed that initially there were significant differences on some performance variables, based on gender, in one of the tasks. However, these disappeared when the task was changed to one with a focus on accuracy. By the end of the study differences in performance were found to be associated with the application of higher order strategies for problem-solving. The research investigated the nature of the early differences between the groups by examining the strategies and interactions of the pairs of children. The study highlights the importance of considering both the type of task and performance over a reasonable period of time when describing the nature and extent of young children's learning when problem solving in a novel environment.     

Vectorization of a generalized procedure for theorem proving inpropositional logic on vector computers

Vectorization techniques for solving the theorem-proving problem in propositional logic on vector computers is presented. To take advantage of vector processing, the rules used in the deduction process are first generalized by considering more than one literal at a time. The soundness of the generalized rules is proved. The vectorized representation of the problem and algorithms based on the generalized rules is proposed. Experiments conducted on vector computers show that the vectorized procedure is effective     

From order to disorder: the role of computer-based electronics projects on fostering of higher-order cognitive skills

This research explored learning and thinking processes enhanced by integrating computers in secondary schools electronics projects. Electronics studies provide a sophisticated learning environment, where computers are simultaneously part of the subject matter learned (Technology Education), and a means for enhancing teaching and learning (Educational Technology), as seen in any other area of education. The follow-up on fifty students working on their final projects showed that students working on computer-based electronics projects tend to adopt flexible strategies, such as creating new ideas, risk-taking, improvisation, using trial and error methods for problem solving, and rapid transition from one design to another. In contrast, students working on non-computerized electronics projects are more likely to progress along a linear path: planning, construction, and troubleshooting. Computerized projects also promote the transfer of knowledge between students, and joint development of ideas. Students who exercise freedom in their project do not express the same independence in their documentation, and prepare portfolios that show how they, supposedly, developed their system in an orderly manner. It is important to educate students, and teachers, that creative design and problem solving requires a balance between openness, flexibility, and intuition, on the one hand, and systematic investigation, discipline, and hard work, on the other hand.     

A Quantitative/Method of Speed Comparison Between Analog/Hybrid and Digital Computers

For many years it has been claimed that analog and hybrid computers have a sizeable speed advantage over digital computers in the solution of differential equations. This speed advantage has, in fact, been documented for a number of specific studies, where direct comparisons with all-digital solutions have shown reduced run times and resulting cost savings using analog or hybrid computers. The purpose of this paper is to present a quantitative method of speed comparison that is quite general and allows direct speed comparisons between specific analog and digital computers. The method is based on previous reports written by the authors.^1,2Ability to make such speed comparisons is particularly important at this time when faster and faster digital computers are being marketed at generally lower prices.     

Comparative analysis of Palm and wearable computers for Participatory Simulations

Abstract Recent educational computer‐based technologies have offered promising lines of research that promote social constructivist learning goals, develop skills required to operate in a knowledge‐based economy ( Roschelle et al. 2000 ), and enable more authentic science‐like problem‐solving. In our research programme, we have been interested in combining these aims for curricular reform in school science by developing innovative and progressive hand‐held and wearable computational learning tools. This paper reports on one such line of research in which the learning outcomes of two distinct technological platforms (wearable computers and Palm hand‐helds) are compared using the same pedagogical strategy of Participatory Simulations. Participatory Simulations use small wearable or hand‐held computers to engage participants in simulations that enable inquiry and experimentation ( Colella 2000 ) allowing students to act out the simulation themselves. The study showed that the newer and more easily distributable version of Participatory Simulations on Palms was equally as capable as the original Tag‐based simulations in engaging students collaboratively in a complex problem‐solving task. We feel that this robust and inexpensive technology holds great promise for promoting collaborative learning as teachers struggle to find authentic ways to integrate technology into the classroom in addition to engaging and motivating students to learn science.     

The impact of LOGO on gifted children's achievement and creativity

It was hypothesised that problem solving via the Arabic logo programming environment would enhance gifted children's mathematics achievement and their creativity as measured by their performance on Torrance Tests of Creative Thinking (TTCT) and Mathematical Skills Assessment (MSA). The study findings extend previous research by indicating that problem solving via the LOGO programming environment can enhance mathematics achievement and creativity in figural, as well as verbal, domains. The evaluation of a large number of previous studies on the enhancement of creativity concluded that many of these studies have a positive effect. An implication is that computer environments may offer appropriate special provisions to meet the special needs of gifted children. In addition, this experiment provided some evidence that if gifted children work in pairs the need for teacher intervention to motivate the children is decreased. Also, if gifted children choose their own goals this increases their motivation and task commitment but might also restrict the range of mathematical ideas used.     

A Latency-Aware Partitioning Method for Distributed Virtual Environment Systems

Distributed virtual environment (DVE) systems allow multiple users working on different client computer's interconnected through different networks to interact in a shared virtual world. In these systems, latency is crucial for providing an acceptable quality of service (QoS), since it determines how fast client computers are reported about changes in the shared virtual scene produced by other client computers. This paper presents in a unified manner a partitioning approach for providing a latency below a threshold to the maximum number of users as possible in DVE systems. This partitioning approach searches the assignment of avatars, which represents the best trade-off among system latency, system throughput, and partitioning efficiency when solving the partitioning problem. Evaluation results show that the proposed approach not only maximizes system throughput, but also allows the system to satisfy, if possible, any specific latency requirement needed for providing QoS. This improvement is achieved without decreasing either image resolution or quality of animation, and it can be used together with other techniques already proposed. Therefore, it can contribute to provide QoS in DVEs.     

Triangulating molecular surfaces over a LAN of GPU-enabled computers

Standalone GPU-enabled computers are adequate to triangulate and rendering molecular datasets with some tens of thousands of atoms at most. But, a standalone GPU-enabled computer has a limited capacity to host programable graphics cards, which in turn have also their constraints in terms of memory space. Thus, in spite of the huge memory space made available and the tremendous processing power of the current GPU-based graphics cards, there remains a scalability problem when it is necessary to triangulate and render big molecules with hundreds of thousands to millions of atoms. In order to overcome this scalability problem we use an OpenMPI–OpenMP–CUDA solution that runs on a loosely-coupled GPU cluster over a LAN (Local Area Network). More specifically, we propose a fast, scalable, parallel triangulation algorithm for molecular surfaces that takes advantage of multicore processors of CPUs and GPUs available over a local network, with each CPU core working as the master of a single GPU. The main contribution of this paper is that likely introduces the first marching cubes algorithm that triangulates molecular surfaces on CUDA devices over a network of GPU-enabled computers.     

Children's posture and muscle activity at different computer display heights and during paper information technology use

OBJECTIVE: The 3-D posture and muscle activity in the neck and upper limb were assessed in children using high-, mid-, and book-level displays, which correspond to working conditions frequently observed when children interact with computers or books and paper. BACKGROUND: The 3-D posture and muscle activity of children reading and inputting data with computers and paper had not been previously assessed. METHODS: Twenty-four children aged 10 to 12 years and of normal height performed an interactive task involving reading from a book and writing on paper or reading from a computer display and inputting data using a mouse and keyboard. RESULTS: Head and neck flexion increased as the visual target was lowered. The high display resulted in mainly upper cervical relative extension, and the book display resulted in both upper and lower cervical flexion. The book condition resulted in greater cervical erector spinae and upper trapezius activity than did the mid and high conditions. CONCLUSION: The data suggest that a mid-level display may be more appropriate for children than a high display (e.g., when the display is placed on top of the central processing unit). The mid display also results in a more upright and symmetrical posture and lower mean muscle activity than does working with books and paper flat on the desk. APPLICATION: This study provides short-term laboratory study evidence for the formulation of guidelines for workstation design and adjustment for children. Use of computers by children is increasing, yet ergonomic guidelines lag behind those for adults.     

Heterogeneous Distribution of Computations Solving Linear Algebra Problems on Networks of Heterogeneous Computers

This paper presents and analyzes two different strategies of heterogeneous distribution of computations solving dense linear algebra problems on heterogeneous networks of computers. The first strategy is based on heterogeneous distribution of processes over processors and homogeneous block cyclic distribution of data over the processes. The second is based on homogeneous distribution of processes over processors and heterogeneous block cyclic distribution of data over the processes. Both strategies were implemented in the mpC language—a dedicated parallel extension of ANSI C for efficient and portable programming of heterogeneous networks of computers. The first strategy was implemented using calls to ScaLAPACK; the second strategy was implemented with calls to LAPACK and BLAS. Cholesky factorization on a heterogeneous network of workstations is used to demonstrate that the heterogeneous distributions have an advantage over the traditional homogeneous distribution.     

Concurrent Programming Technologies and Techniques

Intensive use of computer experiments in modern science introduces qualitative changes into experimental resources. This implies the change in techniques used to solve relevant problems. An analysis of technological chains (from the problem statement to its solution) shows that often a particular problem can be solved in a variety of ways with the use of modern multiprocessor computers, which are also called supercomputers. The multiplicity of approaches to solving a problem requires that researches possess certain skills in using supercomputers. It is difficult for novice users of multiprocessor computers to find bearings when developing software for solving applied problems. The practice shows that main difficulties reveal themselves when it is required to develop portable and efficient parallel software. This is because tools that facilitate the development and provide full access to debugging information have yet to be elaborated. Actually, the problem is in the absence of standards for development and debugging tools for supercomputers, which is explained by the fact that computer science is yet young. For the same reason, no logically complete basic texts for concurrent programming courses for novices are available. On the basis of Russian-language literature, an attempt is made at setting up beacons that mark certain common and promising technologies in using supercomputers. The emphasis is made on problems encountered by programmers when solving applied problems with the use of supercomputers. The development of multiprocessor computers is closely related to concurrent programming technologies, both universal and oriented to specific supercomputer architectures. By programming technology, i.e., by memory management, we mean the use of tools designed for managing a particular computer system. It should be noted that when developing software for supercomputers (both management software and programs for solving applied problems), one must pay special attention to programming technique, i.e., to designing the logical architecture of a program. This implies the development and extending parallelizing algorithms, which enhances the efficiency of execution on multiprocessor computers. This review was compiled on the basis of publications in Russian journals and in the Russian Internet zone.     

A multi-model algorithm for the cost-oriented design of Internet-based systems

The selection of a cost-minimizing combination of hardware and network components of Internet-based systems to satisfy organizational requirements is a complex design problem with multiple degrees of freedom. Decisions must be made on how to distribute the overall computing load onto multiple computers, where to locate computers and how to take advantage of legacy components. The corresponding optimization problem not only embeds the structure of NP-hard problems, but also represents a challenge with a well-structured heuristic approach.A scientific approach has been rarely applied to cost minimization and a rigorous methodological support to cost issues of the design of Internet-based distributed systems is still lacking. The methodological contribution of this paper is the representation of complex design issues as a set of four intertwined cost-minimization sub-problems: two set-partitionings, a set-packing and a min k-cut with a non-linear objective function. Optimization is accomplished by sequentially solving these sub-problems with a heuristic approach and tuning their solution with a local-search approach. Results indicate that decomposition significantly reduces optimization time and solutions have also lower costs than those identified without prior decomposition (20-60%). Cost reductions considerably grow (25-70%) when methodological outputs are compared with practitioners’ solutions.     

基于PVM的稠密线性方程组网上并行求解

将求解线性方程组的Gauss-Jordan消去法与Gauss列主元消去法结合起来,提出了利用并行计算支撑软件PVM在局域网上高效并行求解稠密线性方程组的算法.该算法处理机间的通信开销较少,实现了负载平衡和各处理机间的全并行工作.用1～24台桌面PC机按两种网络布局方式连接成的局域网,在PVM3.4 on Windows2000、VC 6.0并行计算平台上编程对该算法进行了数值试验,得到了正确的结果.     

Code talk: Student discourse and participation with networked handhelds

This study explores the potential of networked handheld computers to support collaborative problem solving in small groups. Drawing on data from a middle school mathematics classroom equipped with a wireless handheld network, I argue that the sharing of mathematical objects through interactive devices broadens the ‘bandwidth’ of classroom collaboration, expanding the range of participatory forms through which students might contribute to the work of a group and enhance their own learning. The analysis focuses on the participation strategies of those students in two focus groups who were most able to demonstrate posttest score gains from relatively low scores on a pretest. In particular, the device network provided those students with a set of collective, dynamic objects through which they supplemented and coordinated discursive forms of participation in the joint work of their respective groups.     

Improving quality of graph partitioning using multi-level optimization

Programming and Computer Software - Graph partitioning is required for solving tasks on graphs that need to be distributed over disks or computers. This problem is well studied, but the majority of...     

On the hardness of solving edge matching puzzles as SAT or CSP problems

Edge matching puzzles have been amongst us for a long time now and traditionally they have been considered, both, a children’s game and an interesting mathematical divertimento. Their main characteristics have already been studied, and their worst-case complexity has been properly classified as a NP-complete problem. It is in recent times, specially after being used as the problem behind a money-prized contest, with a prize of 2US$ million for the first solver, that edge matching puzzles have attracted mainstream attention from wider audiences, including, of course, computer science people working on solving hard problems. We consider these competitions as an interesting opportunity to showcase SAT/CSP solving techniques when confronted to a real world problem to a broad audience, a part of the intrinsic, i.e. monetary, interest of such a contest. This article studies the NP-complete problem known as edge matching puzzle using SAT and CSP approaches for solving it. We will focus on providing, first and foremost, a theoretical framework, including a generalized definition of the problem. We will design and show algorithms for easy and fast problem instances generation, generators with easily tunable hardness. Afterwards we will provide with SAT and CSP models for the problems and we will study problem complexity, both typical case and worst-case complexity. We will also provide some specially crafted heuristics that result in a boost in solving time and study which is the effect of such heuristics.     

Cognitive strategies observed during problem solving with LOGO

Abstract The present paper is devoted to a clinical preliminary analysis of the strategies used during one school year by 280 9 to 12 year olds, working in pairs and engaged in LOGO related problem solving activites. The data are grouped as a function of the type of strategies used by the pupils for a given problem and these strategies are defined as a function of the complexity level of the LOGO procedures created and measured on the basis of a hierarchy based upon actual observations. The types of solving processes and the types of mistakes most often encountered are also analysed. The evolution of the strategies used by different groups are compared. All these data show the relevance of a multilinear and contextual vision of problem solving strategies as opposed to the rigid vision described by some authors. The results presented here are especially relevant for teachers engaged in remedial activities.