ETH_Datenstrukturen&Algorithmen_Vorlesung

links - D&A

Vorlesungsseite: https://lec.inf.ethz.ch/DA/2025/
Exercises: https://expert.ethz.ch

Info

Skript: dsaln_script_FS2025.pdf
Moodle: https://moodle-app2.let.ethz.ch/course/view.php?id=24411
Übungen
- Übungen am Montag (week $n$ ), Abgabe am nächsten Donnerstag (week $n + 1$ )
- study center Freitag Mittag
- $0.25$ Bonus bei Lösung von Bonusaufgaben; 2/3 Bonusaufgaben reichen für vollen Bonus
Prüfung
- schriftlich (hybrid auf Computer und Papier)
- 4 A4-Blätter (8 Seiten) Spick erlaubt
Cheatsheet
- fast vollständig: https://github.com/gianhiltbrunner/DatastructuresAlgorithms
- nützliche screenshots: https://gitlab.ethz.ch/agavranovic/dunda

Hilfsmittel D&A

8 A4-Seiten
- format frei

Exercises

Osterferien: 18.04-27.04

Lösung	Korrektur
20250224_D&A_Serie2.pdf
20250303_D&A_Serie3.pdf
20250319_D&A_Serie4
[20250317_D&A_Serie5]] / [20250317_D&A_Serie5.pdf
[20250325_D&A_Serie6]] / [20250326_D&A_Serie6.pdf
20250331_D&A_Serie7
20250407_D&A_Serie8
20250415_D&A_Serie9

20250506_D&A_Serie11

20250519_D&A_Serie13
20250526_D&A_Serie14

Vorlesung

#timestamp 2025-02-17

compiler optimization -> e.g. branch prediction (speculative execution)

Is $3 n^{2} + 7 n$ in $O (n^{2})$ ? -> yes, since

\begin{array}{r} 3 n^{2} + 7 n \leq 4 n^{2} \end{array}

because $7 n \leq n$ and $7 \leq n$ .

Unterschied Komplexität/

Komplexität -> Problem (minimale asymptotische Kosten über alle Algorithmen, die P lösen)
Asymptotisches Verhalten -> Algorithmus

#timestamp 2025-02-21

Pasted image 20250221092707.png

#timestamp 2025-03-24

Pasted image 20250324183446.png

#timestamp 2025-03-25

traversal possibilities
Pasted image 20250325174722.png

red-black-tree deletion
Pasted image 20250325214040.png