Change search
Link to record
Permanent link

Direct link
BETA
Aspvall, Bengt
Publications (4 of 4) Show all publications
Bell, T. & Aspvall, B. (2011). Sorting algorithms as special cases of a priority queue sort. Paper presented at 42nd ACM Technical Symposium on Computer Science Education, SIGCSE. Paper presented at 42nd ACM Technical Symposium on Computer Science Education, SIGCSE. Dallas: ACM
Open this publication in new window or tab >>Sorting algorithms as special cases of a priority queue sort
2011 (English)Conference paper, Published paper (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Dallas: ACM, 2011
Keywords
D-heap, Priority queue, Sorting algorithms
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-7498 (URN)10.1145/1953163.1953203 (DOI)oai:bth.se:forskinfo75BDE3B3F68C88ABC12578BE003207B5 (Local ID)978-145030500-6 (ISBN)oai:bth.se:forskinfo75BDE3B3F68C88ABC12578BE003207B5 (Archive number)oai:bth.se:forskinfo75BDE3B3F68C88ABC12578BE003207B5 (OAI)
Conference
42nd ACM Technical Symposium on Computer Science Education, SIGCSE
Available from: 2012-09-18 Created: 2011-06-29 Last updated: 2018-01-11Bibliographically approved
Bell, T., Wada, B. T., Kanemunu, S., Xia, X., Lee, W., Choi, S., . . . , A. W. (2008). Making Computer Science Activities Accessible for the Languages and Cultures of Japan, Korea, China and Sweden. Paper presented at SIGCSE 2008, The 39th ACM Technical Symposium on Computer Science Education. Paper presented at SIGCSE 2008, The 39th ACM Technical Symposium on Computer Science Education. New York, NY: Association for Computing Machinery, Inc. (ACM)
Open this publication in new window or tab >>Making Computer Science Activities Accessible for the Languages and Cultures of Japan, Korea, China and Sweden
Show others...
2008 (English)Conference paper, Oral presentation only (Other academic) Published
Alternative title[sv]
Anpassning av datalogiska aktiviteter för språken och kulturerna i Japan, Kina, Korea och Sverige
Abstract [en]

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.

Abstract [sv]

När undervisningsmaterial översätts kan text baserade exempel förlora sin mening, analogier bli meningslösa, alfabet oförenliga, etc. Vi fokuserar på några principer för att undervisningsexempel ska fungera i helt olika språk och kulturer. Vi presenterar en fallstudie baserad på material som är fritt tillgängligt från CSunplugged.org. Det engelska materialet har anpassats till japanska, kinesiska, koreanska och svenska förhållande. (Dataundervisning, Kinestetisk lärande, Översättning)

Place, publisher, year, edition, pages
New York, NY: Association for Computing Machinery, Inc. (ACM), 2008
Keywords
Computer science education, Kinesthetic learning, Cultural accessibility
National Category
Mathematical Analysis Computer Sciences
Identifiers
urn:nbn:se:bth-8256 (URN)oai:bth.se:forskinfo190BFA1E8618EB9CC1257539004EF441 (Local ID)978-1-59593-927-9 (ISBN)oai:bth.se:forskinfo190BFA1E8618EB9CC1257539004EF441 (Archive number)oai:bth.se:forskinfo190BFA1E8618EB9CC1257539004EF441 (OAI)
Conference
SIGCSE 2008, The 39th ACM Technical Symposium on Computer Science Education
Available from: 2012-09-18 Created: 2009-01-09 Last updated: 2018-01-11Bibliographically approved
Aspvall, B. & Pettersson, E. (2007). Från datorernas värld. Nämnaren, 34(2), 44-48
Open this publication in new window or tab >>Från datorernas värld
2007 (English)In: Nämnaren, ISSN 0348-2723 , Vol. 34, no 2, p. 44-48Article in journal (Refereed) Published
Alternative title[sv]
From the world of computers
National Category
Computer Sciences
Identifiers
urn:nbn:se:bth-9188 (URN)oai:bth.se:forskinfo3B87E16E86288197C125730F0041BD15 (Local ID)oai:bth.se:forskinfo3B87E16E86288197C125730F0041BD15 (Archive number)oai:bth.se:forskinfo3B87E16E86288197C125730F0041BD15 (OAI)
Available from: 2012-09-18 Created: 2007-07-05 Last updated: 2018-01-11Bibliographically approved
Aspvall, B., Halldorsson, M. & Manne, F. (2001). Approximations for the general block distribution of a matrix. Theoretical Computer Science, 262(1-2), 145-160
Open this publication in new window or tab >>Approximations for the general block distribution of a matrix
2001 (English)In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 262, no 1-2, p. 145-160Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
AMSTERDAM: ELSEVIER SCIENCE BV, 2001
National Category
Software Engineering
Identifiers
urn:nbn:se:bth-8209 (URN)000169594100009 ()oai:bth.se:forskinfo15FF76F262DA96A1C12575B00020C316 (Local ID)oai:bth.se:forskinfo15FF76F262DA96A1C12575B00020C316 (Archive number)oai:bth.se:forskinfo15FF76F262DA96A1C12575B00020C316 (OAI)
Available from: 2012-09-18 Created: 2009-05-08 Last updated: 2018-01-11Bibliographically approved

Search in DiVA

Show all publications