Datenstrukturen

at Johann Wolfgang Goethe-Universität Frankfurt am Main

Join course
360
Next exam
OCT 01
Discussion
Documents
Flashcards
kann mir wer erklären wie man darauf kommt?
Wäre sehr dankbar wenn jemand die 7.2 Lösung hochladen könnte (grob hingeschmiert würde auch ausreichen)
View 1 more comment
Rückseite der 7.2
Danke!
Guten Abend, ich verstehe leider nicht wie Rekursionsgleichung berechnet wird.. finde auch keine beispiele im internet und keine videos die es erklärt.. kann es mir jemand erklären bitte? Oder eine Quelle schicken wobei man es gut versteht.. Danke im voraus.
bei so einer musst du das solange erweitern, bist du ein Muster siehst, das dann als Summenformel, wenn Summe, aufschreiben und berechnen, ist bissi Tricky, da braucht man einfach Übung (beherrsche es auch noch nicht richtig) sieh dir mal die Nachklausur 2009 an, da gabs eine Aufgabe die war offensichtlicher. Ansonsten bei rekursionen der Form T(n) = aT(n/b) + c ist es einfacher, da benutzt du einfach das Mastertheorem und du bist durch
Die Vorlesung 13 wurde abgeschnitten, war jemand da und kann mir sagen, ob da noch was wichtiges kam? Meistens werden die ja geschnitten, wenn die Anwesenden "belohnt" werden sollen
View 1 more comment
Ah alles klar, ok danke! Also falls wer das mitgeschrieben hat und hochladen kann wäre ich ihm sehr dankbar :)
Wäre auch sehr dankbar wenn das jmd. machen könnte!
Warum gelten diese beiden Sachen?
Kann mir jemanden erklären wie ich den hier lösen kann? Ich verstehe generell mit dem Laufzeiten nicht richtig. Danke sehr schon mal voraus🙈💕✌🏽
View 11 more comments
Danke hgfhj jhjfd. Also wächst e(n) doch schneller als a (n). Hatte mich gewundert, weil mein Tutor meinte es umgekehrt. Aber so macht's natürlich viel mehr Sinn, da das n im Exponenten wächst. Danke nochmal. :)
oh ok, vlt hat dein Tutor das n im Logarithmus übersehen...
noch ne Frage an die die vlt bissi Altklausurerfahrung haben oder ähnliches... Denkt ihr, dass man bei einem (a,b)-Baum auch die Codes können muss oder nur das per Hand durchführen wie bei der 6.2?
In der Erstklausur kamen 3 Aufgaben zu (a,b)-Baum dran, alle im Stil von Aufgabe 6.2 . Einmal insert und zweimal remove (Das linkeste Kind vom linken Knoten und das linkeste Kind vom rechten Knoten). Bei insert war deas Blatt zu groß, man sollte das rekursive mittlere Kind in den Elternknoten packen und die restlichen Kinder aufteilen. Bei remove war einmal eine Fusion gefragt und einmal Schlüselklau/Rotation. Codes dazu wurden bisher noch nie abgefragt. Allerdings war es in der Erstklausur 2019 so, dass ein Code zu Geschwistertausch bei Binärbäumen abgefragt wurde. Bzw der Code war gegeben und man sollte dann halt erkennen, dass das, was dort gecodet wurde, Geschwistertausch bei Binärbaumen sein soll. Also es kann sein, dass vielleicht auch ein Code vorgeben wird und man erkennen soll, das dort was mit (a,b)-Bäumen passiert.
ahhh ok, aber zumindest nicht selbst schreiben, und so Sachen wie aufgabe 6 sind ja so Puktesammler, das ist schonmal gut'
Wie ist man hier auf 2^(n/20) gekommen? Bzw. könnte jemand bitte kurz allgemein erklären, wie man die Rekursionsgleichung 2 * T (n-1) +1 aus dem Code rauslesen konnte?
Aufgabe 5b) Bei einem AVL-Baum ist es doch so, dass die Knoten immer einen Balance-Grad haben müssen, der entweder 0, -1 oder 1 ist. Jetzt hat der Knoten 8 einen Balance-Grad von 2. D.h. dort müsste eine Rechtsrotation durchgeführt werden. Dann wäre die 5 an der Stelle der 8, die 8 rückt einen runter 7 wechselt die Seite und steht nun unter 8 und unter 7 die 6. Unter der 5 würde noch die 3 stehen. Leider versteh ich gar nicht, wieso die 3 hier auf der rechten Seite steht und nicht links von der 4. Kann jemand bitte kurz erklären, (evtl. mit Bild) wie hier rotiert wurde?
schau mal bitte vom Ausgangspunkt aus , da stand die 3 schon da, es ist eigentlich falsch, denn laut Definition ist ein AVL-Baum ein Binärer Suchbaum und somit müsste alles was kleiner als die 4 ist auch links von der 4 stehen... Vlt wurde in diesem Jahr in der Klausur etwas dazu gesagt, so dass man nicht von einer Sortierung aus ging, sondern nur gesagt hat, dass das IDs seien (war diese Jahr auch in einem Beispiel, dort hat er aber auch noch einmal gesagt, dass AVL-Bäume eigentlich sortiert sind)
Weiß jemand von euch was man bei Dijkstra´s in der Klausur machen musste? musste man es schriftlich einfach in Tabellenform durchführen oder coden?
View 3 more comments
In SS 2019 war es so, dass man bei Kruskal den Minimalen Spannbaum und den Union-Find-Baum zeichnen sollte, aber nur bis jeweils zum Einfügen der 6. Kante. Es war also keine Tabelle gefragt, sondern ein MST und ein Union-Find-Baum
Ok alles klar vielen Dank!! :)
Gerade entdeckt dass die letzte Vorlesung in der das Blatt 9 korrigiert wurde nicht online ist. Könnte jmd. die Lösungen hochladen?
Taschenrechner sind bei der DS-Klausur nicht erlaubt, stimmts? Einige Logarithmen von den Übungsblättern (z.B. Aufgabe 2.1) finde ich im Kopf einfach nicht möglich.
Ja, sind nicht erlaubt. Find ich auch etwas unnötig, diese Regelung, aber naja... -.-
Aufgabe 7c) Muss hier an den Stellen 2 und 5 nicht noch nach Größe sortiert werden. z.B. bei der Stelle 5 wurde ja zuerst die 12, danach die 26 und zum Schluss die 19 eingefügt. Deswegen steht bei der Stelle 5: 12 -> 26 -> 19. In allen anderen Altklausuren ist es aber so, dass die Zahlen dann noch aufsteigend sortiert werden, also 12 -> 19 -> 26. Wieso macht man das hier nicht? In den anderen Klausurlösungen wird nach Größe sortiert, in der Klausur hier wird allerdings nach dem Zeitpunkt des Einfügens sortiert. :(
Aufgabe 3b) Was habt ihr bei der Laufzeit raus? Ansatz: T (n) = T (n - 1) + 2n = T (n - 1 - 1) + (n - 1 ) + 2n = T (n - 2) + (n - 1) + 2n = T (n - 2- 1) + (n - 2) + (n - 1) + 2n = T (n - 3) + (n - (k - 1) +....+2n Ist ja so ein bissl wie der "Kleine Gauß", allerdings mit 2n noch hinten dran. Kann man dann einfach sagen, dass das 2n asymptotisch vernachlässigt wird oder ist die Laufzeit n² + 2n ?
soweit ich weiß wird 2n asymptotisch vernachlässigt, vorausgesetzt deine Rechnung ist richtig(hab nicht nachgerechnet)
Danke hgfhj jhjfd.
Aufgabe 4b). Wie kommt man hier auf das Endergebnis? Die Funktion ist T (n) = 2 * T (n - 1) + 1. Dann setzt man rekursiv ein, 2 * (2 * T (n - 1) - 1) + 1) + 1) = 2 * (2 * T (n - 2) + 1) + 1) = 2 * (2 (2 T (n - 2) - 1) + 1) + 1) + 1) = 2 * (2 * (2 * (T (n - 3) + 1) + 1) +1) = 2³ * (T (n - 3) + )1 + 1) +1 Wie kommt man von hier aus weiter?
View 1 more comment
Danke für die Antwort. Mir ist noch nicht klar, wieso 2^n (Potenz). Wenn man dieses 1 + 1 +1 +1 vernachlässigen kann, wieso kann man dieses 2 * 2 * 2 * 2 * usw. (also 2^n) nicht auch asymptotisch vernachlässigen?
2^n ist viiiieeeeel größer als einfach nur Einsen aufsummiert! So weit ich weiß zählt bei Addition dann immer das mit dem stärkeren Wachstum, du hättest also O(2^n + n) (grob geschätzt) dann wäre es asymptotisch O(2^n) aber korrigiere mich ruhig, wenn du denkst ich hab nen Denkfehler, hab aber auch hier nochmal was zu gefunden http://www.tilman.de/uni/ws03/alp/o-notation.php da steht wie man mit der O notation umgeht
Aufgabe 3a) Was habt ihr als Laufzeit raus? Ansatz wäre jetzt: T (n) = T (n - 4 - 4) + 8) + 8 = T (n - 8) + 8) + 8 = T (n - 8) - 4) + 8) + 8) + 8) = T (n - 12) + 8) + 8) +8 .. Weiß leider nicht, wie man das jetzt geschickt vereinfachen soll
Für wie wichtig haltet Ihr die Beweistechnik für die DS-Klausur? Es ist ja das 0te Blatt und am Anfang des Skripts als Wiederholung angegeben? Ich weiß, dass es als Wiederholung/Auffrischung gelten soll, aber ist es möglich, dass man eine Aufgabe für Beweise erhält?
puuuhh hab bei ihm noch nichts geschrieben, bei Meyer brauchte man es eher nicht, allerdings kann immer mal das ein oder andere dran kommen.. schau dir am besten alles nochmal an und auch wie man im Allgemeinen Behauptungen beweist, wie zum Beispiel bei dem Übungsblatt 4 Aufgabe 2.
In der Erstklausur 2019 kam, soweit ich mich erinner, kein Beweis dran. Allerdings in der Nachklausur WS 2017 (selbe Prof/Übungsleiter-Kombination, also auch eine Klausur von Hahn.) Ich würde es lernen, allerdings erstmal Priorität auf die anderen Aufgaben legen.
Wenn man die Adjazenzlistendarstellung macht, wie gehe ich mit dem letzten Element um und seinen Zeiger? also mache ich das dann so: [a| ]-> oder [a| ]->NULL ?
Hey Swifties :) Aufgabe 4a) Seid ihr sicher, dass das wirklich 1. Fall vom Master-Theorem ist? (log_2 n)² wächst doch viel schneller als Wurzel n. Wäre es dann nicht eher 3. Fall Master-Theorem und die Laufzeit somit (log_2 n)² ?
neeeneee das stimmt schon, habs jetzt nachgerechnet, ohne die Lösung vorher zu sehen. du hast mit deiner Aussage recht, aber deine Schlussfolgerung ist falsch. O(n^(0,5-e)) bedeutet ja, dass (logn)^2 höchstens so schnell wächst wie n^(o,5-e) und das ist ja richtig. Um auf nummer sicher zu gehen, lass immer alles übern limes laufen. Dann weißt dus sicher.
noch ne Frage, Aufgabenblatt 3, Aufgabe 3.5 habe ich irgendwie falsch mitgeschrieben, kann mir da jemand die richtige Lösung geben? Bei mir kommt direkt am Anfang eine Endlosschleife..., also ich habe mitgeschrieben: int i = 1; int j = 1; bool exists = TRUE; while(j<=n){ if(A[i,j]==1){ if(i==j){ i = i+1; //hierdrum geht es else{ i = j;} else[ j +=1;} } for(int k = 1; k<=i-1;k++){ if(A[i,k] == 1 ....
View 2 more comments
Hab den Code ehrlich gesagt noch nicht verstanden. Hab nur die Lösung hingeschrieben, damit du abgleichen kannst, ob du richtig mitgeschrieben hast. Meld mich aber, wenn ich es rausgefunden habe.
achso alles klar :)dann danke :) hab auch nochmal nen Kollegen gefragt und meine Lösung hat er auch, die hat aber definitiv ne Schleife xD also vlt haben die Tutoren hier auch gar keine Musterlösung bekommen.
Weiß jemand warum man bei Listen einmal list.current.Wert() und einmal list.read().Wert machen kann? list.read() arbeitet doch mit current oder? und wenn ich nun einen neuen Zeiger Z1 benutzen würde, der auf ein Element x zeigt, würde ich den Wert von x dann durch list.Z1.Wert() bekommen oder nur durch Z1.wert?
hab mich da jetzt noch einmal reingelesen. soweit ich alles richtig verstehe ist das so: list. muss immer davor stehe, da wir als erstes auf die Klasse list zugreifen, ob nun .read() oder .current müsste egal sein, list.read() gibt das komplette Feld data aus und list.read().Pz wie in der Übungsaufgabe dann den Wert von der Punktzahl. list.current.PZ gibt den Wert von der Punktzahl auf, von dem Element, wo current gerade steht. .read() gibt ja immer das vom nächsten Element aus. benutze ich nun noch einen neuen Zeiger Z1 müsste ich also mit list.Z1.Pz arbeiten um die Punktzahl von dem Element, auf das Z1 zeigt auszugeben. Das einzige was ich nun noch nicht verstehe ist, warum wir hier mit . arbeiten und sonst bei Pointern/Zeigern mit ->
gibts hier Leute die im Zweittermin schreiben?
View 6 more comments
alles klar, war auch soweit mein Plan, dass die VL auf Youtube sind wusste ich nicht, aber gut zu wissen! Ich meine mitbekommen zu haben, dass bei Hahn die Klausuraufgaben weniger stures Shemaf rechnen ist, sondern mehr auf wissen basiert, als bei Meyer und co. Aber im Enddeffekt muss man eh beides können denke ich
Nee, nee, unsere Vorlesung ist natürlich nicht auf YouTube. Aber die Vorlesung wird an anderen Unis genau auch gelesen, nur heißt sie dort halt "Algorithmen und Datenstrukturen" (was übrigens im neuen Bachelor auch so sein wird).Und es gibt einen Prof, der heißt Eric Demaine. Er hat mit 14 seinen Bachelor und mit 20 Jahren seinen Doktor gemacht und seine Datenstrukturen-Vorlesung auf YouTube gestellt: https://www.youtube.com/watch?v=FNeL18KsWPc&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=7&t=0s Er erklärt echt extrem gut! Zur Hahns Klausur jetzt im SS 2019: Ich fand es war eine Mischung aus beiden. Es gab einige Aufgaben, die man nach Schema runterrechnen konnte (Union Find, Minimaler Spannbaum, Kruskal, Master-Theorem), aber auch einige, wo man ein bisschen nachdenken musste (Geschwistertausch aus Code-Fraquement ablesen und im Baum umzeichnen, Datenstruktur mit Max-Heap ersellen). Ich fand die Klausur schwieriger als die von Meyer und Schnitger, aber die meisten, die mit mir geschrieben haben und mit denen ich nach der Klausur geredet habe, fanden sie ziemlich fair.
Könnte hier vielleicht jemand schreiben was für Aufgaben in der Erstklausur drankamen? Vielleicht ein wenig erzählen, ob man Zeitdruck hatte etc. Würde bestimmt einige interessieren
- Bei jeweils 3 Logarithmen ankreuzen, welcher asymptotisch am schnellsten wächst, darunter eine Funktion mit log^log, log n! und eine Summenfunktion) - Hashing: Eine Aufgabe mit doppeltem Hashing und eine Tabelle mit linearem Hashing war vorgegeben und man sollte hinschreiben, wie viele verschiedene Einsetzungskombinationen existieren (Antwort wäre: 4) - Ein Code war vorgeben und man sollte die Ausgabe hinschreiben, bzw. beschreiben, was dieser Code macht und dies an einem vorgebenen Graph verdeutlichen (Antwort wäre: Geschwister tauschen). Postorder-Traversierung - 3 Aufgaben mit (a,b)-Bäumen. Einmal insert und zweimal remove (Das linkeste Kind vom linken Knoten und das linkeste Kind vom rechten Knoten). Bei insert war deas Blatt zu groß, man sollte das rekursive mittlere Kind in den Elternknoten packen und die restlichen Kinder aufteilen. Bei removve war einmal eine Fusion gefragt und einmal Schlüselklau/Rotation - 3 Aufgaben mit Master-Theorem: Einmal 2. Fall, einmal 3. Fall, einmal rekursiv. - Eine Datenstruktur ersttellen, mit vorgebenen findmax in konstanter und update in Logarithmischer Laufzeit. Als Lösung sollte man einen Heap, bzw. Max-Heap verwenden - Tiefe, Laufzeit von Binärbaumsuche angeben. - Eine geeignete Datenstruktur für ein vorgegebenes Problem mit vorgebenen V und E bestimmen. Laufzeit der Adjazenzliste/Adjazenzmatrtix in Abhängigkeit von k - Bei Kruskal sollte man die ersten 6 Kanten in den MST einzeichnen und dann Union-Find durchführen und in eine Tabelle mit den jeweiligen Elternknoten eintragen. Wichtig: Aufgabenstellung genau lesen. Das sollte nur für die ersten 6 (!) Kanten gemacht werden. Ich habe ausversehen den kompletten Kruskal durchgeführt und darauf auf diese Aufgabe 0 Punkte bekommen, was mich letzlich das Bestehen gekostet hat...
Wie läuft die Einsicht so ? Kann man sich noch Punkte finden? Meine wäre so gegen 18:00 Uhr deswegen frage ich
1 1.3 1.7 2 2.3 2.7 3 3.3 3.7 4 5 4 7 8 14 17 19 19 23 28 17 110 5% 10% 15% 20% 25% 30% 35% 40% 45% 50% 55% 60% 65% 70% 75% 80% 85% 90% 95% 100% 1.7 2.0 2.3 2.7 2.7 3.0 3.3 3.3 3.7 3.7 4.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0 5.0
View 2 more comments
Was würde passieren, wenn mehr als 110 nicht bestanden hätten?
In WiWi --> es wird solange runtergesetzt, so dass nicht mehr als 20 % durchfallen. Selbst wenn die Bestehensgrenze dann bei 20 oder 30 Punkten liegen würde. In Informatik --> juckt keinen, ob 80 % durchfallen.
Hallo, da mir ein Punkt gefehlt hat, wollte ich fragen, wie die Chancen stehen, dass die Bestehensgrenze runtergesetzt wird oder man bei der Klausureinsicht einen Punkt finden kann.
es lohnt sich zur klausureinsicht zu gehen. die bestehensgrenze wird normaler weise nicht mehr runter gesetzt sobal die ergebnisse online sind. also geh zur klausureinsicht, zähl alle punkte nach und erklär ihnen was du bei den aufgaben gemacht hast, könnte gut sein das du dann noch einen punkt bekommst oder mehr. ist eigentlich der schnitt bekannt?
Habe auch 49 Punkte, hoffentlich können wir einige Punkten ergattern bei der Klausureinsicht.
Wie fandet ihr die Klausur?
Hat jemand diese Gedächtnisprotokoll-Klausur von 2017 lösen können und kann seine Lösungen hier teilen?
Spricht eigentlich was dagegen, sich den Spicker mit Bleistift zu schreiben?
Finde ich nicht. Habe meinen auch mit Bleistift geschrieben.
Elon Musk schreibt sich an der Stelle Motivationssprüche hin, weil er das alles schon kann.
No area was marked for this question
Also kommen keine AVL-Bäume dran?
View 1 more comment
Genau, normale avl-Bäume können drankommen.
ok danke Leute :) dachte ich mir ;D
Kann jemand die Lösung für die Zweitklausur 2017 hochladen, die in der Vorlesung am Dienstag vorgestellt wurden?
hat jemand die Lösungen der Klausuraufgaben die heute im Repetit...Repetitio...Repeti..in der Zusatz-Veranstaltung heute besprochen wurden, mitgeschrieben oder abfotografiert?
Kann mir jemanden mit Beispielen erklären wie Zick-Zack & Zack-Zick Fallen funktionieren? Danke sehr❤️
Hat einer für ein paar Abgaben aus DS zufällig Lösungen und könnte die zum vergleichen hochladen ?
Hallo, ist jemand fertig mit dem Spickzettel? Wenn ja, könnte vllt den hochladen?
View 2 more comments
Bei mir kommt Safe C++ Pseudocode drauf😂
+1 @info_plug
No area was marked for this question
Wow, Danke für teilen. Es hilft sehr!👍🏼
Gerne :D falls du fragen hast, meld dich einfach
Du bist eine Legende
hey hat jemand zaufälligerweise die ds nachklausr von 2018???? mfg
View 15 more comments
Könntest du sie mir vielleicht auch schicken? s7116459@stud.uni-frankfurt.de Wäre super, vielen Dank schonmal :)
Wuerde mich auch sehr ueber die Altklausuren freuen :)) sparky333@pm.me
Hat jemand Lösungen zu der Klausur SS 2017? Das Format (10 Aufgaben - 1 Teil Begründungen, 2. Teil Sortieren, 3. Teil Datenstrukturen entwickeln) entspricht ja ziemlich genau dem, was der Prof zu unserer Klausur gesagt hat.
Schreibt ihr Erst- oder Zeittermin?
''Als erlaubtes Hilfsmittel für die Klausuren wird ein beidseitig handbeschriebenes DIN-A4-Blatt zugelassen''. Da muss man solch wichtige Informationen erst unmittelbar vor der Klausurenphase auf der Vorlesungshomepage bekanntgeben.
Findet ihr auch, dass es für den Aufwand zu wenig CP (5) gibt?
Ja, die Verteilung der CP im 2. Semester ist etwas willkürlich. HWR ist nicht mal halb so viel Aufwand und gibt fast doppelt so viele CPs. Das ändert sich mit dem neuen Bachelor 2019 sowieso. Dann hat DS 4 Vorlesungsstunden pro Woche und dementsprechend auch mehr CP.
Datenstrukturen-Vorlesungen von Prof. Schnitger http://www.thi.informatik.uni-frankfurt.de/lehre/ds/sose15/videos/
Hallo, Kennt ihr zufälligerweise jemanden der/die Nachhilfe in Datenstrukturen geben würde? Eventuell jemand der den Kurs selber schon mal erfolgreich absolviert hat und gerne verständlich erklärt? Danke im Voraus.
Woher sollte man die Zugangsdaten für die Videos bekommen?
Aus der ersten Vorlesung oder von deinem Tutor
Kann mir den Link zu der Veranstaltung schicken? Finde bei ss19 Datenstrukturen leider nicht
View 3 more comments
Die Autobahn wird zur Rennstecke. Zum Glück sind die Abgaben nur alle 2 Wochen. ;-)
ja ich glaub ich nutze eher den Briefkasten brauche ne Stunde zur Uni da muss ich sehr früh raus
Kate Crank , du bist eine Genie! Ich würde mich freuen, wenn du auch die andere Lösungen hochladen könntest. :)
Habe gerade gemacht) Hatte davor leider keine Zeit!