Matfyz Wiki
Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| Seznam je řazen podle abecedy. | # **NTIN066** Datové struktury I: Úkoly 2024 |
| Line 3: | Line 3: |
| * [http://montyb.borec.cz/ Martin Bezdíček] ** něco fotek z matfyzu, něco dalších fotek a vlastní prózy, prostě nuda * [http://martin.alikuvkoutek.cz/ Martin Cetkovský] ** informatika, admin [http://citaty.matfyz.cz Citátů MFF], správce [http://www.kolej.mff.cuni.cz kolejních stránek 17. listopadu], člen (převážně matfyzáckého) [http://sebranka.matfyz.cz pěveckého sboru Sebranka], syn své maminky :) ** [http://basnik.alikuvkoutek.cz/ amatérské básničky] (některé i poměrně kvalitní), [http://vtipy.alikuvkoutek.cz něco pro úsměv], [http://mcsoftware.alikuvkoutek.cz/?FID=70& program proti zapomínání] (Windows) * [http://cendo.skialpfest.sk Peter Čendula] ** skialpy, hory, blog * [http://jojo.matfyz.cz/ Marián Černý] ** zatiaľ nič zaujímavé * [http://www.decky.cz/ Martin Děcký] ** informatika, nějaké [http://projects.decky.cz/ projekty] a [http://lectures.decky.cz/ přednášky] * [http://starec.blog.zive.cz/ Vladimír Dědek] ** C#, ASP.NET, SQL a mnohe dalsi * [http://joshis.iprofil.cz/ Petr Dvořák (Josh)] ** článečky, diskuze, fotogalerie, studijní podklady * [http://www.jail.sk Ján Ilavský (Jail)] ** hudba, zatiaľ nič moc * [http://pavelmotal.zzl.org/ Pavel Motal] ** osobní web: moje práce, odkazy, galerie, chat, atd... * [http://www.koupy.net/ Petr Koupý] ** osobní web, programy * [http://www.aleskrajnik.cz/ Aleš Krajník] ** Wing Chun, PHP, Fotky focené pro radost ... * [http://andree.sk/ Andrej Kruták (andree)] ** informatika, moje projekty, domáce úlohy z C, Pascalu, neprocedurálka... a rôzne iné halušky ;-) * [http://kryl.info Milan Kryl] ** informatika, řešené příklady pro cvika z UNIXu, citáty vyučujících na MFF UK, ... * [http://www.kulman.sk Igor Kulman] ** weblog o webových technológiách a Windows Vista, ModularCMS * [http://mach.matfyz.cz Lukáš Mach] ** zápisky z přednášek (viz červený odkaz - hlavně Teorie her + nějaké náhodné věci) a spálený chleba * [http://www.majda.cz David Majda] ** informatika, [http://www.majda.cz/zapisnik/ zápisník] (především o programování), stránky s [http://ekonomie.majda.cz/ materiály ke Kameníčkově ekonomii], pár dalších věcí * [http://www.jakubmaly.cz Jakub Malý (trupik)] ** Jakub Malý, osobní stránky a blog * [http://www.nekola.cz Ondra Nekola (satai)] ** Jsem Šedý, stojím mezi svící a hvězdou. Jsme Šedí, stojíme mezi světlem a temnotou. Java, Mac OS X, programování v reálném světě a sci-fi. * [http://www.cs.wm.edu/~dnguyen/ David T. Nguyen] ** Osobní stránky absolventa. MFF, Boston, Stanford, W&M, Facebook. * [http://urtax.ms.mff.cuni.cz/~novap2am/ Petr Novák (che)] ** nějaké poznámky, fotky, nově přidaný odkaz na Královskou společnost pro sprchování s rodiči * [http://ivokabel.wz.cz Ivo Pavlík] ** Niečo o mne, nejaké obrázky... * [http://artax.karlin.mff.cuni.cz/~pecaj2am Jakub Pečánka (pecan)] ** studium (matematika a ekonomie), doučování, obecné info, ... * [http://artax.karlin.mff.cuni.cz/~pestm1am Michal Pešta (Mišisko)] ** hory, foto, básne, matematická štatistika, ... * [http://www.tydlin.cz Tomáš Pop (Ty-Dyt nebo Tydlin)] ** Osobní stránky, ale celkem hodně věcí ze studia z MFF, ... * [http://anja.matfyz.cz/ Anička Roubíčková] ** informatika, zápisky z přednášek a cvičení * [http://j4ro.livejournal.com Jan Rouš (ja.ro)] ** blog * [http://atrey.karlin.mff.cuni.cz/~miero/ Miroslav Rudišin (miEro)] ** informatika, správca [http://artax.karlin.mff.cuni.cz/ artax-u], ... * [http://gk2.sk/ Pavol "stick" Rusnák] ** #cypherpunk #hacker #openhw #privacy #bitcoin #newmediaart * [http://www.volny.cz/amiginka/moje/ Jitka Setíkovská (Amiginka)] ** matematika, hlavně úkoly na Výpočetní prostředí pro statistickou analýzu dat, RC5-72 team UK * [http://artax.karlin.mff.cuni.cz/~sotam0am Miroslava Sotáková (mirka)] ** zápisky z ciest, fotky, časom a príležitostne i tá matematika * [http://www.lukysoft.cz Lukáš Stehlík (Luky)] ** informatika, zápočtáky, ročníkáče a moje jiné projekty * [http://www.suchan.cz Martin Suchan] ** blog, fotky, občas zmínka o mé tvorbě na MFF * [http://jsimlo.sk/ Juraj Šimlovič (jsimlo)] ** kopa blbostí, pár zápočťákov [http://jsimlo.sk/home/projects.php tu], editor [http://jsimlo.sk/notepad/ TED Notepad], .. * [http://srakyi.modry.cz/blog/ Michal Šrajer (srakyi)] ** pokus o blog na téma [http://srakyi.modry.cz/blog/ softwarové inženýrství] * [http://andrew.matfyz.cz Ondrej Šterbák (andrew)] ** informatika, nejaké programíky, odkazy.. * [http://www.expost.cz/ František Štrupl] ** Především odkazy na praktika a diferenciální geometrie. * [http://hanasustkova.ic.cz Hana Šustková] ** Stránky o MFF, časopisu Lacadalet a jen tak * [http://kdybynahodou.wz.cz/ Julie Švecová ] **Kdybynáhodou: blbosti, citáty,povídky.. prostě osobní stránky.. * [http://www.josiff.net Jozef Sabo (JosIFF)] ** blog, nejaké fotky a linky, samozrejme guestbook... * [http://www.martinvseticka.eu Martin Všetička] ** Programování I. - řešené úlohy z Pascalu, různé notace (postfix, prefix, infix) v C#; Úvod do UNIXu - zápisky ze cvičení z UNIXu a pár řešených zkouškových úloh |
## 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. ## 3. `Goal` 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. You are given a test program (`splay_experiment`) which calls your implementation from the previous assignment to perform the following experiments: - _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. The program tries each experiment with different values of _n_. In each try, it prints the average number of rotations per splay operation. 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_. - 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. 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.) 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. ### Test program 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`). 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. ### Your implementation 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. ### Hints The following tools can be useful for producing nice plots: - [pandas](https://pandas.pydata.org/) - [matplotlib](https://matplotlib.org/) - [gnuplot](http://www.gnuplot.info/) 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?) 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) 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). |