Loading...
Please wait, while we are loading the content...
Similar Documents
R a N G E M E D I a N a L G O R I T H M S D a V I D K J Ae R — 2 0 0 5 0 7 1 3
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | The range median problem is that of preprocessing a list or array such that the median of any arbitrary subarray can be found rapidly. The challenge is to use as little space as possible in the process. This Thesis is divided into two parts. The first part contain a general survey on structures solving the range median problem. Included in the survey are solutions that solve the range selection problem and thereby the range median problem by inclusion. As a supplement to these algorithms a brief summary of the state of popular range problems is included in the survey. The majority of the time is spent describing the solutions given in [BGJS10] written by Gfeller, Sanders, Brodal and Jørgensen. The range problems will be considered in both a dynamic and a static setting. The second part describes implementations of some of the data structures given in [BGJS10] as well as the outcome of experiments performed on these. Acknowledgements I would like to thank my advisor Gerth for his invaluable insights and advice during this project. I would also like to thank my parents and my office mate Kasper for putting up with me for these six months. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://tildeweb.au.dk/au121/advising/thesis/david-kjaer.pdf |
| Alternate Webpage(s) | http://www.cs.au.dk/~gerth/advising/thesis/david-kjaer.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
