P5 RemoveTest

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Antragon hat geschrieben:Ich bin mittlerweile zur Überzeugung gekommen, dass meine "Lösung" richtig ist, aber der Testcase nicht damit rechnet...
Die Testcases erwarten, dass Sie genauso loeschen, wie es in den Folien spezifiziert ist. Sollte es mehrere Moeglichkeiten geben, sind beide Moeglichkeiten gueltig. In den Testcases werden alle moeglichen Faelle abgefragt.

Und mittlerweile stehen hier in diesem Thread schon SO viele Hinweise, dass man es eigentlich schaffen sollte, das Loeschen entsprechend zu implementieren.

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

wach hat geschrieben: Sollte es mehrere Moeglichkeiten geben, sind beide Moeglichkeiten gueltig. In den Testcases werden alle moeglichen Faelle abgefragt.
[glow=red]FALSCH!!!![/glow]

Ich habe gerade eben das ergebnis meiner "Modifikation" bekommen: PASSED

==> Das Testsystem hatte also offensichtlich nicht akzeptiert "wie" ich gelöscht hatte, obwohl meine Lösung definitiv gültig war!

Ein Beispiel:

Erzeuge den Baum: (in der Reihenfolge einfügen)
10 5 1 3 7 6 9 12 15 13 18

Lösche die 12...

Was meine Löschoperation erzeugte: (Preorder)
[10, 5, 1, 3, 4, 7, 6, 9, 13, 15, 18]

Das Testsystem erwartet:
[10, 5, 1, 3, 4, 7, 6, 9, 15, 13, 18]


Der Unterschied:

Mein Algorithmus suchte zum ersetzten der 12 den kleinsten Knoten des rechten Baumes -> "13"

Was das Testsystem erwartete:
Die 12 wird ersetzt indem die nachfolgende 15 einfach an die stelle von der 12 gesetzt wird, also "nach oben verschoben" wird.



Ich muss sagen: Ich fühle mich wirklich verarscht! Ich hatte den Code für das Programm letzten Donnerstag in 2 Stunden runtergeschrieben und mich wegen diesesem sch**** Fehler des Testsystems nun noch rund 15 Stunden aufhalten lassen wo ich die Zeit bei Leibe hätte besser verwenden können! :twisted:
Zuletzt geändert von Antragon am 28. Mai 2007 11:22, insgesamt 1-mal geändert.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

Du hast das mit dem löschen noch nich ganz verstanden anscheinend, das TestSystem hat da keine schuld ^^
Denn das is doch das System wie man löscht...
Man sucht erst den kleinsten rechten / größten linken Nachfolger / Knoten wenn BEIDE Unterbäume existieren, in deinem Beispiel existiert nur einer...un da wird dann einfach dieser Baum "hochgeschoben"

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Christoph B hat geschrieben:Du hast das mit dem löschen noch nich ganz verstanden anscheinend, das TestSystem hat da keine schuld ^^
Denn das is doch das System wie man löscht...
Man sucht erst andere Nachfolger wenn BEIDE Unterbäume existieren, in deinem Beispiel existiert nur einer...un da wird dann einfach dieser Baum "hochgeschoben"
Das mag dann vielleicht die Darmstädter Variante sein... aber die Aufgabenstellung lautete einen Binären Suchbaum zu implementieren... und da ist es auch eine absolut übliche Variante so wie ich es tat zu ersetzen!

...v.a.: Das Testsystem lies mich im Glaube dass mein Code an sich falsch wäre... und hätte mich nicht ein anderer auf diese Möglichkeit aufmerksam gemacht wäre ich nie im Leben darauf gekommen dass es an so einer Kleinigkeit lag... Die Fehlerausgabe des Testsystems ist für sowas ja viel zu ungenau...

Wäre es denn "fair" das Praktikum mit 0 Punkten bewertet zu bekommen nur weil man so einen "Fehler" hat?

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

Wieso denkst du lernen wir in der Vorlesung wie man mit Binären Bäumen umgeht, löscht etc? Damit man im entsprechenden Praktikum alles anders macht?
Könnts einfach nur sein das du dir nichtmal die entsprechenden Folien reingefahren hast vor dem Programmieren?
Folie 9, seite 9-10 steht GANZ GENAU wie man aus nem BinärBaum löscht.

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Das macht seine Methode aber nicht falsch, höchstens unkonventionell. Er hat den Knoten aus dem Baum gelöscht und den restlichen Baum in einem korrekten Aufbau erhalten. Das Verhalten ist auch nicht asymptotisch schlechter, weil er ja nichts anderes macht als man bei Fall 3 sowieso tun muss, lediglich dass er es halt auch da gemacht hat, wo es eine einfachere Variante gegeben hätte. Aber das macht es immer noch nicht falsch ;) Es stand nicht in der Aufgabenstellung "Implementieren Sie das Löschen streng nach Folienvorlage".

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

Danke Holger... ^^

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

"Implementieren Sie den Suchbaum so wie auf Folien spezifiziert. Führen Sie explizit die Löschoperationen auf Folien 9/9-10 durch."
http://www.di.informatik.tu-darmstadt.d ... php?id=585

Und das steht da jetzt schon laenger ...

Wer lesen kann ...

Benutzeravatar
Antragon
Mausschubser
Mausschubser
Beiträge: 78
Registriert: 26. Okt 2005 13:09
Kontaktdaten:

Beitrag von Antragon »

wach hat geschrieben:"Implementieren Sie den Suchbaum so wie auf Folien spezifiziert. Führen Sie explizit die Löschoperationen auf Folien 9/9-10 durch."
http://www.di.informatik.tu-darmstadt.d ... php?id=585

Und das steht da jetzt schon laenger ...

Wer lesen kann ...
An dem Tag an dem ich es implementiert hatte stand es noch NICHT da!

Und nochmal die Frage: Ist es fair wegen so einer sache mit 0 Punkten zu bewerten? - Schließlich wäre meine lösung auch 100% in Übereinstimmung mit der AUFGABENSTELLUNG (pdf/code)

benrub
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 3. Dez 2006 01:26

Beitrag von benrub »

Thema folien - An dieser Stelle die Bitte, hauptsächlich im Namen meiner nicht-so-gut deutsch sprechenden Komilitonen, den 9. Foliensatz für ICS online zu stellen, da ohne diesen Satz die Praktikumsaufgabe kaum zu bewerkstelligen ist.

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Beitrag von mantra »

Antragon hat geschrieben: An dem Tag an dem ich es implementiert hatte stand es noch NICHT da!
So langsam solltet ihr rausgefunden haben, dass sich die Aufgabenstellung durch unscheinbare Anmerkungen auf der Website noch ein paar mal ändert.
Und nochmal die Frage: Ist es fair wegen so einer sache mit 0 Punkten zu bewerten? - Schließlich wäre meine lösung auch 100% in Übereinstimmung mit der AUFGABENSTELLUNG (pdf/code)
Meiner Meinung nach: nein.

debach
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 18. Mai 2007 15:59
Kontaktdaten:

Beitrag von debach »

wach hat geschrieben:Und das steht da jetzt schon laenger ...

Wer lesen kann ...
Spässchen gemacht? Immerhin ist nicht im Nachteil, wer Aufgabenstellungen nicht klar formulieren kann.
Diese fehlenden Informationen und Einschränkungen zu Beginn der Praktikumsaufgaben können ziemlich viel Zeit und Punkte kosten, unabhängig davon, ob sie im Nachhinein noch geändert werden. Schließlich wartet man nicht bis Donnerstag 16:00, um mit der Lösung anzufangen, in der Hoffnung, dass sich nichts mehr an der Aufgabenstellung ändert.

wach
Computerversteher
Computerversteher
Beiträge: 323
Registriert: 25. Okt 2004 09:08

Beitrag von wach »

Antragon hat geschrieben:Ist es fair wegen so einer sache mit 0 Punkten zu bewerten? - Schließlich wäre meine lösung auch 100% in Übereinstimmung mit der AUFGABENSTELLUNG (pdf/code)
Es gilt immer in Uebungsaufgaben, Praktika und Klausuraufgaben: Mache alles so wie in der Vorlesung. Wieso sollten wir auch willkuerliche Implementierungen zulassen?

Es gibt prinzipiell verschiedene Moeglichkeiten manche Dinge zu implementieren. Aber schon nur die Beschraenkung auf die Varianten in der Vorlesung lassen gewisse Freiheitsgrade zu, die alle bei Tests oder Korrekturen von Aufgaben mit ueberprueft werden muessen.

Wenn Sie Probleme haben und Tests nicht bestehen, koennten Sie einerseits die Homepage mit aktuellen Informationen zur Aufgabe lesen, oder auf die wirklich guten Ratschlaege Ihrer Kommilitonen hier im Thread. Wenn Sie das schon nicht tun, beschweren Sie sich dann auch bitte nicht ...

Wenn weiterer Diskussionsbedarf steht, kommen Sie in meine Sprechstunde.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

HolgerF hat geschrieben:Das Verhalten ist auch nicht asymptotisch schlechter, weil er ja nichts anderes macht als man bei Fall 3 sowieso tun muss, lediglich dass er es halt auch da gemacht hat, wo es eine einfachere Variante gegeben hätte.
Na klar is das asymptotisch schlechter, er sucht ja in jedem fall sofern nen unterbaum existiert nach einem nachfolger, un zwar wirklich den GANZEN restbaum, bis zu einem blatt nehm ich an (oder schiebste da nen Teilbaum hoch wenn du irgendwann net mehr weiterkommst un nur noch einen Teilbaum hast? ^^)
Angenommen wir sollten nen Knoten löschen der Links keinen Teilbaum hat, rechts aber nen Baum der ne Höhe 1000000000000000000 * e^x + Pi oda sonstwas hat
Was geht wohl schneller? diese ganzen Stufen durchgehn bis man nen ersatz hat? oder einfach mal eben so den einen Verweis ändern?

HolgerF
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 263
Registriert: 16. Jan 2007 14:20
Kontaktdaten:

Beitrag von HolgerF »

Das Löschen eines Knotens liegt bereits sowieso asymptotisch in O(h) (h die Höhe des Baums), weil du den zu löschenden Knoten suchen musst. Ob du, wenn du ihn gefunden hast, von da aus noch einen zweiten Knoten suchst, spielt also für die asymptotische Laufzeit überhaupt keine Rolle. Dein Beispiel münzt auf die konkrete Laufzeit für ein bestimmtes Beispiel, nicht auf die asymptotische.

Außerdem gibt es ja auch Fälle bei remove, wo du gar nichts anderes tun kannst, also ist das in remove sowieso abgedeckt.

Antworten

Zurück zu „Archiv“