This paper investigates what students understand about algorithm efficiency before receiving any formal instruction on the topic. We gave students a challenging search problem and two solutions, then asked them to ide...
详细信息
ISBN:
(纸本)9781605586151
This paper investigates what students understand about algorithm efficiency before receiving any formal instruction on the topic. We gave students a challenging search problem and two solutions, then asked them to identify the more efficient solution and to justify their choice. Many students did not use the standard worst-case analysis of algorithms;rather they chose other metrics, including average-case, better for more cases, better in all cases, one algorithm being more correct, and better for real-world scenarios. Students were much more likely to choose the correct algorithm when they were asked to trace the algorithms on specific examples;this was true even if they traced the algorithms incorrectly.
We describe a prototype of RRTS (Recurrence Relation Tutorial System), a tool for Students to use to practice solving homogeneous and non-homogeneous recurrence relations, both linear and divide-and-conquer, that aris...
详细信息
ISBN:
(纸本)9781595936103
We describe a prototype of RRTS (Recurrence Relation Tutorial System), a tool for Students to use to practice solving homogeneous and non-homogeneous recurrence relations, both linear and divide-and-conquer, that arise in algorithm analysis.
Dynamic spectrum access (DSA) supporting opportunistic transmission without extra spectrum bandwidth is attractive for future wireless communication. To facilitate such DSA system, a power-efficient (green) communicat...
详细信息
ISBN:
(纸本)9781424480166
Dynamic spectrum access (DSA) supporting opportunistic transmission without extra spectrum bandwidth is attractive for future wireless communication. To facilitate such DSA system, a power-efficient (green) communication processor is needed to support extremely high speed operation on a power-limited mobile device. Traditional general-purpose and digital signal processors are unable to simultaneously satisfy the processing speed and power efficiency for DSA systems. By exploiting critical parallelism and data exchange patterns based on communication algorithms inside a green processor, we successfully develop green SDR based communications processor for DSA that can be reconfigured to multiple system operation. We verify this novel architecture in TSMC 0.13 mu m CMOS process and demonstrate advantages simultaneously in performance and power efficiency.
This paper decomposes the algorithmic parameters that affect the accuracy and parallel run times of mean shift segmentation. Following Comaniciu and Meer [1], rather than perform calculations in the feature space of t...
详细信息
ISBN:
(纸本)9781479970612
This paper decomposes the algorithmic parameters that affect the accuracy and parallel run times of mean shift segmentation. Following Comaniciu and Meer [1], rather than perform calculations in the feature space of the image, the joint spatial-range domain is represented by the image space, with feature space information associated with each point. We report parallel speedup and segmentation accuracy using a standardised segmentation dataset and the Probabilistic Rand index (PRI) accuracy measure. Changes to the algorithmic parameters are analysed and a sweet spot between PRI and run time is found. Using a range window radius of 20, spatial window radius of 10 and threshold of 50, the PRI is improved by 0.17, an increase of 34% which is comparable to state of the art. Mean shift clustering run time is reduced by 97% with parallelism, a speedup of 32 on a 64-core CPU.
Chessboard cryptalgorithm is an algorithm to encrypt N bit binary data using a key of size N. It provides unique mappings for each key and scrambles the sequence using an approach similar to the movement of the Queen ...
详细信息
ISBN:
(纸本)9781538637852
Chessboard cryptalgorithm is an algorithm to encrypt N bit binary data using a key of size N. It provides unique mappings for each key and scrambles the sequence using an approach similar to the movement of the Queen on the chessboard. An important property is that the function for encryption and decryption is the same and not inverse as in typical cryptalgorithms. The number of combinations that can be generated is large and therefore to an extent, it protects against the brute force approach.
File sharing is a very popular service provided by peer-to-peer (P2P) networks. In a P2P file-sharing network, users share files and issue queries to the network to find the locations of the riles residing at other pe...
详细信息
ISBN:
(纸本)078037553X
File sharing is a very popular service provided by peer-to-peer (P2P) networks. In a P2P file-sharing network, users share files and issue queries to the network to find the locations of the riles residing at other peer nodes. Due to factors such as large user base and use of query broadcast protocols, each node in the network receives many search queries every second. Recently network developers have incorporated proxy-enabled peers, or supernodes, which are designed to enhance scalability by providing indexing services to nodes on slower network connections. Typically, supernodes build a vector or multi-index of all the filenames of the shared files stored on other (slower) peers nodes connected to them. In this paper we consider a new model whereby the index tables of the individual nodes are merged into a single data structure stored by the supermode. We analyze this new model in relation to the standard vectorized data structure. We compare the performance of these supernode indexing algorithms and provide a theoretical analysis that is asymptotic and probabilistic in nature. However, there are several significant constant factors that the theory does not account for, and which in practice are important for designing an optimal system solution. We report herein on a series of simulation experiments which provide 1) verification of the asymptotic analysis of the formal framework, and 2) tools to determine the magnitude of the constant factors involved in the performance analysis. Our general conclusion is that when the query rate exceeds the rate of data updates, the new merged model is preferable to the vector model. However, the details of our analysis allow us to consider combinations of several parameters, and thereby enable the design of optimal indexing schemes via the incorporation of measurements of the parameters of particular applications.
We study three different Hoare logics for reasoning about time bounds of imperative programs and formalize them in Isabelle/HOL: a classical Hoare like logic due to Nielson, a logic with potentials due to Carbonneaux ...
详细信息
ISBN:
(纸本)9783319899602;9783319899596
We study three different Hoare logics for reasoning about time bounds of imperative programs and formalize them in Isabelle/HOL: a classical Hoare like logic due to Nielson, a logic with potentials due to Carbonneaux et al. and a separation logic following work by Atkey, Chaguerand and Pottier. These logics are formally shown to be sound and complete. Verification condition generators are developed and are shown sound and complete too. We also consider variants of the systems where we abstract from multiplicative constants in the running time bounds, thus supporting a big-O style of reasoning. Finally we compare the expressive power of the three systems.
The great challenge in parallel computing is to make a task of programming parallel machines easy while not sacrificing the efficiency of target code. One of the successful methodologies is to start from a high-level ...
详细信息
ISBN:
(纸本)0818680679
The great challenge in parallel computing is to make a task of programming parallel machines easy while not sacrificing the efficiency of target code. One of the successful methodologies is to start from a high-level specification of the functional behaviour of a program by applying a sequence of optimizing transformations tuned for a particular architecture to generate a specification of the operational behaviour of a parallel program. We believe that visualization is an excellent way to bring this methodology to a wider programming community. In this paper we describe an interactive visual system which integrates 3D graphics, animation, and direct manipulation techniques into parallel programming environment.
The main idea of Optimized Selection Sort algorithm (OSSA) is based on the already existing selection sort algorithm, with a difference that old selection sort;sorts one element either smallest or largest in a single ...
详细信息
ISBN:
(纸本)9781467376822
The main idea of Optimized Selection Sort algorithm (OSSA) is based on the already existing selection sort algorithm, with a difference that old selection sort;sorts one element either smallest or largest in a single iteration while optimized selection sort, sorts both the elements at the same time i.e smallest and largest in a single iteration. In this study we have developed a variation of OSSA for two-dimensional array and called it Optimized Selection Sort algorithms for Two-Dimensional arrays OSSA2D. The hypothetical and experimental analysis revealed that the implementation of the proposed algorithm is easy. The comparison shows that the performance of OSSA2D is better than OSSA by four times and when compared with old Selection Sort algorithm the performance is improved by eight times (i.e if OSSA can sort an array in 100 seconds, OSSA2D can sort it in 24.55 Seconds, and similarly if Selection Sort takes 100 Seconds then OSSA2D take only 12.22 Seconds). This performance is remarkable when the array size is very large. The experiential results also demonstrate that the proposed algorithm has much lower computational complexity than the one dimensional sorting algorithm when the array size is very large.
This paper adapts a graph-based analysis and visualisation tool, search trajectory networks (STNs) to multi-objective combinatorial optimisation. We formally define multi-objective STNs and apply them to study the dyn...
详细信息
ISBN:
(数字)9783031300356
ISBN:
(纸本)9783031300349;9783031300356
This paper adapts a graph-based analysis and visualisation tool, search trajectory networks (STNs) to multi-objective combinatorial optimisation. We formally define multi-objective STNs and apply them to study the dynamics of two state-of-the-art multi-objective evolutionary algorithms: MOEA/D and NSGA2. In terms of benchmark, we consider two- and ***-landscapes for constructing multi-objective multi-modal landscapes with objective correlation. We find that STN metrics and visualisation offer valuable insights into both problem structure and algorithm performance. Most previous visual tools in multi-objective optimisation consider the objective space only. Instead, our newly proposed tool asses algorithm behaviour in the decision and objective spaces simultaneously.
暂无评论