yea erster - After test thread 19.10.2007

[sebus]

Hi!

Ich eröffne mal den After-Test Thread zum heutigen (Freitag, 19.10.2007) Test.

Ich fand den Test nicht sehr schwer, hab' ihn aber wohl doch versaut, weil zuwenig gelernt. :mad:

Vorallem beim Berechnen der Hash-Tabellenwerte mit der Sondierung (egal welche) machte mir Kopfzerbrechen weil ich das genau ein einziges mal geübt habe.

Außerdem hab ich bei der Laufzeitanalyse keine Ahnung gehabt.

Quicksort war eigentlich easy, mit Laufzeit T(min) = n und T(max) = n*log*n;
Beispiel:
Maximales Sortieren 1 2 3 4 5 6 7 8 9 10;
Minimales Sortieren ? Wusst ich nicht;

Preorder, Inorder ging auch, Baum zeichnen Post-Order;

Für das Traverse hatt ich keine Zeit mehr.

Indexed Trie -> Suffix Compression (hab ich auch nich geschnallt, hab da nichts mehr zum komprimieren gefunden!)
Packed Trie -> Lustige Schraffierarbeit :)

Wie ging's euch so, was meint ihr zum Test?

Lg,

derSeb

[matrium]

beispiel 1
a)
kam ich auf ne laufzeit von theta n^3 log n .. kann das jemand bestätigen? demnach hab ich dann n^3 als untergrenze angegeben und n^3xWURZEL(n) als obergrenze
b) hatte ich nicht wirklich plan wie man einen algorithmus macht der n^3 x log n laufzeit hat, habs dann ungefähr so versucht, ist aber falsch

x = n
für i= 1..x
{ für j= 1...x
{ für h= 1... x
{ für k=1...n
{ n= n/2
}}}}c) den beweis wusste ich auch nciht sorecht wie ich das angehen soll.. habs dann ungefähr so versucht
aus f(n) = theta(g(n)) folgt dass f(n) = O(g(n)).. d.h. es existiert c,n0 > 0 sodass für alle n>n0: 0 <= f(n) <= c g(n)
und daraus folgt dass auch ein c1 = c*(2/3) exisiteren muss sodass für alle n > n0 gilt : 0<= f(n) <= c1 g(n)
.. hm meint ihr reicht das? :(

beispiel 2 (meine große hoffnung)
a) hm quicksort hat doch n log n im bestcase und n^2 im worst case, oder? aaarrg bitte lass es so sein! worstcase ist bereits aufsteigend sortierte folge, beim bestcase dachte ich muss das pivotelement die menge idealerweise immer halbieren, aber habs trotzdem falsch gemacht (verdammt, hätt ich das doch wenigstens textuell hingeschrieben :( )
b)hab ich geantwortet dass merge-sort in dem fall besser wäre weil er im gegensatz zu quicksort nur konstant viel zusätzlichen speicherplatz benötigt.
c) insertion sort und selection sort durchführen müsste ich richtig haben (hoff)

beispiel 3
a) was war da gemeint mit schreiben sie die hashfunktion auf?? nur das h(n) = h1(n) + i*h2(n) ??? sonst denk ich müsste ich das richtig haben, ohne brent kam ich auf 4 kollisionen, mit brent gab es nur 1-2 kollisionen (je nachdem ob man da j1 mitzählt, j2 hat dann gepasst)
b) tjaaa dachte echt das WENN hashverfahren kommt kommt allerhöchstens double hasing, hab mir also quadratisches sondieren (obwohl es einfach ist) garnicht angesehen und demnach hier wahrscheinlich 0 punkte

beispiel 4
einigen wir uns darauf dass es auf meiner angabe kein beispiel 4 gab, ja? (blackout)

beispiel 5
alle möglichkeiten aufschreiben war ja watschneinfach.. suffix compression war ich mir schon nichtmehr sicher, gab aber 2 knoten die völlig gleich waren und die habe ich halt zusammengelegt.. glaube/hoffe das müsste passen
packed trie uiuiui mit dem steh ich auf kriegsfuß, also hab das irgendwie hingemurkst, ist zwischen 0 und 6 punkten alles drin glaub ich (aber eher 0 xD)

ingesamt sind meine chancen mies, da müsste wirklich alles was ich hingeschrieben hab richtig sein damit ich auch nur ne winzige chance hab.. besonders dass ich das mit der durchmusterungsreihenfolge so verschissen hab ärgert mich weil das wirklich 4geschenkte punkte waren und der pseudo-code.. naja..

[sebus]

hab beim laufzeit-analyse beispiel denke ich genau gleich angekreuzt wie du! also erste zeile glaub ich war dann
"X X X"
"- - X"
"X - -"
was 2. und 3.zeile war, weiss ich nimma - kann ich auch genau falsch angekreuzt haben - jedenfalls hat ich auch den eindruck dass die spalte "keines" fürn hugo war :)

Bei Suffix Compression habe ich mich natürlich schon beim Wortbilden "verlesen" - vielleicht ein Freudscher Verleser, denn bei mir war das längste Wort das bildbar war "P O T" und nicht "P O L" :)
Dachte mir schon, witzige Menschen die den Test gemacht haben, bin dann aber noch auf meinen Fehler draufgekommen (hatte ein end = T als Buchstaben interpretiert anstatt Buchstabe "l" ).

Gemeinsame Endungen hab ich zwar schon auch entdeckt, ich hatte aber den Eindruck, dass egal was ich "umlenke", dadurch neue Wörter erlaubt worden wären die im ursprünglichen W nicht vorgekommen sind.
-> War mir da aber auch plötzlich total unsicher, wie ich das sonst immer gemacht habe - war denn der indexed trie vielleicht schon (zumindest) parziell komprimiert?

[sebus]

beispiel 2 (meine große hoffnung)
a) hm quicksort hat doch n log n im bestcase und n^2 im worst case, oder?

Hmm, ich glaub betreffend worst case hast du recht;
Hatte ich zuerst genauso, aber ich hab mich dann entsinnt, dass im Skriptum extra gestanden ist, dass theta(n) = n² FALSCH in irgendeinem Buch drin steht - vielleicht finde ich die Stelle im Skriptum wieder (habe Skriptum SS04) - das ist aber anscheinend bezogen auf die Bewegungen, d.h. die Anzahl der Bewegungen im schlechtesten Fall sind n*log n und gesamt n²
Damn!

Na super, beim anderen hast du's auch richtig und ich falsch - ich hab (n), weil das die bekackten Bewegungen sind, ach menno, so ein dreck.

Das iss mal wieder typisch, schnell schnell im Skript drüber lesen und nicht denken und dann beim Test intuitiv das richtige Eintragen, um es später auszustreichen und das Falsche reinzuschreiben.

Ich könnt heulen :wein:

[matrium]

aufjedenfall wird dein packed trie falsch sein wenn du vorher nicht die suffix compression gemacht hast.. aber wer weiß wenn es sonst stimmt springen bestimmt trotzdem punkte ab

ich hab einfach nach "doppelten" knoten gesucht.. wenn diese dann übereinstimmen kannst du noch weiterschaun ob vl sogar ihre "vorgänger-knoten" übereinstimmen.. dann kannst du sogar 2 (oder mehr.. ) knoten ersetzen
bsp: (die v sollen pfeilköpfe darstellen :D)

a->b->d
| |
v v
e->f g
wenn jetzt z.b. f und g genau gleich sind kannst du einen der beiden entfernen und die pfeile halt auf den andren umlenken.. außerdem kannst du dann noch weitersehen, wenn z.b. d und e auch übereinstimmen kannst du gleich e+f (oder d+g) entfernen
wahrscheinlich gibts schwierigere fälle auch, aber ich hab beim test nur nach genau gleichen knoten gesucht, bei denen kann auf keinenfall was schief gehn (sprich: neue wörter entstehen).. und so konnte ich genau einen knoten eliminieren, hoffentlich war da nicht mehr zu machen

ah oki bin ich froh (sry :) )

[IRBaboon]

Die Angabe der Pruefung vom 19.10.2007 ist ab sofort ueber die aktuelle LVA-Homepage erreichbar bzw. direkt ueber diesen Link:

http://www.ads.tuwien.ac.at/teaching/archiv/186089/20071019.pdf

I.R.Baboon

[matrium]

na dann heißts mal warten auf die ergebnisse.. hoffentlich nicht zuuu lange, wenn ichs versaut hab tret ich wahrscheinlich beim nächsten termin nochmal an solang der stoff noch "sitzt"
viel glück allen :-)

[myst1cal]

GL an alle auf ne positive note!
schon langsam nervt mich das fach=)

[mjx_biz]

Ich hab keine Ahnung mehr, was ich alles geschrieben hab. Bin rausgegangen und habs sofort verdrängt :D.

ich weiß nur noch, dass ich ein Blackout bei Traverse() hatte :/. Hinter den Algorithmus bin ich nicht gekommen und dann war ich so fertig, dass ich nicht einmal den Baum zeichnen konnte :(. GsD hab ich das Beispiel zum Schluss gemacht.

Die anderen Beispiele waren ganz ok glaub ich, nur beim Packed Trie hab ich mich dann noch vertan. Bin bei der Kontrolle draufgekommen, dass er zu viele Wörter ausspuckt :sudern:.

Naja, abwarten und Tee trinken ... ... ... wie lange denn ca., Mr. Baboon? Nicht, dass ich drängen will, aber ich bin schon sooo neugierig ;).

[IRBaboon]

Waren ja nur 25 TeilnehmerInnen, d.h. es sollte sich diese Woche mit den Ergebnissen ausgehen. Aber wie immer, ich verspreche gar nichts.

I.R.Baboon

[mjx_biz]

Waren ja nur 25 TeilnehmerInnen, d.h. es sollte sich diese Woche mit den Ergebnissen ausgehen. Aber wie immer, ich verspreche gar nichts.

I.R.Baboon

25? Laut TUWIS++ war der letzte Stand 37 glaube ich. Da sind dann ein paar wohl doch draufgekommen, dass sie zu wenig gelernt haben ;).

Danke jedenfalls für die Info =)!

[toxiscm]

1.A a.) Geht da nicht die erste Funktion gegen n^3 weil n^2*log(n^n) is ja eigentlich n^3 oder lieg ich da falsch ?
und nur die zweite funktion gegen n^3 * log (N)

helft mir wo is mein denkfehler ?

[matrium]

1.A a.) Geht da nicht die erste Funktion gegen n^3 weil n^2*log(n^n) is ja eigentlich n^3 oder lieg ich da falsch ?
und nur die zweite funktion gegen n^3 * log (N)

helft mir wo is mein denkfehler ?

log (a^b) = b * log a

in dem fall: n^2 * log(n^n) = n^2 * n * log n = n^3 * log n

[mjx_biz]

Noten sind da =)!

Bei mir is es ein 3er geworden und das reicht mir vollkommen. Hauptsache is, dass ich das Thema jetzt abgeschlossen :D.

[IRBaboon]

Ich weiss nicht, sitzt du den ganzen Tag vor dem Rechner und drueckst im Browser bei des Notenabfrage "reload" ... "reload" ... "reload" ... "reload" ... "reload" ... "reload" ... "reload" ... "reload" ...? Wir haben das gerade mal vor rund 10 Minuten online gestellt, und jetzt wollte ich das hier schreiben ... und schon zu spaet. :)

Naja, eine Neuigkeit hab ich trotzdem: Einsichtnahme wird es kommenden Dienstag, 30.10.2007, 14:00-15:00 bei Fr. Potocka geben. Danach wuerden wir die Zeugnisse ausstellen, d.h. ... naja, da liegen irgendwie Feiertage ... sagen wir ab rund 5.11. muessten die Zeugnisse dann in der Studien- und Pruefungsabteilung abholbereit sein. Wem das zu spaet ist, der soll sich bitte direkt an mich bzw. die aktuelle AD1-Hotline algodat1-ws07@ads... wenden.

I.R.Baboon

[matrium]

wuhuu nen 3er:omg:.. alter verwalter da muss sogut wie alles was ich hingeschrieben hab richtig gewesen sein, nachdem ich bsp 4 garnicht gemacht hab muhuhahahahahahahahaha :-)

und ich dachte echt ich hab zu 90% nen fetzen weeeeiiiil: ein beispiel nicht gemacht+ probleme bei 1b und c + probleme bei packed trie + riiieeesen problem bei quadratischem sondieren

gratulation auch an alle andren die es gepackt haben..

[mjx_biz]

Ich weiss nicht, sitzt du den ganzen Tag vor dem Rechner und drueckst im Browser bei des Notenabfrage "reload" ... "reload" ... "reload" ... "reload" ... "reload" ... "reload" ... "reload" ... "reload" ...? Wir haben das gerade mal vor rund 10 Minuten online gestellt, und jetzt wollte ich das hier schreiben ... und schon zu spaet. :)
:verycool: Nein, hab nur einmal am Vormittag nachgesehen und jetzt wieder. Hab anscheinend gespürt, dass sie schon eingetragen wurden. Tut mir leid, dass ich dir die fröhliche Botschaft weggenommen hab :p.

[matrium]

hehe aber ich bin so einer, hab glaub ich die letzten tage jeeede menge notenabfragen gemacht oder so *ggg*

paar leute wie mich und wir killn euren server :tongue1: