Matfyz Wiki
Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| <center>[[Image:Jizak6.jpg]]</center> | # **NTIN066** Datové struktury I: Úkoly 2024 ## 1. `tree_successor` Given an implementation of a simple binary search tree including parent pointers, implement a `successor` method. The methods is given a node and it should return another node of the tree with the next higher key (i.e., the smallest of keys which are greater than the given one). - If there is no such node, it should return a null pointer. - The given node can also be a null pointer, in which case the method should return the smallest node in the tree. You can expect that `successor` method is never called on an empty tree. You should submit the file `tree_successor.*` (but not the `tree_successor_test.*`). Source code templates can be found in [the git repository](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). ## 2. `splay_operation` Given an implementation of a binary search tree including parent pointers: - implement `splay` method, preferably utilizing the provided `rotate` operation performing a single rotation; - update `lookup`, `insert` and `remove` methods to utilize it correctly. You can implement the `remove` operation in more ways. However, if it is not the one presented in the lecture, you should provide a reference to the proof that it has the right amortized efficiency (e.g., a reference to a standard textbook). You should submit the `splay_operation.*` file (but not the `splay_operation_test.*`). Source code templates can be found in [the git repository](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). Files splay_operation_more_tests.{cpp,py} contain additional tests for bugs discovered in students' solutions during this semester. They are not included on recodex, but your program should pass them in few seconds. |
| Line 4: | Line 40: |
| == Jak to tady vypadá == | ## 3. `Goal` |
| Line 6: | Line 42: |
| '''Jižák''', areál pěti budov kolejí, menzy, dvou hospod ([http://www.elmagico.cz El Magico] a [http://www.klub-blanice.cz/?page_id=44 Blanice]) a budovy VŠE. A z těchto hospod je na obou stranách koleje otava premanentní hluk. O párty na chodbě, jež ruší celé patro a slabé stěně, přez kterou je slyšet sebemenší hluk z vedlejšího pokoje ani nemluvě. Prostě ani trochu klidu. Mezi vybavenost kolejí dále patří dvě smíšená zboží - v Blanici (typicky označovaný "U Zlodějky") a večerka Vltava (zatím bez přezdívky). U vstupu do koleje Otava je pobočka firmy Mironet, na koleji Otava je dále kadeřnictví (přístupné i zvenčí). U vstupu do koleje Vltava je umístěná pizzerie, ve večerních hodinách možnost donášky pizzy až na pokoj zdarma. | The goal of this assignment is to evaluate your implementation of Splay trees experimentally and to compare it with a "naive" implementation which splays using single rotations only. |
| Line 8: | Line 46: |
| * [http://blanice.vse.cz kolej '''Blanice'''] – ekonomové z VŠE * kolej '''Otava''' – přírodovědci a medici (hlavně medičky) UK a matfyzáci * kolej '''Vltava''' – přírodovědci a medici UK a matfyzáci (spodní patra), ekonomové VŠE (horní patra) * kolej '''Sázava''' – VŠCHT * kolej '''Volha''' – VŠCHT |
You are given a test program (`splay_experiment`) which calls your implementation from the previous assignment to perform the following experiments: |
| Line 14: | Line 50: |
| Budovy jsou desetipatrové, část prvního patra je zabraná kancelářemi KaM a pokoji pro hosty. Na patře je 26 buněk na Blanici, Otavě až asi 18 na Sázavě. Každou buňku tvoří dva pokoje, se společnou předsíňí s uličkou pro skříně, koupelnou se sprchou, záchodem, kuchyňský koutem a místností s dřezem. Pokoje jsou dvoulůžkové a třílůžkové, takže na buňce je 4 nebo 6 lidí. Pokoje v nejjižnější části (1, 2, 3 a 4) jsou otočeny kolmo na ostatní, mají výhled směrem na jih a jsou vybaveny balkonem. Pokoje v nejsevernější části (Bla, Ot, Vlt: 21, 22, 23, 24, 25, 26) části jsou také vybaveny balkonem ale neliší se orientací oproti ostatním pokojům. |
- _Sequential test:_ Insert _n_ elements sequentially and then repeatedly find them all in sequential order. - _Random test:_ Insert _n_ elements in random order and then find _5n_ random elements. - _Subset test:_ Insert a sequence of _n_ elements, which contains arithmetic progressions interspersed with random elements. Then repeatedly access a small subset of these elements in random order. Try this with subsets of different cardinalities. |
| Line 20: | Line 59: |
| Všechny pokoje na Otavě a všechny pokoje na Vltavě pod správou UK jsou připojeny k internetu. Blanice a Vltava VŠE jsou pokryty WiFi, zpravidla v okolí vrátnice (typický výjev ekonomů s notebookem na klíně jak okolo půlnoci serfují na pohovce před vrátnicí). Podmínky na Sázavě a Volze mi nejsou známy. | The program tries each experiment with different values of _n_. In each try, it prints the average number of rotations per splay operation. |
| Line 22: | Line 62: |
| (Kolej Volha je ve všem jiná, předchozí popis na ni neplatí.) | You should perform these experiments and write a report, which contains the following plots of the measured data. Each plot should show the dependence of the average number of rotations on the set size _n_. |
| Line 24: | Line 66: |
| == Jak se sem dostat == | - The sequential test: one curve for the standard implementation, one for the naive one. - The random test: one curve for the standard implementation, one for the naive one. - The subset test: three curves for the standard implementation with different sizes of the subset, three for the naive implementation with the same sizes. |
| Line 26: | Line 71: |
| ''Platnost k 1.9. 2009'' | The report should discuss the experimental results and try to explain the observed behavior using theory from the lectures. (If you want, you can carry out further experiments to gain better understanding of the data structure and include these in the report. This is strictly optional.) |
| Line 28: | Line 76: |
| Ze zastávky metra Chodov lze jet buď autobusem linky 177 nebo 197 do zastávky Volha, nebo linkami 136 a 154 do zastávky Koleje Jižní město. Nevýhodou je, že linky staví na opačné straně rušné silnice a tak si nemůžete vybírat až při příjezdu autobusu. U linek 136 a 154 lze vystoupit navíc o zastávku dříve na zastávce Na Jelenách, která má tu výhodu, že je blíže kolejím a vede velmi blízku bankomatu ČSOB, a naopak nevýhodu v podobě nezpevněné přístupové cesty, která se za deště stává neschůdná, a absence přechodu pro chodce na její přímé trase. Z Opatova jezdí na zastávku Volha autobus 177. V noci je pak ideální spojení autobusem 511, který staví na několika rušných bodech v centru města (např. Hlavní nádraží, Muzeum, I.P. Pavlova) a na kolej mu to trvá cca 15 minut. | You should submit a PDF file with the report (and no source code). You will get 1 temporary point upon submission if the file is syntantically correct; proper points will be assigned later. |
| Line 30: | Line 80: |
| ''Pozn.: Autobusy jedoucí ze zastávky Volha na Chodov bývají, hlavně ve špičkách, značně přeplněné. Pro lidi, kteří se neradi tlačí je proto výhodnější směr Opatov, který je však zajištěn jen jedním autobusem (tudíž nejezdí tak často), nebo linky 136 a 154. Za tmy je nezpevněná cesta ze zastávky Na Jelenách špatně osvětlená a stává se tak ještě hůře schůdnou.'' | ### Test program |
| Line 32: | Line 82: |
| == Vzdálenost od školy == | The test program is given three arguments: - The name of the test (`sequential`, `random`, `subset`). - The random seed: you should use the last 2 digits of your student ID (you can find it in the Study Information System – just click on the Personal data icon). Please include the random seed in your report. - The implementation to test (`std` or `naive`). |
| Line 34: | Line 89: |
| Ze zastávky Volha lze jet kterýmkoli autobusem kterýmkoli směrem (kromě 197, směr Smíchovské nádraží) a odveze vás na Chodov nebo Opatov (obojí trasa metra C). | The output of the program contains one line per experiment, which consists of: - For the sequential and random test: the set size and the average number of rotations. - For the subset test: the subset size, the set size, and the average number of rotations per find. The initial insertions of the full set are not counted. |
| Line 36: | Line 94: |
| * Malá Strana ** 40-50 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (I.P.Pavlova) -> tram (Malostranské náměstí) ** 35-45 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (Muzeum) -> metro (Malostranská) -> tram (Malostranské náměstí) nebo pěšky * Karlov ** 30 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (I.P.Pavlova nebo Vyšehrad) -> pěšky (fakulta) ** 25 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (I.P.Pavlova) -> bus (Dětská nemocnice Karlov - jezdí jen každých 15 min) * Karlín ** 30 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (Florenc) -> tram (Křižíkova) ** 35 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (Florenc) -> metro (Křižíkova) * Troja ** 45 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (Nádraží Holešovice) -> bus (Kuchyňka) ** 55 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (Nádraží Holešovice) -> pěšky (fakulta) * Hostivař ** 30 min: bus (Volha) -> bus (Na Groši) -> bus (Gercenova) ** 30 min: bus (Na Jelenách) -> bus (Gercenova) ** 30-40 min: bus (Volha) -> metro (Chodov||Opatov) -> metro (Háje) -> bus (Gercenova) |
### Your implementation |
| Line 53: | Line 96: |
| Please use your implementation from the previous exercise. Methods `splay()` and `rotate()` will be augmented by the test program. If you are performing a double rotation directly instead of composing it from single rotations, you need to adjust the `BenchmarkingTree` class accordingly. |
|
| Line 54: | Line 101: |
| V noci jezdí z Florence přes Muzeum a I. P. Pavlova úžasně rychlý autobus '''511'''. Z I. P. Pavlova na Volhu to zvládne za 14 minut. | ### Hints |
| Line 56: | Line 103: |
| == Adresa == | The following tools can be useful for producing nice plots: - [pandas](https://pandas.pydata.org/) - [matplotlib](https://matplotlib.org/) - [gnuplot](http://www.gnuplot.info/) |
| Line 58: | Line 108: |
| === Otava === | A quick checklist for plots: - Is there a caption explaining what is plotted? - Are the axes clearly labelled? Do they have value ranges and units? - Have you mentioned that this axis has logarithmic scale? (Logarithmic graphs are more fitting in some cases, but you should tell.) - Is it clear which curve means what? - Is it clear what are the measured points and what is an interpolated curve between them? - Are there any overlaps? (E.g., the most interesting part of the curve hidden underneath a label?) |
| Line 60: | Line 119: |
| Kolej Otava<br /> Chemická 954<br /> 148 00 Praha 4 – Jižní Město |
In your discussion, please distinguish the following kinds of claims. It should be always clear which is which: - Experimental results (i.e., the raw data you obtained from the experiments) - Theoretical facts (i.e., claims we have proved mathematically) - Your hypotheses (e.g., when you claim that the graph looks like something is true, but you are not able to prove rigorously that it always holds) |
| Line 64: | Line 126: |
| === Vltava === | Source code templates can be found in [git](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 66: | Line 128: |
| Kolej Vltava<br /> Chemická 953<br /> 148 00 Praha 4 – Jižní Město |
## 4. `ab tree` You are given a representation of _(a, b)-tree_ with a `find` operation, and a representation of an _(a, b)-tree node_. |
| Line 70: | Line 132: |
| ''Pozn.: Ačkoli se koleje udávají s adresou "Chemická", stejnou budovu najdete i na adrese "Ekonomická". To může být k užitku například pokud jedete na kolej poprvé autem, chcete využít navigaci a ta ulici "Chemická" nezná. Důkazem tohoto tvrzení může být adresa Mironetu na jejich oficiálních stránkách. Pošta nezvykne mít problémy.'' | Your goal is to implement an `insert` operation, which inserts the given key in the tree (or does nothing if the key is already present). Preferably, you should also implement `split_node` method and use it properly in your `insert` implementation. |
| Line 72: | Line 137: |
| == Odkazy == | The implementation uses the variant of (a,b)-trees from lecture notes by [Martin Mares, Chapter 3](http://mj.ucw.cz/vyuka/dsnotes/03-abtree.pdf) where the actual values are stored also in the internal nodes of the tree and not only in leaves. |
| Line 74: | Line 141: |
| Oficiální web: [http://www.jm.koleje.cuni.cz/ Koleje Jižní Město] | You should submit the `ab_tree.*` file (but not `ab_tree_test.*` files). |
| Line 76: | Line 143: |
| Source code templates can be found in [git](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). | |
| Line 77: | Line 145: |
| [[Category:Koleje]] |