Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Quicksort Game
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Quicksort-spelet (Swedish)
Abstract [en]

In this thesis, we introduce a new combinatorial game called the Quicksort game. This game is played on a sequence of numbers, and players move by pivoting around a number in the manner of the familiar Quicksort algorithm. We also examine a variation on the Quicksort game called Pseudo-Quicksort. These games have some very interesting properties: Quicksort games are all-small, while Pseudo-Quicksort games are numbers. We solve Quicksort for a particular family of sequences, and describe an algorithm for converting certain Pseudo-Quicksort games into Hackenbush graphs.

Abstract [sv]

I detta examensarbete introduceras ett nytt kombinatoriskt spel, Quicksort-spelet. Spelet spelas på en sekvens av tal, där spelarna gör drag genom att välja ett pivotelement och sedan omordna sekvensen på samma vis som i Quicksortalgoritmen. Vi undersöker även Pseudo-Quicksort, en variant av Quicksortspelet. Dessa två spel har en del intressanta egenskaper: Quicksortspel är infinitesimala, men Pseudo-Quicksortspel är tal. Vi löser Quicksort för en viss mängd sekvenser, samt beskriver en algoritm som omvandlar vissa Pseudo-Quicksortspel till Hackenbush-grafer.

Place, publisher, year, edition, pages
2016.
Series
TRITA-MAT-E, 2016:24
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-188170OAI: oai:DiVA.org:kth-188170DiVA: diva2:935354
Subject / course
Mathematics
Educational program
Master of Science - Mathematics
Supervisors
Examiners
Available from: 2016-06-10 Created: 2016-06-08 Last updated: 2016-06-10Bibliographically approved

Open Access in DiVA

fulltext(518 kB)90 downloads
File information
File name FULLTEXT01.pdfFile size 518 kBChecksum SHA-512
703fb45d21964f074aab8f5cf8bd49d9c41cb7803215096e7c89f20329bb9b682e96d6338d7089045e33d7a324edb451bbd2e7d89db4eb77bfdeaa9fddc45415
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 90 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 369 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf