bluuebunny/crossref_metadata_2025 huggingface dataset:
Tiny-sync
Authors: Yoon Suyoung , Veerarittiphan Chanchai , Sichitiu Mihail L.
Published: September 2007

Time synchronization is a fundamental middleware service for any distributed system. Wireless sensor networks make extensive use of synchronized time in many contexts (e.g., data fusion, TDMA schedules, synchronized sleep periods, etc.). We propose a time synchronization method relevant for wireless sensor networks. The solution features minimal complexity in network bandwidth, storage as well as processing, and can achieve good accuracy. Especially relevant for sensor networks, it also provides tight, deterministic bounds on offset and clock drift. A method for synchronizing the entire network is presented. The performance of the algorithm is analyzed theoretically and validated on a realistic testbed. The results show that the proposed algorithm outperforms existing algorithms in terms of precision and resource requirements.
Quantum cryptography
Authors: Bruss Dagmar , Erdélyi Gábor , Meyer Tim , Riege Tobias , Rothe Jörg
Published: September 2007

We survey some results in quantum cryptography. After a brief introduction to classical cryptography, we provide the quantum-mechanical background needed to present some fundamental protocols from quantum cryptography. In particular, we review quantum key distribution via the BB84 protocol and its security proof, as well as the related quantum bit commitment protocol and its proof of insecurity.
Optimized stratified sampling for approximate query processing
Authors: Chaudhuri Surajit , Das Gautam , Narasayya Vivek
Published: September 2007

The ability to approximately answer aggregation queries accurately and efficiently is of great benefit for decision support and data mining tools. In contrast to previous sampling-based studies, we treat the problem as an optimization problem where, given a workload of queries, we select a stratified random sample of the original data such that the error in answering the workload queries using the sample is minimized. A key novelty of our approach is that we can tailor the choice of samples to be robust, even for workloads that are “similar” but not necessarily identical to the given workload. Finally, our techniques recognize the importance of taking into account the variance in the data distribution in a principled manner. We show how our solution can be implemented on a database system, and present results of extensive experiments on Microsoft SQL Server that demonstrate the superior quality of our method compared to previous work.
Out-of-core coherent closed quasi-clique mining from large dense graph databases
Authors: Zeng Zhiping , Wang Jianyong , Zhou Lizhu , Karypis George
Published: September 2007

Due to the ability of graphs to represent more generic and more complicated relationships among different objects, graph mining has played a significant role in data mining, attracting increasing attention in the data mining community. In addition, frequent coherent subgraphs can provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databases has witnessed several applications and received considerable attention in the graph mining community recently. In this article, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the fact that the downward-closure property no longer holds. By fully exploring some properties of quasi-cliques, we propose several novel optimization techniques which can prune the unpromising and redundant subsearch spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of closed quasi-cliques only. Since large databases cannot be held in main memory, we also design an out-of-core solution with efficient index structures for mining coherent closed quasi-cliques from large dense graph databases. We call this Cocain*. Thorough performance study shows that Cocain* is very efficient and scalable for large dense graph databases.
Metamodel-based model conformance and multiview consistency checking
Authors: Paige Richard F. , Brooke Phillip J. , Ostroff Jonathan S.
Published: September 2007

Model-driven development, using languages such as UML and BON, often makes use of multiple diagrams (e.g., class and sequence diagrams) when modeling systems. These diagrams, presenting different views of a system of interest, may be inconsistent. A metamodel provides a unifying framework in which to ensure and check consistency, while at the same time providing the means to distinguish between valid and invalid models, that is, conformance. Two formal specifications of the metamodel for an object-oriented modeling language are presented, and it is shown how to use these specifications for model conformance and multiview consistency checking. Comparisons are made in terms of completeness and the level of automation each provide for checking multiview consistency and model conformance. The lessons learned from applying formal techniques to the problems of metamodeling, model conformance, and multiview consistency checking are summarized.
Importance sampling for sums of random variables with regularly varying tails
Authors: Dupuis Paul , Leder Kevin , Wang Hui
Published: September 2007

Importance sampling is a variance reduction technique for efficient estimation of rare-event probabilities by Monte Carlo. For random variables with heavy tails there is little consensus on how to choose the change of measure used in importance sampling. In this article we study dynamic importance sampling schemes for sums of independent and identically distributed random variables with regularly varying tails. The number of summands can be random but must be independent of the summands. For estimating the probability that the sum exceeds a given threshold, we explicitly identify a class of dynamic importance sampling algorithms with bounded relative errors. In fact, these schemes are nearly asymptotically optimal in the sense that the second moment of the corresponding importance sampling estimator can be made as close as desired to the minimal possible value.
Paraconsistent reasoning and preferential entailments by signed quantified Boolean formulae
Authors: Arieli Ofer
Published: September 2007

We introduce a uniform approach of representing a variety of
paraconsistent nonmonotonic formalisms by quantified Boolean
formulae (QBFs) in the context of multiple-valued logics. We show
that this framework provides a useful platform for capturing, in a
simple and natural way, a wide range of methods for preferential
reasoning. The outcome is a subtle approach to represent the
underlying formalisms, which induces a straightforward way to
compute the corresponding entailments: By incorporating
off-the-shelf QBF solvers it is possible to simulate within our
framework various kinds of preferential formalisms, among which are
Priest's logic LPm of reasoning with minimal inconsistency, Batens'
adaptive logic ACLuNs2, Besnard and Schaub's inference relation
&vbar;=

n

, a variety of formula-preferential
systems, some bilattice-based preferential relations (e.g.,
&vbar;=

I

1
and
&vbar;=

I

2
), and consequence
relations for reasoning with graded uncertainty, such as the
four-valued logic &vbar;=
4

c

.
Answering XML queries by means of data summaries
Authors: Baralis Elena , Garza Paolo , Quintarelli Elisa , Tanca Letizia
Published: September 2007

XML is a rather verbose representation of semistructured data, which may require huge amounts of storage space. We propose a summarized representation of XML data, based on the concept of instance pattern, which can both provide succinct information and be directly queried. The physical representation of instance patterns exploits itemsets or association rules to summarize the content of XML datasets. Instance patterns may be used for (possibly partially) answering queries, either when fast and approximate answers are required, or when the actual dataset is not available, for example, it is currently unreachable. Experiments on large XML documents show that instance patterns allow a significant reduction in storage space, while preserving almost entirely the completeness of the query result. Furthermore, they provide fast query answers and show good scalability on the size of the dataset, thus overcoming the document size limitation of most current XQuery engines.
A compiler cost model for speculative parallelization
Authors: Dou Jialin , Cintra Marcelo
Published: September 2007

Speculative parallelization is a technique that allows code sections that cannot be fully analyzed by the compiler to be aggressively executed in parallel. However, while speculative parallelization can potentially deliver significant speedups, several overheads associated with this technique can limit these speedups in practice. This paper proposes a novel compiler static cost model of speculative multithreaded execution that can be used to predict the resulting performance. This model attempts to predict the expected speedups, or slowdowns, of the candidate speculative sections based on the estimation of the combined runtime effects of various overheads, and taking into account the scheduling restrictions of most speculative execution environments. The model is based on estimating the likely execution duration of threads and considers all the possible permutations of these threads. This model also produces a quantitative estimate of the speedup, which is different from prior heuristics that only qualitatively estimate the benefits of speculative multithreaded execution. In previous work, a limited version of the framework was evaluated on a number of loops from a collection of SPEC benchmarks that suffer mainly from load imbalance and thread dispatch and commit overheads. In this work, an extended framework is also evaluated on loops that may suffer from data-dependence violations. Experimental results show that prediction accuracy is lower when loops with violations are included. Nevertheless, accuracy is still very high for a static model: the framework can identify, on average, 45% of the loops that cause slowdowns and, on average, 96% of the loops that lead to speedups; it predicts the speedups or slowdowns with an error of less than 20% for an average of 28% of the loops across the benchmarks and with an error of less than 50% for an average of 80% of the loops. Overall, the framework often outperforms, by as much as 25%, a naive approach that attempts to speculatively parallelize all the loops considered, and is able to curb the large slowdowns caused in many cases by this naive approach.
Optimal pants decompositions and shortest homotopic cycles on an orientable surface
Authors: Verdière Éric Colin De , Lazarus Francis
Published: September 2007

We consider the problem of finding a shortest cycle (freely) homotopic to a given simple cycle on a compact, orientable surface. For this purpose, we use a
pants decomposition
of the surface: a set of disjoint simple cycles that cut the surface into
pairs of pants
(spheres with three holes). We solve this problem in a framework where the cycles are closed walks on the vertex-edge graph of a combinatorial surface that may overlap but do not cross.

We give an algorithm that transforms an input pants decomposition into another homotopic pants decomposition that is
optimal
: each cycle is as short as possible in its homotopy class. As a consequence, finding a shortest cycle homotopic to a given simple cycle amounts to extending the cycle into a pants decomposition and to optimizing it: the resulting pants decomposition contains the desired cycle. We describe two algorithms for extending a cycle to a pants decomposition. All algorithms in this article are polynomial, assuming uniformity of the weights of the vertex-edge graph of the surface.
Periodicity and unbordered words
Authors: Harju Tero , Nowotka Dirk
Published: September 2007

The relationship between the length of a word and the maximum length of its unbordered factors is investigated in this article. Consider a finite word
w
of length
n
. We call a word
bordered
if it has a proper prefix, which is also a suffix of that word. Let μ(
w
) denote the maximum length of all unbordered factors of
w
, and let ∂(
w
) denote the period of
w
. Clearly, μ(
w
) ≤ ∂(
w
).

We establish that μ(
w
) = ∂(
w
), if
w
has an unbordered prefix of length μ(
w
) and
n
≥ 2μ(
w
) − 1. This bound is tight and solves the stronger version of an old conjecture by Duval [1983]. It follows from this result that, in general,
n
≥ 3μ(
w
) − 3 implies μ(
w
) = ∂(
w
), which gives an improved bound for the question raised by Ehrenfeucht and Silberger in 1979.
An efficient on-the-fly cycle collection
Authors: Paz Harel , Bacon David F. , Kolodner Elliot K. , Petrank Erez , Rajan V. T.
Published: September 2007

A reference-counting garbage collector cannot reclaim unreachable cyclic structures of objects. Therefore, reference-counting collectors either use a backup tracing collector infrequently, or employ a cycle collector to reclaim cyclic structures. We propose a new
concurrent
cycle collector, one that runs concurrently with the program threads, imposing negligible pauses (of around 1ms) on a multiprocessor.

Our new collector combines a state-of-the-art cycle collector [Bacon and Rajan 2001] with sliding-views collectors [Levanoni and Petrank 2001, 2006; Azatchi et al. 2003]. The use of sliding views for cycle collection yields two advantages. First, it drastically reduces the
number
of cycle candidates, which in turn drastically reduces the
work
required to record and trace these candidates. Consequentially, a large improvement in cycle collection efficiency is achieved. Second, it eliminates the theoretical termination problem that appeared in the earlier concurrent cycle collector. There, a rare race may delay the reclamation of an unreachable cyclic structure forever. The sliding-views cycle collector guarantees reclamation of all unreachable cyclic structures.

The proposed collector was implemented on the Jikes RVM and we provide measurements including a comparison between the use of backup tracing and the use of cycle collection with reference counting. To the best of our knowledge, such a comparison has not been reported before.
Efficient simulation of critical synchronous dataflow graphs
Authors: Hsu Chia-Jui , Ko Ming-Yung , Bhattacharyya Shuvra S. , Ramasubbu Suren , Pino José Luis
Published: September 2007

System-level modeling, simulation, and synthesis using electronic design automation (EDA) tools are key steps in the design process for communication and signal processing systems, and the synchronous dataflow (SDF) model of computation is widely used in EDA tools for these purposes. Behavioral representations of modern wireless communication systems typically result in
critical SDF graphs
: These consist of hundreds of components (or more) and involve complex intercomponent connections with highly
multirate
relationships (i.e., with large variations in average rates of data transfer or component execution across different subsystems). Simulating such systems using conventional SDF scheduling techniques generally leads to unacceptable simulation time and memory requirements on modern workstations and high-end PCs. In this article, we present a novel
simulation-oriented scheduler
(SOS) that strategically integrates several techniques for graph decomposition and SDF scheduling to provide effective, joint minimization of time and memory requirements for simulating critical SDF graphs. We have implemented SOS in the
advanced design system
(ADS) from Agilent Technologies. Our results from this implementation demonstrate large improvements in simulating real-world, large-scale, and highly multirate wireless communication systems (e.g., 3GPP, Bluetooth, 802.16e, CDMA 2000, XM radio, EDGE, and Digital TV).
A framework for heterogeneous specification and design of electronic embedded systems in SystemC
Authors: Herrera Fernando , Villar Eugenio
Published: September 2007

This work proposes a methodology which enables heterogeneous specification of complex, electronic systems in SystemC supporting the integration of components under different models of computation (MoCs). This feature is necessary in order to deal with the growing complexity, concurrency, and heterogeneity of electronic embedded systems. The specification methodology is based on the SystemC standard language. Nevertheless, the use of SystemC for heterogeneous system specification is not straightforward. The first problem to be addressed is the efficient and predictable mapping of untimed events required by abstract MoCs over the discrete-event MoC on which the SystemC simulation kernel is based. This mapping is essential in order to understand the simulation results provided by the SystemC model of those MoCs. The specification methodology proposes the set of rules and guidelines required by each specific MoC. Moreover, the methodology supports a smooth integration of several MoCs in the same system specification. A set of facilities is provided covering the deficiencies of the language. These facilities constitute the methodology-specific library called HetSC. The methodology and associated library have been demonstrated to be useful for the specification of complex, heterogeneous embedded systems supporting essential design tasks such as performance analysis and SW generation.
Efficient power modeling and software thermal sensing for runtime temperature monitoring
Authors: Wu Wei , Jin Lingling , Yang Jun , Liu Pu , Tan Sheldon X.-D.
Published: September 2007

The evolution of microprocessors has been hindered by increasing power consumption and heat dissipation on die. An excessive amount of heat creates reliability problems, reduces the lifetime of a processor, and elevates the cost of cooling and packaging considerably. It is therefore imperative to be able to monitor the temperature variations across the die in a timely and accurate manner.

Most current techniques rely on on-chip thermal sensors to report the temperature of the processor. Unfortunately, significant variation in chip temperature both spatially and temporally exposes the limitation of the sensors. We present a compensating approach to tracking chip temperature through an OS resident software module that generates live power and thermal profiles of the processor. We developed such a software thermal sensor (STS) in a Linux system with a Pentium 4 Northwood core. We employed highly efficient numerical methods in our model to minimize the overhead of temperature calculation. We also developed an efficient algorithm for functional unit power modeling. Our power and thermal models are calibrated and validated against on-chip sensor readings, thermal images of the Northwood heat spreader, and the thermometer measurements on the package. The resulting STS offers detailed power and temperature breakdowns of each functional unit at runtime, enabling more efficient online power and thermal monitoring and management at a higher level, such as the operating system.
HW-SW emulation framework for temperature-aware design in MPSoCs
Authors: Atienza David , Del Valle Pablo G. , Paci Giacomo , Poletti Francesco , Benini Luca , Micheli Giovanni De , Mendias Jose M. , Hermida Roman
Published: September 2007

New tendencies envisage multiprocessor systems-on-chips (MPSoCs) as a promising solution for the consumer electronics market. MPSoCs are complex to design, as they must execute multiple applications (games, video) while meeting additional design constraints (energy consumption, time-to-market). Moreover, the rise of temperature in the die for MPSoCs can seriously affect their final performance and reliability. In this article, we present a new hardware-software emulation framework that allows designers a complete exploration of the thermal behavior of final MPSoC designs early in the design flow. The proposed framework uses FPGA emulation as the key element to model hardware components of the considered MPSoC platform at multimegahertz speeds. It automatically extracts detailed system statistics that are used as input to our software thermal library running in a host computer. This library calculates at runtime the temperature of on-chip components, based on the collected statistics from the emulated system and final floorplan of the MPSoC. This enables fast testing of various thermal management techniques. Our results show speedups of three orders of magnitude compared to cycle-accurate MPSoC simulators.
Efficient and scalable compiler-directed energy optimization for realtime applications
Authors: Huang Po-Kuan , Ghiasi Soheil
Published: September 2007

With continuing shrinkage of technology feature sizes, the share of leakage in total energy consumption of digital systems continues to grow. Coordinated supply voltage and body bias throttling enables the compiler to better optimize the total energy consumption of the system in future technology nodes. We present a compilation technique that targets realtime applications running on embedded processors with combined dynamic voltage scaling (DVS) and adaptive body biasing (ABB) capabilities. Considering the delay and energy penalty of switching between operating modes of the processor, our compiler judiciously inserts mode-switch instructions in selected locations of the code and generates executable binary that is guaranteed to meet the deadline constraint. More importantly, our algorithm runs very fast and comes reasonably close to the theoretical limit of energy optimization using DVS+ABB. At 65nm technology, we improve the energy dissipation of the generated code by an average of 33.20% under deadline constraints. While our technique's improvement in energy dissipation over conventional DVS is marginal (6.91%) at 130nm, the average improvement continues to grow to 13.19%, 22.97%, and 33.21% for 90nm, 65nm, and 45nm technology nodes, respectively. Compared to a recent ILP-based competitor, we improve the runtime by more than three orders of magnitude, while producing improved results.
Asynchronous random sleeping for sensor networks
Authors: Hua Cunqing , Yum Tak-Shing Peter
Published: September 2007

Sleeping scheduling is a common energy-conservation solution for sensor networks. For application whereby coordination of sleeping among sensors is not possible or inconvenient, random sleeping is the only option. In this article, we study the asynchronous random sleeping(ARS) scheme whereby sensors (i) do not need to synchronize with each other, and (ii) do not need to coordinate their sleeping schedules. The stationary coverage probability and the expected coverage periods for ARS are derived. For surveillance application, we derive in addition the detection probability and detection delay distribution. The correctness of our results is validated through extensive simulations. We compare ARS with other synchronous and asynchronous sleeping scheduling algorithms and show that ARS offers better performance in terms of detection delay in the lower duty-cycle regime. We also conduct simulations to demonstrate that our results can be a good approximation for clock drifting case.
Distant voices
Authors: Rowell Laurie
Published: September 2007

Why does functional computer voice recognition always seem just out of reach?
Robot networks of internet destroyers
Authors: Treese Win
Published: September 2007

Imagine having a thousand robots, all under your control, scattered all around the world. Any time you want, you can command them to act, attacking any target. Your control of them is secret; you can choose the target or auction it off to the highest bidder. Most of the time, no one can trace the attack---after it is over, the robots go back into hiding, waiting for their next command.
An accurate nonuniform fourier transform for SPRITE magnetic resonance imaging data
Authors: Rioux J. , Halse M. , Aubanel E. , Balcom B. J. , Kaffanke J. , Romanzetti S. , Dierkes T. , Shah N. J.
Published: September 2007

A new algorithm is proposed for computing the discrete Fourier Transform (DFT) of purely phase encoded data acquired during Magnetic Resonance Imaging (MRI) experiments. These experiments use the SPRITE (Single Point Ramped Imaging with
T
1
Enhancement) method and multiple-point acquisition, sampling data in a nonuniform manner that prohibits reconstruction by fast Fourier transform. The chirp z-transform algorithm of Rabiner, Schafer, and Rader can be combined with phase corrections to compute the DFT of this data to extremely high accuracy. This algorithm outperforms the interpolation methods that are traditionally used to process nonuniform data, both in terms of execution time and in terms of accuracy as compared to the DFT.
Efficient compilation of a class of variational forms
Authors: Kirby Robert C. , Logg Anders
Published: September 2007

We investigate the compilation of general multilinear variational forms over affines simplices and prove a representation theorem for the representation of the element tensor (element stiffness matrix) as the contraction of a constant reference tensor and a geometry tensor that accounts for geometry and variable coefficients. Based on this representation theorem, we design an algorithm for efficient pretabulation of the reference tensor. The new algorithm has been implemented in the FEniCS Form Compiler (FFC) and improves on a previous loop-based implementation by several orders of magnitude, thus shortening compile-times and development cycles for users of FFC.
Graphics and the symbolization of ideas
Authors: Sparling George A. J.
Published: September 2007

I work in a very arcane area of mathematical physics. It begins with Einstein's theory of gravitation and adds in the ideas of Sir Roger Penrose.
pClock
Authors: Gulati Ajay , Merchant Arif , Varman Peter J.
Published: September 2007

Storage consolidation is becoming an attractive paradigm for data organization because of the economies of sharing and the ease of centralized management. However, sharing of resources is viable only if applications can be isolated from each other. This work targets the problem of providing performance guarantees to an application irrespective of the behavior of other workloads. Application requirements are represented in terms of the average throughput, latency and maximum burst size. Most earlier schemes only do weighted bandwidth allocation; schemes that provide control of latency either cannot handle bursts or penalize applications for their own prior behavior, such as using spare capacity.

Our algorithm
p
Clock is based on arrival curves that intuitively capture the bandwidth and burst requirements of applications. We show analytically that an application following its arrival curve never misses its deadline. We have implemented
p
Clock both in DiskSim and as a module in the Linux kernel 2.6. Our evaluation shows three important features of
p
Clock: (1) benefits over existing algorithms; (2) efficient performance isolation and burst handling; and (3) the ability to allocate spare capacity to either speed up some applications or to a background utility, such as backup.
p
Clock can be efficiently implemented in a system without much overhead.
Optimizing system configurations quickly by guessing at the performance
Authors: Osogami Takayuki , Kato Sei
Published: September 2007

The performance of a Web system can be greatly improved by tuning its configuration parameters. However, finding the optimal configuration has been a time-consuming task due to the long measurement time needed to evaluate the performance of a given configuration. We propose an algorithm, which we refer to as Quick Optimization via Guessing (QOG), that quickly selects one of nearly best configurations with high probability. The key ideas in QOG are (i) the measurement of a configuration is terminated as soon as the configuration is found to be suboptimal, and (ii) the performance of a configuration is guessed at based on the measured similar configurations, so that the better configurations are more likely to be measured before the others. If the performance of a good configuration has been measured, a poor configuration will be quickly found to be suboptimal with short measurement time. We apply QOG to optimizing the configuration of a real Web system, and find that QOG can drastically reduce the total measurement time needed to select the best configuration. Our experiments also illuminate several interesting properties of QOG specifically when it is applied to optimizing Web systems.
Managing energy-performance tradeoffs for multithreaded applications on multiprocessor architectures
Authors: Park Soyeon , Jiang Weihang , Zhou Yuanyuan , Adve Sarita
Published: September 2007

In modern computers, non-performance metrics such as energy consumption have become increasingly important, requiring tradeoff with performance. A recent work has proposed performance-guaranteed energy management, but it is designed specifically for sequential applications and cannot be used to a large class of multithreaded applications running on high end computers and data servers.

To address the above problem, this paper makes the first attempt to provide performance-guaranteed energy management for multithreaded applications on multiprocessor architectures. We first conduct a comprehensive study on the effects of energy adaptation on thread synchronizations and show that a multithreaded application suffers from not only local slowdowns due to energy adaptation, but also significant slowdowns propagated from other threads because of synchronization. Based on these findings, we design three Synchronization-Aware (SA) algorithms, LWT (Lock Waiting Time-based), CSL (Critical Section Length-based) and ODP (Operation Delay Propagation-based) algorithms, to estimate the energy adaptation-induced slowdowns on each thread. The local slowdowns are then combined across multiple threads via three aggregation methods (MAX, AVG and SUM) to estimate the overall application slowdown.

We evaluate our methods using a large multithreaded commercial application, IBM DB2 with industrial-strength online transaction processing (OLTP) workloads, and six SPLASH parallel scientific applications. Our experimental results show that LWT combined with the MAX aggregation method not only controls the performance slow down within the specified limits but also conserves the most energy.
Clustering and sharing incentives in BitTorrent systems
Authors: Legout Arnaud , Liogkas Nikitas , Kohler Eddie , Zhang Lixia
Published: September 2007

Peer-to-peer protocols play an increasingly instrumental role in Internet content distribution. It is therefore important to gain a complete understanding of how these protocols behave in practice and how their operating parameters affect overall system performance. This paper presents the first detailed experimental investigation of the peer selection strategy in the popular BitTorrent protocol. By observing more than 40 nodes in instrumented private torrents, we validate three protocol properties that, though believed to hold, have not been previously demonstrated experimentally: the clustering of similar-bandwidth peers, the effectiveness of BitTorrent's sharing incentives, and the peers' high uplink utilization. In addition, we observe that BitTorrent's modified choking algorithmin seed state provides uniform service to all peers, and that an underprovisioned initial seed leads to absence of peer clustering and less effective sharing incentives. Based on our results, we provide guidelines for seed provisioning by content providers, and discuss a tracker protocol extension that addresses an identified limitation of the protocol.
Broadening participation in computing
Authors: Peckham Joan , Harlow Lisa L. , Stuart David A. , Silver Barbara , Mederer Helen , Stephenson Peter D.
Published: September 2007

In this paper we survey the literature to identify the issues and challenges of broadening participation in computer science, and provide some suggestions to address these challenges. Our attention focuses on redefining the way we approach computing education so that we can successfully entice students to computing that have not traditionally participated, thereby promoting diversity and increasing the total numbers of computing professionals. Based on the literature review, we propose an
interactional
model from the social sciences to inform the way in which we might restructure and broaden the definition of computing and provide some examples of strategies that we have found to be successful in practice.
Second annual robotics summer camp for underrepresented students
Authors: Cannon Kelly R. , Panciera Katherine A. , Papanikolopoulos Nikolaos P.
Published: September 2007

The University of Minnesota Center for Distributed Robotics and the Digital Technology Center hosted the second annual Technology Day Camp, a week long camp targeting underrepresented students such as girls, African Americans, and Hispanics from the Twin Cities metro area. Students were surveyed prior to the camp revealing a strong proclivity towards math and science, but a resistance to the perceived lifestyle of computer scientists. With an emphasis on the college experience, building hardware, creating software, and interacting with robots, the camp implemented proposed changes from the previous year as well as new activities with a special emphasis on robotics. The successes and failures are discussed in an effort to provide insight for organizations hosting similar programs, new research questions are presented, and a materials list is provided.
A TDD approach to introducing students to embedded programming
Authors: Miller James , Smith Michael
Published: September 2007

Learning embedded programming is a highly demanding exercise. The beginner is bombarded with complexity from the start: embedded production based around a myriad of C++ constructs with low-level elements integrated onto ever more complicated processor architectures. The picture is further compounded by tool support having unfamiliar roles and appearances from previous student experiences. This demanding situation often has the student bewildered; seeking for "a crutch" or the simplest way forward regardless of the overall consequences. To control this potentially chaotic picture, the instructor needs to introduce devices to combat this complexity. We argue that test driven development (TDD) should become the instructor's principal weapon in this fight. Reasons for this belief combined with our, and the students', experiences with this novel approach are discussed.
Checking automatically the output of concurrent threads
Authors: Oechsle Rainer , Barzen Kay
Published: September 2007

Assessing automatically students' solutions to concurrent programming assignments by looking at the produced output is a crucial and error-prone task. On the one hand a student's program may coincidentally produce a correct output although the program is faulty; the program could also produce invalid output which does not happen to be observed even when the program is run several times. On the other hand the synchronization in a student's program may be too strong, leading to a situation where certain correct outputs can never be generated. This paper presents an approach for checking automatically the output of concurrent threads for correctness. The basic idea is that we provide special implementations of synchronization primitives like semaphores that use vector timestamps. Every output action of a thread is tagged by its vector timestamp. Therefore it can be decided whether two output actions are causally related (they can occur only in the order which was actually observed because of an underlying synchronization), or whether two output actions are not causally related, i.e. concurrent (they may happen in any order). The output of a student's program is represented as a graph. The correctness check consists of a comparison between the expected graph and the observed graph.
Computer assisted assessment of diagrams
Authors: Thomas Pete G. , Smith Neil , Waugh Kevin G.
Published: September 2007

In this paper, we describe an approach to the grading (marking) of graph-based diagrams. The work is an application of a framework for the computer interpretation of imprecise diagrams (which students produce in response to assessment questions). We describe the interpretation framework and how it has been applied in the domain of entity-relationship diagrams used in data modeling. In our approach to grading, student diagrams are compared to specimen solutions representing correct solutions to an assessment question. The comparison between a student diagram and a specimen solution diagram results in a matching of the two diagrams from which a grade is computed. The comparison matching is used to provide graphical feedback on the correctness of the student diagram. The approach has been applied to a test corpus of 394 diagrams produced in answer to an examination question with some good results: 91% of all automatically produced grades were within 0.5 of a mark of the human graders. However, when supertype-subtype associations are present, the performance drops to around 87%. The paper concludes with a discussion of some applications of the marker.
Using disruptive technology for explorative learning
Authors: Oliver Iain , Getchell Kristoffer , Miller Alan , Allison Colin
Published: September 2007

Computer Networking is the subject that enables us to build and understand the Internet which in turn lies at the heart of many social and economic transformations that are central to modern society. At the subject's core are the protocols for sending and receiving packets and reporting errors. Although it is a dynamic and naturally engaging subject there are significant barriers which make it difficult for a student to engage realistically with network protocols. These can be categorised as barriers of time, space and access. From the perspective of time, many of the interactions occur at timescales that are outside of the range of human perception; from the perspective of space, a student will be situated in one location which will often define their view of the network; from the perspective of access, interaction with network protocols is mediated through libraries provided by operating systems which in turn require the use of programming languages to manipulate. This paper advocates the use of disruptive technology, based on the PlanetLab overlay network to support explorative approaches to learning about Computer Networking.
Inclusive computer science education using a ready-made computer game framework
Authors: Distasio Joseph , Way Thomas
Published: September 2007

Leveraging the prevailing interest in computer games among college students, both for entertainment and as a possible career path, is a major reason for the increasing prevalence of computer game design courses in computer science curricula. Because implementing a computer game requires strong programming skills, game design courses are most often restricted to more advanced computer science students, yet real game design involves a diverse and creative team. This paper reports on a ready-made game design and experimentation framework, implemented in Java, which makes game programming more widely accessible. This framework, called Labyrinth, enables students at all programming skill levels to participate in computer game design. We describe the architecture of the framework, and discuss programming projects suitable for a wide variety of computer science courses, from capstone to non-major.
A framework for describing and comparing courses and curricula
Authors: Pedroni Michela , Oriol Manuel , Meyer Bertrand
Published: September 2007

Curriculum and course planning is a key step in developing quality educational programs, but current practices very often lack a systematic approach. This article addresses this issue by refining and expanding the concept of Testable, Reusable Unit of Cognition (Truc). The methodology allows modeling courses and verifying compliance of a given course to a given description. It also makes it possible to describe precisely what students have previously learned and, as a result, adapt the teaching to their specific needs. The article presents a case study of comparing a subset of two introductory programming textbooks and describes the application TrucStudio that supports the methodology.
Case-based instruction on the web for teaching software project management
Authors: Papadopoulos Pantelis M. , Demetriadis Stavros N. , Stamelos Ioannis G.
Published: September 2007

Software project management (SPM) is an ill-structured domain, where past experiences of project management can become valuable learning resources for novices. To support instruction in the domain, we have developed the eCASE-SPM Web environment, for engaging students in case-based instruction and help them develop SPM related problem solving skills. This work presents major design issues of the environment and initial research results regarding (a) a student-based evaluation, connecting also students' attitudes to their learning styles, and (b) the learning effectiveness of the environment, investigating the use of embedded question prompts as students' cognitive scaffolds. Results so far reveal interesting interactions between students' learning styles and their attitudes towards learning in the eCASE-SPM environment. Furthermore, there is strong indication that using question prompts may have beneficial effect on students' learning and problem solving abilities, although fading out of the scaffolding should be implemented to moderate students' workload.
Independent, synchronous and asynchronous an analysis of approaches to online concept formation
Authors: Bower Matt
Published: September 2007

This paper compares and contrasts three different approaches to pre-class concept formation in an online computing course. In the initial third of the semester students made individual responses to sets of weekly pre-class tutorial style questions. In the following four weeks a virtual classroom was used to facilitate the synchronous construction of group responses to the same type of activities. In the final third of semester a wiki was used to provide an asynchronous means of composing group responses to the pre-class tutorial questions. The different patterns of student contribution and interaction that resulted from each mode are described. Implications for concept formation specifically and learning generally are discussed.
Challenges with respect to the e-readiness of secondary school teachers in Kwazulu-Natal, South Africa
Authors: Govender Desmond Wesley , Maharaj Manoj
Published: September 2007

In this study the authors investigate the challenges facing the provincial department of education with respect to the e-Readiness of secondary school teachers in the Province of KwaZulu-Natal, South Africa. The study is based on a sample of the secondary schools in the Ethekwini Municipality. The results indicate that any ICT interventions by the provincial Department of Education are bound to fail unless other non-technological interventions are put into place first. We show that where the ICT interventions are needed the most, the teachers are least prepared to receive it. Thus we conclude that instead of making short-term political decisions, the Department must first embark on a medium to long term plan to first make the environment amenable for an ICT intervention. These would include large-scale school upgrading, teacher training and retention plans to keep experienced and qualified teachers within the schooling system.
Spatial skills and navigation of source code
Authors: Jones Sue Jane , Burnett Gary E.
Published: September 2007

Learning to program is a difficult process, and students that perform well in other subjects may not produce comparable results in programming. Evidence suggests that some programmers are inherently more skilled than others, and one individual difference that has been shown to be important is spatial ability. This cognitive characteristic is implicated in successful real-world navigation. It is also important for navigating within hypertext, and there is a growing recognition that it has a part to play in program comprehension and development, with navigation of source code considered similar to navigating in the real world. Little research has been carried out to study the navigational patterns of programmers with differing spatial skills. In this study, 24 students enrolled on a Masters in IT course at a University in the UK were given a code comprehension exercise. Various measures were made of time taken and movement around the code. Those with high spatial ability completed the task in shorter time, spent less time searching around deciding where to go next, and jumped more frequently within and between class files. Strong relations were also found between spatial ability and results in programming modules, with much weaker relations with non-programming modules. This paper discusses the implications of these results in relation to the accessibility of programming to learners with low spatial ability.
Studying our inclusive practices
Authors: Deibel Katherine
Published: September 2007

Students with disabilities can experience difficulty in receiving an education; inclusive education is an educational practice designed to ameliorate these problems. This paper presents the design for a study of the current inclusivepractices in computer science courses. Challenges in studying the experiences of disabled students are discussed, and a methodology using semi-structured interviews and grounded theory is developed to address these difficulties. A pilot study involving students taking their first computing courses is also described.
Scribbles
Authors: Martin Christopher James
Published: September 2007

Scribbles represents a light weight intuitive tool to support early collaborative software design. Collaboration is not well supported in many modern CASE (computer aided software engineering) environments making paper and white boards an attractive alternative. As a result of this, CASE tools tend to be more suited to documenting designs rather than assisting the generation of a design, meaning that early ideas may be lost. Scribbles uses shape recognition, to allow freehand manipulation of a hybrid Mind Map. This preserves the simplicity of paper or a whiteboard whilst adding the ability to capture early design ideas in a reusable way. This is a very lightweight modeling environment ideally suited to introducing students to Object Oriented Design.
Teaching AJAX in web-centric courses
Authors: Draganova Chrisina , Vassilev Vassil
Published: September 2007

Asynchronous JavaScript and XML (AJAX) is a web development technique for building responsive web applications behaving in a similar fashion to traditional desktop applications. This poster illustrates ideas for teaching the AJAX technique in web-centric courses based on the experience of implementing these ideas at London Metropolitan University and provides links to resources appropriate for use in laboratorial work.
Complexity of ambient intelligence in managerial work
Authors: Burea Vladimír , Čech Pavel
Published: September 2007

Recently, ambient intelligence a vision of information society of the future has become the subject of attention of many theorists and practitioners. The achievement of ambient intelligence postulates an adequate shift in thinking. The shift in thinking concerns also managerial work. The paper presents on field experience on how to test the meaningfulness of teaching systems thinking for managers.
How will future learning work in the third dimension?
Authors: Leidl Martin , Rößling Guido
Published: September 2007

In this paper, we describe the possibilities of virtual worlds for educational purposes, and justify the need for special design and usability concepts for learning applications within these worlds.