My sorting home page presents a number of original sorting algorithms (+ variants) in Java designed by Arne Maus. All algorithms are downloadable and their usage are regulated by the BSD license (basically that their original author must always be credited whenever used).
All code is accompanied by a pubished paper explaining its usage, performance and limitations. Disclaimer: Although all these algorithms are thoroughly tested, no guarantee is given that they work as intended in any application where they might be used.
Emneord:
Parallel programming,
Java,
Object Oriented programming,
Delaunay triangulation,
Sorting,
algorithms
Publikasjoner

Maus, Arne (2015). A full parallel Quicksort algorithm for multicore processors. NIK: Norsk Informatikkonferanse.
ISSN 18920713.

Gjessing, Stein & Maus, Arne (2012). Teaching predicates and invariants on shared data structures in concurrent programming, In Edward F. Gehringer & Dick Brown (ed.),
SPLASH '12 Conference on Systems, Programming, and Applications: Software for Humanity, Proceedings of the 2012 workshop on Developing competency in parallelism: techniques for education and training.
ACM Publications.
ISBN 9781450318402.
Artikkel.
s 9
 14

Maus, Arne (2011). A full parallel radix sorting algorithm for multicore processors, In
Norsk Informatikkonferanse NIK 2011.
Tapir Akademisk Forlag.
ISBN 9788251928434.
paper 4.
s 37
 48
Fulltekst i vitenarkiv.

Maus, Arne & Moen Drange, Jon (2010). All closest neighbors are proper Delaunay edges generalized, and its application to parallel algorithms, In Terje Fallmyr & Erik Hjelmås (ed.),
Norsk Informatikkonferanse.
Tapir Akademisk Forlag.
ISBN 9788251927031.
Artikkel nr. 1.
s 1
 12
Vis sammendrag
In this paper we first prove that for any set of points P in the plane,the closest neighbor b to any point p in P is a proper triangle edge bp in D(P), the Delaunay triangulation of P. We also generalize this result and prove that the j'th (second, third, ..) closest neighbors bj to p are also edges pbj in D(P) if they satisfy simple tests on distances from a point. Even though we can find many of the edges in D(P) in this way by looking at close neighbors, we give a three point example showing that not all edges in D(P) can be found in this way. For a random dataset we give results from test runs and a model that show that our method finds on the average 4 edges per point in D(P). Also, we prove that the Delaunay edges found in this way form a connected graph. We use these results to outline two parallel algorithms for finding D(P). Finally, we comment on using these theorems and solving the k'th closest neighbors problem.

Maus, Arne & Lingjærde, Ole Christian (2009). LASTING EFFECTS OF AUTOMATIC PLAGIARISM DETECTION IN AN INTRODUCTORY COURSE IN PROGRAMMING, In L Gómez Chova (ed.),
INTED2009 Proceedings CD.
The International Academy of Technology, Education and Development.
ISBN 9788461275786.
i sessjonen:Emerging Technologies: Internet Based Technologies.

Maus, Arne (2008). IPS, sorting by transforming an array into its own sorting permutation with almost no space overhead, In Frode Sandnes Eika & Andreas Prinz (ed.),
Norsk informatikkonferanse NIK 2008.
Tapir Akademisk Forlag.
ISBN 9788251923866.
artikkel.
s 63
 74
Vis sammendrag
This paper presents two new algorithms for inline transforming an integer array ‘a’ into its own sorting permutation  that is: after performing either of these algorithms, a[i] is the index in the unsorted input array ‘a’ of its i’th largest element (i=0,1..n1). The difference between the two IPS (Inline Permutation Substitution) algorithms is that the first and fastest generates an unstable permutation while the second generates the unique, stable, permutation array. The extra space needed in both algorithms is O(log n) – no extra array of length n is needed! The motivation for using these algorithms is given along with their pseudo code. To evaluate their efficiency, they are tested relative to sorting the same array with Quicksort on 4 different machines and for 14 different distributions of the numbers in the input array, with n=10, 50, 250.. 97M. This evaluation shows that both IPS algorithms are generally faster than Quicksort for values of n less than 107, but degenerates both in speed and demand for space for larger values. These are results with 32 bit integers (with 64 bits integers this limit would be proportionally higher, at least 1014 ). The two IPS algorithms do a recursive, most significant digit radix sort (left to right) on the input array while substituting the values of the sorted elements with their indexes.

Maus, Arne & Lingjærde, Ole Christian (2008). The application of a novel plagiarism detection system to an introductory course in programming: lessons learned, In I. Gómes Chova; D. Martí Belenguer & I. Candel Torres (ed.),
INTED2008 IProceedings.
The International Academy of Technology, Education and Development.
ISBN 9788461201907.
artikkel 578.

Maus, Arne (2007). Buffered Adaptive Radix – a fast, stable sorting algorithm that trades speed for space at runtime when needed, In Frode Eika Sandnes (ed.),
Norsk informatikkonferanse NIK 2007.
Tapir Akademisk Forlag.
ISBN 9788251922722.
Kap. 2.
s 19
 30

Maus, Arne & Gjessing, Stein (2007). A Model for the Effect of Caching on Algorithmic Efficiency in Radix based Sorting, In Sergiu Dascalu & Petre Dini (ed.),
ICSEA 2007 (International Conference on Autonomic and Autonomous Systems).
IEEE.
ISBN 9780769529370.
33.

Maus, Arne (2006). Making a fast unstable sorting algorithm stable, In Chunming Rong & Arne Løkketangen (ed.),
NIK'2006 : Norsk informatikkonferanse.
Tapir Akademisk Forlag.
ISBN 8251921864.
Arikkel nr. 4.
s 41
 52

Gjessing, Stein & Maus, Arne (2005). Discrete Event Simulation of a Large OBS Network, In Mo Jamshidi (ed.),
Proceedings 2005 IEEE International Conference on Systems, Man and Cybernetics.
IEEE.
Kapittel.

Maus, Arne (2005). Research and Curricula Developemnt of Norwegian Universities From the early years to the mid1970s, In Janis Bubenko; John Impagliazzo & Arne Sølvberg (ed.),
History of Nordic Computing.
Springer.
ISBN 0387241671.
12.
s 137
 154

Gjessing, Stein & Maus, Arne (2002). A Fairness Algorithm for Highspeed Networks based on a Resilient Packet Ring Architecture, In Abdelkader El Kamel (ed.),
2002 IEEE International Conference on Systems, Man and Cybernetics.
IEEE.
ISBN 295123094X.
CD proceeding.
Fulltekst i vitenarkiv.
Vis sammendrag
IEEE is currently standardizing a spatial reuse ring topology network called the Resilient Packet Ring (RPR, IEEE P802.17). The goal of the RPR development is to make a LAN/MAN standard, but also WANs are discussed. A ring network needs a fairness algorithm that regulates each stations access to the ring. The RPR fairness algorithm is currently being developed with mostly long distances between stations in mind. In this paper we discuss the feedback aspects of this algorithm and how it needs to be changed in order to give good performance if and when RPR is used for highspeed networks and LANs with shorter distances between stations. We discuss different architectural parameters including buffers sizes and distances between stations. We suggest the use of triggers instead of timers to meet the response requirements of highspeed networks. We have developed a discrete event simulator in the programming language Java. The proposed improvements are compared and evaluated using a ring network model that we have built using our simulator.

Maus, Arne (2002). ARL, a faster inplace, cache friendly sorting algorithm, In Norvald Stohl; Torbjørn Strøm; Terje Fallmyr; Sissel Haddjerroudit; Dag Langmyhr & Fredrik Manne (ed.),
Norsk Informatikkonferanse NIK'2002.
Høgskolen i Buskerud.
ISBN 8291116458.
Chapter.
s 85
 95

Maus, Arne (1996). Vitenskap, informasjonsteknologi, og samfunnsmessige virkninger, I: Odd Wormnæs (red.),
Vitenskap  enhet og mangfold.
ad Notam/Gyldendal, Oslo.
ISBN 8241706820.
s 388
 406
Vis sammendrag
Dette kapittelet handler om virkningene av data og datanettteknologien. Vi skal søke å se på vitenskapens rolle, samfunnsmessige virkninger og etiske dilemma som reiser seg ved anvendelser av IT.

Maus, Arne (1995). Datavtalene og Arbeidsmilojøloven. IT og arbeidsplassene. Personvern og sikerheten i informasjonssamfunnet, I: Gisle Hannemyr; Arne Maus; Gerhard M Skagestein & Aud Sugar (red.),
BIT 1 A Brukersystemer.
ISBN 8202153611.
s 46
 71
Vis sammendrag
To kapitler i lærebok for videregående skole i IT.

Maus, Arne (1984). Delanay Triangulation and the Convex Hull of n Points in expected linear Time. BIT Numerical Mathematics.
ISSN 00063835.
24(37), s 151 163
Vis sammendrag
An algorith is presented which produces a Delaunay triangulation of n points in the Euclidean plane in expexted linear time. The expected execution time is acheived when the data are (not too far from) uniformly distributed. A modification of the algorithm discussed in the appendix, treats most of the nonuniform distributions. The basis of this algorithm is a geographical partitioning of the plan into boxes by the wellknown Radix algorithm. This partiotioning is also used as a basis for a linear time algorithm for finding the convex hull of n points in the Euclidean plane.

Maus, Arne (1982). Technology and Employment, In Eystein Forrum (ed.),
Computerization of Working Life.
Ellis Horwood limited, Chirhester.
ISBN 0853125848.
s 61
 84
Vis sammendrag
The question of wheather EDP has an impact on employment, is one of the most cotroversial issues concerning the social impact of technology.

Maus, Arne & Endresen, Jan (1979). Misuse of computergenerated results. Medical and Biological Engineering and Computing.
ISSN 01400118.
s 126 129
Vis sammendrag
The number of statistical tests performed has increased by several orders of magnitude through the use of computers and readmade statistical packages. The vast majority of these tests neither physically can be, nor ever are, published. Only tests which show a strog statistical corrolation between some variables seems to be sorted out for publication. This practice, which can be found in applied sciences such as social and medical sciences, is investigated and shown in many cases to lesd to a considerable increase in the percentage of published false results. A new function to be perormed by statistical packages is then proposed to reduce theis percentage.

Maus, Arne (1975). On Access to Temporary Resources. BIT Numerical Mathematics.
ISSN 00063835.
15(1), s 72 84
Vis sammendrag
The sharable resources of a multiprogramming system can be classified as either permanent or temporary, and their use can be classified as either exclusive or nonexclusive. While semaphores, as defined by Dijkstra syncronize access to permanent resources, this article proposes two new primitives for synchronize access to temporary resources. Theis usefullness is demonstrated by examining the problem of a number of 'readers' and 'writers' sharing a single file. Finally, a highlevel language notation is proposed which synchronizes access to a declared, sharable resource of any of the categories classified above.
Se alle arbeider i Cristin

Maus, Arne & Gjessing, Stein (2014). Practical Parallel Programming – a B.S. course on how to design an efficient parallel algorithm..
EduPar14.
ISBN 9781479941179.
8 s.

Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2011). Rett på Java  3.utg.
Universitetsforlaget.
ISBN 9788215018522.
390 s.

Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2005). Rett på Java, 2 utg.
Universitetsforlaget.
ISBN 8215007813.
363 s.

Brunland, Anders; Hegna, Knut; Lingjærde, Ole Christian & Maus, Arne (2003). Rett på Java.
Universitetsforlaget.
ISBN 8215002579.
280 s.

Hannemyr, Gisle; Maus, Arne; Skagestein, Gerhard M & Sugar, Aud (red.) (1995). BIT 1 A Brukersystemer.
ISBN 8202153611.
Se alle arbeider i Cristin

Opdal, LarsErik; Maus, Arne & Stray, Viktoria (2016). Parallelle beregninger med MPI i delt og distribuert minne.

Maus, Arne (2002). PRP  Parallel Recursive Procedures, a low cost, easy to use alternative for some often ocurring classes of problems.
Vis sammendrag
Almost all work on parallelizing programs uses the abstraction of communicating parallel programs in the form of processes or parallel threads. This lecture presents an alternative abstraction  parallelizing a problem though the use of a recursive procedure (PRP). With this PRP concept the recursion tree is split among all participating machines (connected by a LAN or Web). The user involvement in this process is minimal by just putting in two different comments in the original recursive program. What restrictions that has to be put on the recursive procedure in PRP is presented along with a sketch of the implementation and examples on problems solved. This concept is demonstrated to scale very well up to 120 machines (max. tried so far) and for some interesting classes of problems. This is a report from an ongoing series of master thesis at the Dept. of Informatics, Univ. of Oslo, which now has produced a well working Java based platform for the PRP system.

Maus, Arne (2002). Two 'new' sorting algorithms  and the effect of multi level caching on performance.
Vis sammendrag
This presentation introduces two new, fast sorting algoritms: MSort and Psort, both having advantages (inplace reordering and generating the sorting permutation). Both are significantly faster then Quicksort. MSort is a modified Most Significant Radix algorithm. PSort is a fast way to generate the permutation p that defines the sorting order of a set of integer keys in an integer array ¿a¿ that is: a[p[i]] is the i¿th sorted element in ascending order. The motivation for using Psort is given along with its implementation in Java. This distribution based sorting algorithm, Psort, is compared to two comparison based algorithms, Heapsort and Quicksort, and two other distribution based algorithms, Bucket sort and Radix sort. The relative performance of the distribution sorting algorithms for arrays larger than a few thousand elements are assumed to be caused by how well they handle caching (both level 1 and level 2). The effect of caching is investigated, and based on these results, more cache friendly versions of Psort and Radix sort are presented and compared.

Maus, Arne (2000). Sorting by generating the sorting partition, and the effect of caching on sorting.
Vis sammendrag
This paper presents a fast way to generate the permutation p that defines the sorting order of a set of integer keys in an integer array 'a'  that is: a[p[i]] is the i'th sorted element in ascending order. The motivation for using Psort is given along with its implementation in Java. This distribution based sorting algorithm is compared to two comparison based algortthms, Heapsort and Quicksort, and two other distribution based algorithms, Bucket sort and Radix sort. The relative performance of the distribution sorting algorithms for arrays larger then a few thousand elements are assumed to be caused by how well they handle caching (both level 1 and 2). The effect of caching is invesitgated, and based on these results, more cache friendly versions of Psort and Radix sort are presented and compared.

Gjessing, Stein; Maus, Arne; Strøm, Torstein & Huse, Lars Paul (1999). Running the Synthetic Aperture Radar (SAR) Application on a switched SCI cluster.
Vis sammendrag
We describe how a real application, the Syntetic Aperture Radar (SAR) program, is parallelized and run on a cluster of PCs connected by SCI. We have a prototype SCI switch that uses the serial IEEE 1355 HIC technology in its switching fabric. The prototype switch can not keep up with the speed of the SCI interconnect, and we analyze and discuss how switch performance influence the execution time of our parallelized application.

Maus, Arne (1999). Klynger av PCer, framtidas superdatamaskiner.
Vis sammendrag
Oversikt over potensielle hastighetsforbedringer og programvare for å å koble tett sammen et antall PCer

Maus, Arne (1999). Objektorientert systemutvikling.
Vis sammendrag
Grunnleggende innføring i begreper, metoder og anvendelser.

Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Final report on the testing of the SCI to HIC switch & Running the SAR (Synthetic Aperture Radar) application in a switched cluster of PCs.
Vis sammendrag
This combined delivery first describes testing of a HIC based SCI switch embedded in a cluster of PCs running standard micro benchmarks (pingpong latency and throughput) of various data packet sizes and with various configurations of 2 and 3 switched SCI rings. The switch itself is made up of switching units that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology and is more thoroughly described in D4.1.1 and D 4.1.2 and the micro benchmarks has in more detail been reported in D4.1.4 and D4.1.5. The limitations of this prototype switch are then discussed. After these initial tests, a real industrial application, the SAR (Synthetic Aperture Radar) application was run through the switch connected as a 3way switch, varying the number of nodes in each switched SCI rings. This deliverable concludes with a discussion of the viability of an industrial version of this switch.

Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Running the SAR Application on a Cluster of PCs Connected with SCI using a HIC based SCI switch.
Vis sammendrag
This paper describes a prototype SCIswitch and its behaviour in a real application. The switching fabric uses the IEEE 1355 HIC technology to switch SCI packets in a switch with up to seven SCI ports. In our lab we have tested a switch with up to three SCI ports. We report on the performance of a Synthetic Aperture Radar (SAR)application when it is run on a number of dual processor PCs connected by SCI and using our HICbased SCI switch.

Maus, Arne; Strøm, Torstein; Gjessing, Stein & Huse, Lars Paul (1999). Running the SARapplication on a cluster of PCs connected with SCI, using a HICbased SCIswitch.
Vis sammendrag
This paper first describes testing of the HIC based SCI switch embedded in a cluster of PCs running standard micro benchmarks (pingpong latency and throughput) of various data packet sizes and with various configurations of 2 and 3 switched SCI rings. The switch itself is made up of switching units that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The limitations of this prototype switch are then discussed. A real industrial application, the SAR (Synthetic Aperture Radar) application was run through the switch connected as a 3way switch, varying the number of nodes in each switched SCI ring. This paper concludes with a discussion of the viability of an industrial version of this switch.

Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). A HIC based SCI switch  implementation and performance.
Vis sammendrag
This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 13555 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed backtoback to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.

Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). Switched embedded workstation cluster exploiting the HIC based SCI switch.
Vis sammendrag
This report describes performance characteristics of an experimental HIC based SCI switch embedded in a cluster of PCs. Internally the switch translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. Architectually up to seven SCI rings can be connected to the switch, but due to limited resources, only a 2x2 and a 3x3 switch has been tested. This deliverable focuses on presenting a comprehensive set of low level latency and throughput figures for different configurations, and evaluating the state of this prototype switch and the potentials of an industrial version of this switch.

Strøm, Torstein; Halfen, Bjørn; Maus, Arne & Gjessing, Stein (1999). Working SCI switch based on HIC components.
Vis sammendrag
This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed backtoback to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.

Strøm, Torstein; Maus, Arne; Halfen, Bjørn & Gjessing, Stein (1999). A HIC Based SCI switch  implementation and performance.
Vis sammendrag
This paper describes a prototype switching unit that translates IEEE 1596 SCI packets to and from the serial IEEE 1355 HIC technology. The unit has one SCI interface and twelve HIC interfaces. Up to seven of these units can be placed backtoback to make up an SCI switch. Hardware and system behaviour is described. Latency and throughput are presented for different configurations and different sizes of user data. Finally the potential of an industrial version of this prototype is evaluated.

Ryan, Stein Jørgen; Maus, Arne & Gjessing, Stein (1997). An operating system independent driver for an I/O based SCI interface.

Sjøberg, Dag; Jørgensen, Magne & Maus, Arne (1996). Evaluating Software Maintenance Technology.

Maus, Arne & Aas, Torfinn (1995). PRP  Parallel Recursive Procedures.
Vis sammendrag
It is believed that writing parallel programs is hard. Therefore a pradigm for writing parallel programs that is not much harder than writing a sequeltial program is in demand. This paper describes a general method for parallelizing programs based on the idea of using recursive procedures as the grain of parallelism (PRP). This paradigm only adds a few new constructs to an ordinary sequential program with recursive procedures and makes both the underlying hardware topology and in most cases also the number of independant processing nodes, transparent to the programmer. The implementation reported in this paper uses workstations and servers connected to an Ethernet. The efficiency achieved by the PRPconcept must be said to be good with a more than 50% processor utilization on the two problems reported. Other implementatons of the PRPparadigm is also reported.

Jørgensen, Magne & Maus, Arne (1993). A case study of software maintenance tasks.

Maus, Arne (1992). Entropy as a Complexity Measure, and the Optimal Module Size of Object Oriented Programs.
Vis sammendrag
This paper defines a measure for the complexity of a program and its components as seen from a maintenance programmer point of view. This is done by using the entropy measure from thermodynamics. It is shown that two programmes solving the same problem differ considerably in entropy  the program properly structured into classes and procedures having the lowest entropy. The optimal number of procedures and classes is derived. This complexity measure can easily be built into any compiler.

Maus, Arne (1992). Solutions to a trivial problem  a study in programming paradigms.
Vis sammendrag
The complexity theories of programming seek to find and classify the best algorithms for a given problem. This paper has a different perpective. The 'natural' solutions to a trivial problem (finding the sum of the n first natural numbers) are investigated, And it is demonstrated that there is an extreme variation in the time and space efficiency in the solutions we get when following dominant programming styles. This paper can both be used as a student tutorial and be seen as a criticism of some of the more popular programming paradigms.

Maus, Arne (1991). Entropy as a Complexity Measure, and the Optimal Module Size of Object Oriented Programs.
Vis sammendrag
This paper defines a measure for the complexity of a program and its components as seen from a maintenance programmer point of view. This is done by using the entropy measure from thermodynamics. It is shown that two programmes solving the same problem differ considerably in entropy  the program properly structured into classes and procedures having the lowest entropy. The optimal number of procedures and classes is derived. This complexity measure can easily be built into any compiler.

Thoresen, Kari Trædal & Maus, Arne (1979). Technological unemployment and working conditions in the comuterized office  two problem areas for trade unions.

Maus, Arne (1978). Interlude on Signals and Semaphores Revisited. Communications of the ACM.
ISSN 00010782.
21(7), s 592 592

Krogdahl, Bjørn & Maus, Arne (1978). Offentlige etaters anskaffelse av EDBsystemer.
Se alle arbeider i Cristin
Publisert 4. nov. 2010 14:08
 Sist endret 10. okt. 2016 13:58