Matfyz Wiki
Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| == Jak se sem dostanete == Nejobvyklejší cesta vede ze stanice metra Hradčanská tramvají 1 nebo 18 do zastávky 'Větrník'. Další možnost je dojet metrem až na Dejvickou a odtud tramvají 2 opět do zastávky 'Větrník'. Z Andělu je možné sednout na autobus 191 a nechat se dovézt až na zastávku 'Koleje Větrník', nebo ze stanice 'Nové Butovice' na stejnou zastávku jezdí autobusy 179 a 184. |
# **NTIN066** Datové struktury I: Úkoly 2024 |
| Line 6: | Line 3: |
| == Jak to tu vypadá == | ## 1. `tree_successor` |
| Line 8: | Line 5: |
| Dvojlůžkové pokoje (2,5 × 5 m). Výjimkou jsou 3 trojlůžáky na druhém bloku. Bydlení tam je levnější, ale tři lidi mají společné dvě skříně, takže trocha komfortu chybí. Sociální zařízení a kuchyňka jsou všude společná pro patro (cca 40 lidí). | 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). |
| Line 10: | Line 10: |
| === Ubytování === | - 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. |
| Line 12: | Line 14: |
| Větrník má 4 bloky. | You can expect that `successor` method is never called on an empty tree. |
| Line 14: | Line 16: |
| '''I. blok''' je lukrativní místo s dobrým výhledem směrem na východ. Západní strana je na tom hůře. Má společnou vrátnici s II. blokem a díky většímu počtu lidí jsou u vrátnice instalovány automaty na všelico možné. | You should submit the file `tree_successor.*` (but not the `tree_successor_test.*`). |
| Line 16: | Line 19: |
| '''II. blok''' má podle mnoha lidí nejsilnější atmosféru. Má pověst hlučného bloku s častými večírky. Východní strana má výhled na fotbalové "hřišťátko" (rozuměj udusanou hlínu) a dále přes sousedy, věčně a hlučně opravující loď, až do oken bloku 3.A. Západní strana má romantický výhled na parkoviště a především na Billiard Club. Společná vrátnice s 1. blokem zajišťuje oběma blokům výhodnou pozici. Mají to nejblíž na autobus, do hospody, do obchodu, na tramvaj. Na ubytovačku o něco dál, než 3.blok. K menze to má nejdál, ale ta je stejně tak daleko, že to nehraje skoro roli. | Source code templates can be found in [the git repository](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 18: | Line 21: |
| '''III. blok''' je rozdělen na dva podbloky. Blok III. A a III. B.<br /> Ačko, kam se dostanete, když na vrátnici zahnete doprava, má na západ výhled na 2. blok a sousedy, na východ kouká na 3.B. Béčko (na vrátnici doleva) zas na západ kouká na 3.A a na východ na blok 4. Pokoje na koncích chodeb se vyznačují bonusem - mají navíc jedny prosklené francouzské dveře a nejvyšší patra z nich ten nejlepší výhled jaký můžete na této koleji mít. Celý blok je podstatně tišší a klidnější než 2, chodby jsou kratší a vzniká tady rychleji takové domáčtější prostředí. K tomu přispívá i možnost vysedávání (např. u grilu) uvnitř 'podkovy', kde je klid a poměrně zeleno. Blok je čerstvě po zateplení a rekonstrukci koupelen. Vzdálenostmi je na tom průměrně. Všude to má dál, jen k ubytovačce to má kousek. |
## 2. `splay_operation` |
| Line 21: | Line 23: |
| '''IV. blok''' je rozdělený na IV. A a IV. B stejně jako III. blok. Je často obsazován zahraničními studenty a podle toho to tam vypadá. Párty, oslavy, křik, kterému nerozumíte. Občasné kulturní rozdílnosti způsobují problémy. Přesto, nebo právě proto, se do něj investují největší peníze. Je zateplený, rekonstruované koupelny a jsou tam automaty na vrátnici. Má to nejdál na ubytovačku, do obchodu, na autobus a na tramvaj. Zase k menze na Kajetánce to má nejblíž. | 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). |
| Line 23: | Line 29: |
| '''Vybavení bloků''' prochází poslední dobou průběžnou obnovou. Všude jsou nové postele (na III. A nejnovější a nejlepší). Nábytek je nový na IV. bloku a na některých pokojích bloku 1. Jinde je nábytek takový, že na něm můžete najít vyrytý i podpis vašich rodičů z dob studijních. Ale nezoufejte - dá se esteticky vylepšit a svou kvalitu prokazuje již několik desetiletí. Na podlaze je linoleum, stěny jsou děravé a padá z nich omítka. Je možné si vymalovat a nechat proplatit barvu. Stejně tak v nouzi můžete poprosit údržbáře, zda by vám nepůjčil nářadí, případně sám nepomohl při zkulturňování pokoje.<br /> V přízemí jsou v oknech mříže. III. a IV. blok má okna plastová. Z těch ostatních starých se odlupuje barva a dělá binec v pokoji.<br /> Pokoje na všech blocích jsou zasíťované a na každém jsou 2 ethernetové zásuvky. Připojení rychlostí 100MBit zajišťuje [http://kam.cuni.cz KaM]. Každý připojený má vlastní veřejnou IP adresu, ale všechna příchozí spojení jsou blokována, tedy zapomeňte na ssh, ftp, www, apod. servery přístupné z divočiny internetu. Abyste mohli na internet, je nutné si zaregistrovat MAC adresu a k tomu potřebujete ID Univerzity Karlovy. Studentům jiných škol jako nápověda slouží [http://kam.cuni.cz/KAM-66.html tato stránka]. |
You should submit the `splay_operation.*` file (but not the `splay_operation_test.*`). |
| Line 28: | Line 32: |
| Ve většině pokojů jsou ledničky (dokupují se další).<br /> Záchod, sprchy a kuchyňku uklízí každý všední den uklízečka, takže máte všude čisto bez práce. Tedy alespoň do té doby, než to nějaké čuně před vámi zaneřádí. |
Source code templates can be found in [the git repository](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 31: | Line 34: |
| Na závěr, nezapomeňte, že každý pokoj se dá zútulnit. :) === Co najdete na koleji a kolem ní === |
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 35: | Line 39: |
| Na II. a III. bloku je ping-pongový stůl, na II. bloku je posilovna, kterou spravuje KR. Na I. bloku jsou dvě místnosti s klavírem - najdete tu jak klasický klavír, tak křídlo. Na III. bloku je další klavír. Na každém bloku je řada studoven a po jedné televizní místnosti. | |
| Line 37: | Line 40: |
| Za druhým blokem najdete menší fotbalové hřiště s mizernými brankami, ale hrát se tam dá dobře. Za prvním blokem je volejbalové hřiště s antukou. Pokud jej chcete využívat, ptejte se na vrátnici. Za kolejí je veliký sad, kde se dá buď učit pod stromem, nebo na lavičce, když je teplo, nebo si tam i zaběhat. | ## 3. `Goal` |
| Line 39: | Line 42: |
| Kousek od koleje jsou tři obchody (2×Billa, 1×Norma), pošta, 2×drogerie, hospoda (cca 4×, podle toho jak daleko chcete jít) a spousta dalšího. | 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 41: | Line 46: |
| Přímo v budově prvního bloku je Bécéčko (Billiard Club), zakouřená hospoda, kde se dá zahrát kulečník nebo i fotbálek. Pro nekuřáky tam mají i salónek, překvapivě relativně bez kouře (nebojte se, stejně pak budete smrdět). Asi 5 minut pěšky můžete jít na Hvězdu do [http://www.klubhvezda.cz/ klubu], kde jsou skoro každý den diskotéky. | You are given a test program (`splay_experiment`) which calls your implementation from the previous assignment to perform the following experiments: |
| Line 43: | Line 50: |
| Nevýhoda bydlení na sousední koleji Hvězdě je v tom, že hned vedle je umístěna plochodrážní dráha, která vás může občas rušit (hlavně pokoje, které mají okna obrácena k dráze). Radši pojďte na Větrník, je to kousek. | - _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 45: | Line 59: |
| Docela slušně tu funguje společenský život. Stačí se jen trochu zajímat. Určitě si prohlédněte [http://www.vetrnik.koleje.cuni.cz/diskuse/ naše fórum], najdete tam mnoho informací a třeba i nějaká překvapení. ;) | The program tries each experiment with different values of _n_. In each try, it prints the average number of rotations per splay operation. |
| Line 47: | Line 62: |
| === Matfyzáci === | 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 49: | Line 66: |
| Od doby, kdy zdražili kolej 17. listopadu, je na Větrníku mnohem víc matfyzáků. A hlavně, tady nejsou zavření v buňkách u počítače, ale pořád se tu něco děje. Matfyzáků je tu opravdu dost. | - 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 51: | Line 71: |
| == Vzdálenost od školy == | 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 53: | Line 76: |
| * nám. Jana Palacha **tram 18 -> Staroměstská (~20 minut) * Malá Strana **tram 18 -> Malostranská, tram 12,20,22,23 -> Malostranské Náměstí (~25 minut) **tram 1,18 -> Hradčanská, tram 20 -> Malostranské náměstí (~25 minut) **tram 1,2,18 -> Vozovna Střešovice, přesun asi 2min, Brusnice, tram 22,23 -> Malostranské náměstí (~25 minut) * Karlín **tram 1,18 -> Hradčanská, tram 8 -> Křižíkova (~35-40 minut) **tram 1,18 -> Hradčanská, metro A -> Můstek, metro B -> Křižíkova (~35 minut) **tram 2 -> Dejvická, metro A -> Můstek, metro B -> Křižíkova (~35 minut) * Trója **tram 1 -> Vltavská, metro C -> Nádraží Holešovice, bus -> Kuchyňka (nebo Pelc Tyrolka) (~45 minut) **tram 1,2,18 -> Vozovna Střešovice, tram 15 -> Nádraží Holešovice, bus -> Kuchyňka (nebo Pelc Tyrolka) (~45 minut) * Hostivař **tram 1,18 -> Hradčanská, metro A -> Skalka, bus 154,271 -> Gercenova (~60 minut) **tram 2 -> Dejvická, metro A -> Skalka, bus 154,271 -> Gercenova (~60 minut) * Motol **bus 179,184 -> Nemocnice Motol/Motol (~15 minut) * Karlovo náměstí, Albertov **tramvaj 18 -> Karlovo náměstí/Albertov (~30 minut) **bus 191 -> Anděl, tram 7 -> Albertov (~30 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 75: | Line 80: |
| == Odkazy == | ### Test program |
| Line 77: | Line 82: |
| [http://www.vetrnik.koleje.cuni.cz/ www.vetrnik.koleje.cuni.cz/] Stránky KR Větrník | 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 79: | Line 89: |
| [http://www.vetrnik.koleje.cuni.cz/diskuse/ www.vetrnik.koleje.cuni.cz/diskuse/] Diskuzní fórum | 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 81: | Line 94: |
| [http://www.ff.cuni.cz/dok/studium/lekar.php http://www.ff.cuni.cz/dok/studium/lekar.php] Ordinace praktického lékaře pro studenty na Hvězdě | ### Your implementation |
| Line 83: | Line 96: |
| == Akce, možnosti == | 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 85: | Line 101: |
| Nechce se vám tahat knihy na kolej? Pro studenty dějin umění, kulturologie, historie a podobných oborů je tu řešení: [http://obrazar.2web.cz/obrazar/knihovna.phtml MiniKnihovna na Větrníku] | ### Hints |
| Line 87: | Line 103: |
| A ještě pro studenty dějin umění: sháníte zkušnosti, grantovou historii, položky do CV? http://obrazar.2web.cz/obrazar/mista.phtml |
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 90: | Line 108: |
| Na koleji funguje už delší čas klub [http://www.coolnicka.cz Coolnička], který vedou převážně křesťani z koleje. Pořádá mimo jiné středeční diskuzní večery a pondělní kavárnu [http://www.coolnicka.cz/index.php?htm=mm&mnu=4 Mississipi Mud]. | 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 92: | Line 119: |
| == Adresa == Kolej Na Větrníku Na Větrníku 1932 162 00 Praha 6 - Petřiny |
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 97: | Line 126: |
| bloky I-II: čp. 1931, blok III: čp. 1933, blok IV: čp. 1934 (Pokud nechcete hledat poštu po všech blocích koleje, pište do adresy přesný blok a pokoj) [[Category:Koleje]] |
Source code templates can be found in [git](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). ## 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_. 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. 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. You should submit the `ab_tree.*` file (but not `ab_tree_test.*` files). Source code templates can be found in [git](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |