Matfyz Wiki
Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| # Matfyzácké vtipy | # **NTIN066** Datové struktury I: Úkoly 2024 |
| Line 3: | Line 3: |
| Na statku onemocnělo kuřátko. Hospodář už si nevěděl rady co s ním, a proto si zavolal tři odborníky: biologa, chemika a fyzika. Biolog zkoumal, jestli kuřátko nemá parazity, jestli náhodou nechytilo nějakého bacila, ale na nic nepřišel. Chemik zjišťoval, zdalipak se kuřátko něčím nepřiotrávilo, ale podle něho bylo taky v pořádku. No a fyzik se na kuřátko ani nepodíval, sedl si ke stolu a dva dny zuřivě počítal. Pak se zvedl a zvolal: "Vím co je vašemu kuřátku! A vím jak ho vyléčit! Ale moje řešení platí jen pro sféricky symetrické kuře ve vakuu!!!" |
## 1. `tree_successor` |
| Line 9: | Line 5: |
| ---- | 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 11: | Line 10: |
| Květnová noc, matfyzák s matfyzačkou v parku na lavičce. "Miláčku, myslíš na to co já? " "Myslím... " "A kolik ti to vyšlo?" ---- |
- 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 18: | Line 14: |
| Na co myslí matfyzák, když vidí červené kolečko? Na sex. A proč? Protože matfyzák myslí na sex pořád. |
You can expect that `successor` method is never called on an empty tree. |
| Line 23: | Line 16: |
| ---- | You should submit the file `tree_successor.*` (but not the `tree_successor_test.*`). |
| Line 25: | Line 19: |
| Biolog, fyzik a matematik zkoumají výtah. Do výtahu nastoupili 2 lidé a odjeli nahoru. Výtah se vrátil a vystoupili 3 lidé. Jak je to možné? Biolog: "Rozmnožili se." Fyzik: "Chyba měření." Matematik: "Když teď jeden vyjede nahoru, nebude tam nikdo." |
Source code templates can be found in [the git repository](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 33: | Line 21: |
| ---- | ## 2. `splay_operation` |
| Line 35: | Line 23: |
| V hotelu spí inženýr. Hotel je to ale nebezpečný a v noci mu na pokoji vypukne požár. Zápach hořícího koberce ho probudí, tak doběhne k umyvadlu, natočí kýbl vody a oheň uhasí. |
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 38: | Line 29: |
| Za rok tam spí fyzik. Jenže co se nestane, zase to tam chytne. Fyzika to také probudí, vytáhne si zápisky z přednášek, numericky vyřeší pár diferenciálních rovnic, natočí do kýble 7,8666667 litrů vody, oheň uhasí a jde si lehnout. |
You should submit the `splay_operation.*` file (but not the `splay_operation_test.*`). |
| Line 42: | Line 32: |
| Za další rok tam spí matematik. Zase mu tam hoří. Vstane, dojde k umyvadlu, zkusí, jestli teče voda, zjistí, že řešení existuje, a jde si lehnout. |
Source code templates can be found in [the git repository](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 46: | Line 34: |
| ---- | 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 48: | Line 39: |
| Zavřou do tří paralelních hladomoren inženýra, fyzika a matematika. Každému dají jednu libovolně velkou, leč pevnou konzervu a nechají je vegetovat. Pak příjde amnestie. V první hladomorně je živý inženýr, ostře nabroušený kámen a otevřená konzerva. Ve druhé hladomorně je živý fyzik, stoh popsaných papírů, otevřená konzerva a geniální zařízení na otvírání konzerv zkonstruované ze skřipce a španělské boty. Ve třetí hladomorně je mrtvý matematik, zavřená konzerva, stoh popsaných papírů, z nichž každý začíná: "Nechť je konzerva otevřena." |
|
| Line 58: | Line 40: |
| ---- | ## 3. `Goal` |
| Line 60: | Line 42: |
| Seděj funkce v hospodě a chlastaj. V tom se na obzoru objeví derivace. Všechny funkce se rychle běží schovat ven do křoví, jenom jedna v pohodě popíjí dál. "Neblbni, uteč taky, jinak tě zderivujou! " "Jen klid, já jsem e na ixtou. " Do hospody vtrhnou derivace, nějakou dobu se tam na ubohý funkci vyžívaj a nakonec vítězně odtáhnou. Pak se z hospody vybelhá ubohý nulový mrzáček. "Jak ti to udělaly, vždyť jsi byla e na ixtou. " "No jo, jenže oni mě derivovaly podle y." |
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 70: | Line 46: |
| ---- | You are given a test program (`splay_experiment`) which calls your implementation from the previous assignment to perform the following experiments: |
| Line 72: | Line 50: |
| Jede opravář, ředitel a programátor autem. Auto se porouchá a nejede. opravář: "Hned za rohem je servis, to dotlačíme." ředitel: "To je blbost, koupíme nový auto." programátor: "Já bych ještě zkusil vystoupit a zase nastoupit." |
- _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 78: | Line 59: |
| ---- | The program tries each experiment with different values of _n_. In each try, it prints the average number of rotations per splay operation. |
| Line 80: | Line 62: |
| Co se stane, když vyhoděj matfyzáka a ten pokračuje ve studiu na VŠE? Prudce vzroste úroveň obou škol. |
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 83: | Line 66: |
| ---- | - 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 85: | Line 71: |
| Proč nemají matfyzáci jarní prázdniny? Protože by za tu dobu vystudovali VŠE. |
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 88: | Line 76: |
| ---- | 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 90: | Line 80: |
| Kterej pražskej gympl je nejtěžší? VŠE. |
### Test program |
| Line 93: | Line 82: |
| ---- | 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 95: | Line 89: |
| Jak jezdí normální člověk výtahem do třináctého patra? No přece zmáčkne 13. A jak jezdí do třináctky informatik? Zmáčkne 1, pak 3 a zuřivě hledá enter. |
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 100: | Line 94: |
| ---- Jsou takhle dva strašně hladoví MATFYZáci na koleji a jeden povídá druhýmu: Hele co kdybychom tady začali chovat prase?? A ten druhej mu odpoví a co ten smrad a ten hroznej bordel?? A ten první říká:ono si zvykne… |
### Your implementation |
| Line 106: | 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 108: | Line 101: |
| Potkají se čarodějnice s misskou. Baví se o životě a také dojde řeč na plány do budoucna. Obě dvě chtějí studovat. Misska říká:„Já půjdu na VŠE. Sice tam nebudu nejhezčí, ale určitě budu nejchytřejší.“ To čarodějnice má jiné plány: „Já se chystám na matfyz. Tam zcela jistě nebudu nejchytřejší, ale určitě budu nejkrásnější.“ |
### Hints |
| Line 115: | Line 103: |
| ---- | 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 117: | Line 108: |
| Potkají se dvě matfyzačky a jedna se svěřuje s hrozným zážitkem: „Představ si, co se mi stalo. Jdu kolem Vltavy a najednou proti mně úchylák! Tak jsem na nic nečekala a začala jsem co nejrychleji utíkat.“ A ta druhá se dychtivě ptá: „A co, dohonilas ho?“ |
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 122: | Line 119: |
| ---- | 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 124: | Line 126: |
| Jdou tři holky: První je ošklivá, druhá je hnusná a třetí je taky z Matfyzu. |
Source code templates can be found in [git](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 127: | Line 128: |
| ---- | ## 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 129: | Line 132: |
| Jak řeší matfyzák úlohu, kolik je 2 na druhou? | 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 131: | Line 137: |
| Prvák bez zaváhání odpoví, že to jsou 4. | 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 133: | Line 141: |
| Druhák se trošku zamyslí, ověří všechny předpoklady a na kalkulačce spočítá, že to jsou čtyři. | You should submit the `ab_tree.*` file (but not `ab_tree_test.*` files). |
| Line 135: | Line 143: |
| Třeťák napíše několikastránkový program v Pascalu nebo Céčku a po několika hodinách práce doje k výsledku čtyři, ovšem s přesností omezenou kapacitou počítače. | Source code templates can be found in [git](https://gitlab.kam.mff.cuni.cz/datovky/assignments/-/tree/master). |
| Line 137: | Line 145: |
| Čtvrťák se zamyslí a už sedí u počítače a vymýšlí nový programovací jazyk vhodný právě pro tento druh úlohy. Po probdělé noci strávené usilovnou prací dostane odpověď, že jsou to asi čtyři, ale není si výsledkem zcela jist, protože použitá metoda je pouze aproximativní a přesnější výsledek by si vyžádal mnohem větší úsilí Pokud tu samou otázku položíte páťákovi před státnicemi, zoufale složí hlava do dlaní a rozpláče se se slovy: „Copak si musím všechny konstanty pamatovat?“ ---- Jede matfyzák tramvají a cvaká si lístky. Vidí ho chlápek, nedá mu to a zeptá se: „Prosím vás, proč si cvakáte najednou dva lístky?“ „No kdybych jeden ztratil, tak mám ještě jeden.“ Chlapíkovi to přijde logické, ale za chvilku se ptá znovu: „A co když ztratíte oba dva?“ Matfyzák se šibalsky usměje a povídá: „Tak mám ještě lítačku!“ ---- Přijde matfyzák do fotolabu: „Potřeboval bych vyvolat fotky.“ Prodavač: „9 na 13?“ „2541865828329 - Proč?“ ---- Profesor na přednášce zformuloval větu a řekl: „Důkaz je zřejmý.“ Pak se na minutku zamyslel, opustil posluchárnu a po dvaceti minutách se vrátil štastný: „Ano, důkaz je zřejmý!“ ---- Víte proč pařez není strom? Protože má kružnice. ---- na hodine deskripce: "Máme koule psí a mí." ---- „Pane profesore, našel jsem dva protipříklady k vašemu tvrzení“ „To nevadí, já mám pět důkazů.“ ---- Zvolme epsilon záporné… ---- Einstein-Pythagorova věta: e = mc² = m.(a²+b²) ---- Proč si matfyzáci pletou Halloween a Vánoce? Protože OCT 31 = DEC 25. ---- Jak informatik neudělal přijímačky na VŠE. Přijde matfyzák informatik na přjímačky na VŠE, otázky zní: - Kolik je 5 + 3? - 8, okamžitě odpoví. - Správně. Dejme si něco těžšího. Kolik je 9 + 7? - 16, opět okamžitě odpoví. - Skvěle, a teď nejtěžší příklad. Kolik je 2 - 3? - 255. ------- Přijde matfyzák č. 1 pozdě na cvičení, cvičitel se zlobí a ptá se ho, kde byl. „No, já ráno vstal, tak sednu na koně a jedu do školy, ale na Štrosmajeráku, znáte to jaká je tam vždycky zácpa, mi ten kůň z toho smogu padnul. Tak jsem musel jít pěšky.“ Cvičitel jen kroutí hlavou, ale nechá ho sednout a pokračuje. Za chvíli dorazí matfyzák č. 2. Cvičitel se opět ptá, kde se flákal. „Já jsem ráno zaspal, tak okamžitě sedlám koně a ženu do školy, ale víte ta dopravní situace, šílený vzduch, prostě na Štrosmajeráku to ten kůň už nevydržel.“ Cvičitel už tomu nevěří, ale tak zatne zuby a pokračuje dál ve výkladu. Pět minut před koncem dorazí matfyzák č. 3, tak se na něj oboří: „CO VY, TAKY VÁM PADNUL KŮŇ??“ „Ale ne, já normálně jsem ráno vstal, jedu do školy dvanáctkou, ale na Štrosmajeráku nemohla projet, protože tam leželi přes cestu nějaký chcíplý koně!“ ----- Víte proč nosí matfyzáci kostkované košile? Aby si určili souřadnice kde je svědí záda… ----- Sestoupí Bůh na Zemi a prochází se ulicemi. Tu pojednou spatří plačící ženu a ptá se jí: "Proč pláčeš?" Ona odpoví: "To víte, umřel mi manžel." Bůh je dojat a říká: "Je to velké neštěstí, a proto Ti manžela pošlu zpátky na Zem." Jde dál a náhle uvidí plačící děcko. Ptá se, proč brečí. Dítě mu odpoví, že ztratilo oba rodiče. Bůh se slituje a povolá rodiče zpátky k dítěti. Popojde o kus dál a vidí, jak na obrubníku chodníku sedí student. Student řve, až se domy třesou, a naříká. Bůh se ptá, proč on pláče. Na to odpoví: "Víte, já jsem student Matematicko-fyzikální fakulty." Bůh usedl vedle něho a plakali oba. ----- Dva programátoři v TV vědomostní soutěži: Takže pane Jaroslave, pan Zbyněk dostal na papírku jméno osobnosti a vy máte hádat, kdo to je, a to jen pomocí otázek, na které Pan Zbyněk může odpovídat jen "Ano" nebo "Ne". Jaroslav: Jaké je jméno osobnosti kterou představujete? Zbyněk: Ne, ano, ne, ano, ne, ne, ano, ano; ne, ano, ano, ne, ne, ano, ne, ano; ne, ano, ano, ne, ne, ne, ano, ne; ne, ano, ano, ne, ne, ano, ne, ano; ne, ano, ano, ano, ne, ano, ne, ne; ne, ano, ano, ne, ano, ano, ano, ano; ne, ano, ano, ano, ne, ano, ano, ne; ne, ano, ano, ano, ne, ne, ano, ano; ne, ano, ano, ne, ano, ne, ano, ano; ne, ano, ano, ano, ano, ne, ne, ano; ----- Potká matfyzák matfyzáka. To nevíš co se mi včera stalo. Povidej. Šel jsem v noci po parku, a najednou tam přijede ženská na kole, svlíkne se, a říká abych si vzal co chci. Tak jsem si vzal kolo. Tos udělal dobře, ty šaty by ti stejně byly malý. ----- Přijde do hospody nekonečně mnoho matematiků a začnou si u hostinského postupně objednávat. První si dá pivo, druhý půl piva, třetí čtvrt piva atd. Hostinský povídá: "Vy jste ale pitomci," a přinese jim dvě piva. ----- Theorem: a cat has nine tails. Proof: A cat has one tail more than no cat. No cat has eight tails. Therefore, a cat has nine tails. ------- Matematikové potřebují k práci jen tužky, papíry a odpadkové koše. Filozofům potřebují ještě méně - těm stačí tužky a papíry. ------- Hrají v nebi na schovávanou Watt, Newton a Pascal, Watt stojí u pikoly. Pascal se utíká schovat, Newton kolem sebe nakreslí čtverec metr krát metr. Watt skončí, otočí se a povídá "Deset, dvacet, Newton!" "Já nejsem Newton, já jsem Pascal!" ------- Zena posiela manzela-programatora na na nakup: "Chod kupit dve nozicky klobasy. A ked budu mat vajicka, vezmi desat." Programator vojde do obchodu. "Dobry den. Mate vajicka?" "Ano." "Tak mi dajte desat noziciek klobasy." ------- Jede Pepíček s babičkou ve vlaku a povídá jí: "Babi, koukni se na tu množinu kraviček, co se pase na louce!" "Co to kecáš kluku, jaká množina kraviček? Vždyť tam žádné nejsou..." "Ale to je prázdná množina, babičko..." ------- Paradox množin: "Ty jsi úplně největší kokot, takový kokot, že kdyby byla soutěž všech kokotů, skončil bys druhý!" "A proč druhý?" "No protože jsi kokot!" ------- nemám rád faktoriál. nemám faktoriál rád. rád nemám faktoriál. rád faktoriál nemám. faktoriál nemám rád. faktoriál rád nemám. ------- Novinář, fyzik a matematik jedou po Americe vlakem, a koukají se z okýnka. Za oknem jsou pastviny a na nich se pasou krávy. Jedou už půl hodiny a stále vidí jen samé černé krávy. Novinář prohlásí: "To je k nevíře, v Americe jsou všechny krávy černé!" Fyzik na to: "To je sice zajímavé, ale není to tak úplně pravda - to byste musel říci, že všechny krávy v Americe, "které jsme dosud viděli", jsou černé." Ovšem matematik ho opraví: "Pane kolego, to ale stále ještě není přesné. Musíte říci: 'Všechny krávy v Americe, které jsme dosud viděli, jsou černé "alespoň z jedné strany".'" ------- Mladá dynamická společnost hledá hackera na HPP. Svůj strukturovaný životopis prosím zanechte na našem počítači STANICE1 v adresáři C:\Windows\System\Dokumenty... (na žádné verzi win nebyly dokumenty v adresáři %windir%\System - buď byly v C:\dokumenty, nebo obecně v (%userprofile%||%allusersprofile%)\dokumenty. Správná cesta přes net shares tedy je " STANICE1\c$\<profile\dokumenty>" s <profile\dokumenty> zjištěným přes userenv a přístupem přes vytěžení rootovského share.) ------- Vykládá matka svému synovi (programátorovi), co má nakoupit v obchodě: "Kup třicet deka salámu, a pokud budou mít vajíčka, kup jich deset." Syn pak v obchodě říká prodavačce: "Máte vajíčka?" "Ano." "Tak čtyřicet deka salámu." (poslední věta má znít "Tak deset deka salámu.") ((a o kus výš tenhle vtip už je...) (Ne ty lamo, ty asi matfyzak nebudes ... Tak se chová matematik, ktery tam ma jeste navic dve oddelene vety, takze druha veta lze aspon trochu pochopit jako oprava te prvni. Informatik premysli nasledovne: Nejdriv si zapamatuje, ze chce 30 deka salámu, pak zacne vyhodnocovat podminku, jestli maji vajicka, a ta je kladna, tak koupi dalsich 10. Zkratka [30 AND (if vajicka THEN 10)], 30 a 10 obvykle byva 40. Takze je spis divny ten puvodni vtip s matematikem...) (Nebo taky mohl přinést 3 kg salámu, že?) ------- Co udělá za zvuk kalkulačka kterou hodíte do hnoje? "čvut." ------- Paní učitelka zkouší v první třídě Pepíčka: "Kolik je 1 + 2?" "Tři!" odpoví Pepíček. "A kolik je 2 + 1," táže se dál paní učitelka. "Taky tři, protože binární operace sčítání je na množině celých čísel komutativní." ------- Jak pozve matfyzák jedináček slečnu na rande? "Přijď večer na párty, přijedou všichni bráchové a ségry." |