EAA Austauschseite

News

• 27.03.2008: Link hinzugefügt zu EAA-Zusammenfassung von Hilliges (.pdf)
• 12.03.2008: Links zu anderen Algorithmen-VLs eingefügt
• 04.03.2008: EAA-Themenliste aus Rote-Aufzeichnung (Steffen) → EAA-Themenliste (.odt)
• 04.03.2008: alle EAA-Protokolle in ein Dokument integriert und versch. Versionen hochgeladen (Steffen) → Zusammenfassung aller Fragen
• 03.03.2008: Habe die ersten 14 EAA-Protokolle durchgearbeitet (Steffen) → Zusammenfassung in OO
• Introduction to Algorithms 2nd Instructor's Manual gefunden!

Diskussion

• Die Zusammenfassung aller Protokollfragen ist noch nicht ganz aufgeräumt, da ich noch nicht so ganz den Überblick habe, um alles sinnvoll zu gliedern. Rotes Fragen sollten aber schon halbwegs sinnvoll strukturiert sein. Ich werde mich als nächstes mal dem EAA-Stoff widmen und einen Inhaltsüberblick verfassen, so dass man mal gucken kann, was im Cormen alles Pflicht ist neben den 2 Wahlkapiteln. (Steffen)
• Ich schaffe ca. 20 Cormen-Seiten pro Stunde im Schnitt (ohne Exercises/Problems). Geht es bei euch auch so träge voran? (Steffen) Ich habe genau die gleiche Leserate. (Florian)
• Wie siehts denn mit einem weiteren Treffen Anfang kommende Woche aus? Dann sollte ich mit dem Buch auch locker durch sein. Konnte leider doch erst am Montag effektiv anfangen. (Florian) Also ich könnte Dienstag ab ca. 11 Uhr und ab Mittwoch ab 10 Uhr. (Steffen) Mir würde Mittwoch ab 11 Uhr gut passen, da bin ich sowieso in der Uni. (Florian) Max hat morgen keine Zeit, von daher wird's leider frühestens Donnerstag was. Ich könnte ab 9 Uhr. (Steffen) Na ok, Donnerstag geht auch, aber nur bis 13 Uhr. (Florian) Okay, dann morgen um 10 Uhr in der Uni im Keller. (Steffen) Geht klar, aber bitte c.t. (Florian)

• Mal eine Frage zu dem Zettelkram: Ist die "LV-Nr." zu jedem Kurs auf den Studienbuchseiten diese 19xxx aus dem KVV?(Florian) Ja, zumindest habe ich meine Seite in der Annahme ausgefüllt (Steffen)

Inhaltliche Diskussion

• Ich bin grad beim Vergleich EAA-Cormen und mir ist aufgefallen, dass Rote die Themen Hashing und B-Bäume (nur als 2-3-Bäume?) nicht behandelt hat, sehe ich das richtig oder sind meine Unterlagen unvollständig? (Florian) Korrekt, wurde nicht behandelt. (Steffen)

Treffen

• nächstes Treffen: Mittwoch, 02.04.08, 10 Uhr c.t.

Stand

• Steffen:
  • Cormen lesen: fertig (Kapitel 5, 9, 13, 27-31, 33, 35 + Appendix ausgelassen)
  • Cormen zusammenfassen: Seite 1014
  • Karteikarten schreiben: fertig
    • Heaps, Treap
    • Amortized Analysis
    • UNION-FIND (Disjoint-set data structures)
    • Hashing
    • Graph algorithms:
      • BFS, DFS, topo sort
      • generic MST, Kruskal, Prim
      • Bellman-Ford, dag, Dijkstra
      • Floyd-Warshall
      • Maximum Flow, Ford-Fulkerson, Edmonds-Karp, Maximum bipartite matching, Push-relabel, Relabel-to-front
    • String matching: naive, Rabin-Karp, finite automaton, Knuth-Morris-Pratt
    • Sorting:
      • comparison sorts: heapsort, quicksort
      • lower bound for comparison sorts
      • linear time sorts: counting, radix, bucket
    • Selection problem (median): expected linear time, worst-case linear time
    • Master method (master theorem)
    • Dynamic programming, greedy algorithms
    • Komplexitätstheorie
      • N, NP, NPC, NPH, P-NP-Problem
      • Polynomialzeit-Reduktion
      • Algorithmen: akzeptierend, entscheidend, verifizierend
      • Satz von Cook + Beweisidee
      • Reduktionsbeispiel (3-CNF-SAT <p CLIQUE, HAM <p TSP)
  • Wiederholung/Auffrischung: laufend
  • Aufwand in h: 125

• Florian:
  • Cormen lesen: durch (mit den obengenannten Auslassungen)
  • Zusammenfassung: komplett, verinnerliche Stoff und ergänze Zusammenfassung weiter
  • Aufwand in h: 85

hilfreiche Links

• EAA-Zusammenfassung von Hilliges (.pdf)
• Algorithmentheorie 07/08 - Uni Freiburg - englisch
• Algorithmentheorie 06/07 - Uni Freiburg - deutsch
• Zusammenfassung aller Protokollfragen (.odt)
• Zusammenfassung von Rotes Protokollfragen (.odt)
• Zusammenfassung von Rotes Protokollfragen (.pdf)
• EAA-Themenliste Rote (.odt)
• EAA-Themenliste Rote (.pdf)