width:

ALGO | exam prep

anchored to [[111.00_anchor]]

WHAT TO REVISIT:

• DAG
• TOPOLOGY SORT !
• QUEUE implementieren
• BIPARTITE GRAPHEN
• MST PRISM ALGORITHM
• DIJKSTRA
• FLOYD WARSHALL
• A*
• ZHK | SZK –> Zusammenfassen von Graphen nach dem Prinzip!
• SZK –> kann man komprimieren!
• 2ZK –> 2fach zsm, wnen auch ohne Knoten $v$ weiterhin zsm hängend
• Artikulationspunkt
• abgeschlossene SZK
• HASHING
• REHASHING ???
• openadressing oder chaining als Lösung für Kollisionen!
  • space amount denoted with $\beta =\frac{n}{m}$ if its 1 then increase $m$ by two!
  • chaining –> using adjacency lists in each entry to mitigate collisions
  • injektiv at best
  • linear probing –> also einfach $k+n$, wobei $n$ offset
  • löschen
    • spezialsymbol löschen
    • shift lößung
• MASTER THEOREM –> Anwenden können! https://de.wikipedia.org/wiki/Master-Theorem
• dynamic programming
• Greedy algorithm idea –> local optima finden!
• BucketSORT
• BELLMAN FORD
• **SZK finden!**2
• search in sorted set
  • linear search -> from left to right (O n )
  • binary search -> always take middle of searched set and either search left /right to minimize space (o log n)
  • Interpolationssuche
• HEAPS –> always LOG N XD ( most important rule is heapify with: parent must be larger/smaller than its parents)
• BEN-OR ?
• Treess
  • depth Bestimmung: ${\log }_{b}n$, where b is the amount of children each node can have W
  • -> depth described as ${\log }_2(n+1)-1$
  • position in array: $2\cdot i$ links, $2\cdot i+1$ rechts –> can be extended too!
  • parent = $\lfloor \frac{i}{2}\rfloor$
• Balanced Search trees :: Laufzeit von Suchen/Entferne/Zufügen! ?
• AVL-Bäume !
• Ruckack-Problem beschreiben –> Greedy lösung vielleicht aufschreiben !
• TSP lower bound –> mind. günstigster Weg nach und aus Stadt heraus, $\forall cities$
• a,b Trees !

Go through the summary of tasks provide on moodl!

I have to take a look at those contents / tasks to solve them more or less efficiently !

I think