| 1. |
- Aspvall, Bengt, et al.
(författare)
-
Approximations for the general block distribution of a matrix
- 2001
-
Ingår i: Theoretical Computer Science. - AMSTERDAM : ELSEVIER SCIENCE BV. - 0304-3975 .- 1879-2294. ; 262:1-2, s. 145-160
-
Tidskriftsartikel (refereegranskat)abstract
- The general block distribution of a matrix is a rectilinear partition of the matrix into orthogonal blocks such that the maximum sum of the elements within a single block is minimized. This corresponds to partitioning the matrix onto parallel processors so as to minimize processor load while maintaining regular communication patterns. Applications of the problem include various parallel sparse matrix computations, compilers for high-performance languages, particle in cell computations, video and image compression, and simulations associated with a communication network. We analyze the performance guarantee of a natural and practical heuristic based on iterative refinement, which has previously been shown to give good empirical results. When p2 is the number of blocks, we show that the tight performance ratio is Theta(rootp). When the matrix has rows of large cost, the details of the objective function of the algorithm are shown to be important, since a naive implementation can lead to a Ohm (p) performance ratio. Extensions to more general cost functions, higher-dimensional arrays, and randomized initial configurations are also considered. (C) 2001 Elsevier Science B.V. All rights reserved.
|
|
| 2. |
- Aspvall, Bengt, et al.
(författare)
-
Från datorernas värld
- 2007
-
Ingår i: Nämnaren. - 0348-2723. ; 34:2, s. 44-48
-
Tidskriftsartikel (refereegranskat)
|
|
| 3. |
- Bell, Tim, et al.
(författare)
-
Making Computer Science Activities Accessible for the Languages and Cultures of Japan, Korea, China and Sweden
- 2008
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)abstract
- When teaching material is translated into another language, text-based examples can lose their significance, analogies may be meaningless in the local culture, and there may even be problems with physical access to the material. We consider principles for addressing these issues so that teaching examples can be made accessible to a diverse range of languages and cultures. We present a case study of the adaptation of a free resource for school outreach and lecture demonstrations (csunplugged.org), looking at issues encountered for Japanese, Korean, Chinese and Swedish translations. These represent a large range of languages, types of alphabets and cultures.
|
|
| 4. |
- Bell, Tim, et al.
(författare)
-
Sorting algorithms as special cases of a priority queue sort
- 2011
-
Konferensbidrag (refereegranskat)abstract
- This paper offers an exercise for revisiting the main sorting algorithms after they have been taught to students. This is done in a way that emphasizes the relationships between them, and shows how considering abstraction and extreme cases can lead to the generation of new algorithms. A number of authors (including textbook authors) have noted particular relationships between algorithms, such as an uneven split in merge sort being equivalent to insertion sort. In this paper we use a flexible priority queue, the d-heap, to derive three common sorting algorithms. We combine this with using a BST as a priority queue, plus prior observations in the literature, to show strong relationships between the main sorting algorithms that appear in textbooks. In the process students are able to revisit a number of algorithms and data structures and explore elegant relationships between them. This approach can also lead to exercises and exam questions that go beyond desk-checking to evaluate students' understanding of these algorithms.
|
|
