polishing

9 files changed, 34 insertions, 24 deletions

diff --git a/datastructures/unionFind.cpp b/datastructures/unionFind.cpp
index 35843cd..68eef86 100644
--- a/datastructures/unionFind.cpp
+++ b/datastructures/unionFind.cpp
@@ -1,5 +1,5 @@
 // unions[i] >= 0 => unions[i] =  parent
-// unions[i]  < 0 => unions[i] = -height
+// unions[i]  < 0 => unions[i] = -size
 vector<int> unions;
 
 void init(int n) { //Initialisieren
@@ -11,12 +11,16 @@ int findSet(int n) { // Pfadkompression
 	return unions[n] = findSet(unions[n]);
 }
 
-void linkSets(int a, int b) { // Union by rank.
+void linkSets(int a, int b) { // Union by size.
 	if (unions[b] > unions[a]) swap(a, b);
-	if (unions[b] == unions[a]) unions[b]--;
+	unions[b] += unions[a];
 	unions[a] = b;
 }
 
 void unionSets(int a, int b) { // Diese Funktion aufrufen.
 	if (findSet(a) != findSet(b)) linkSets(findSet(a), findSet(b));
 }
+
+int size(int a) {
+	return -unions[findSet(a)];
+}
diff --git a/geometry/formulars.cpp b/geometry/formulars.cpp
index e34b3c6..22e9e32 100644
--- a/geometry/formulars.cpp
+++ b/geometry/formulars.cpp
@@ -34,7 +34,7 @@ bool isCoplanar(pt a, pt b, pt c, pt d) {
 	return abs((b - a) * (c - a) * (d - a)) < EPS;
 }
 
-// identifiziert winkel zwischen Vektoren u und v
+// charakterisiert winkel zwischen Vektoren u und v
 pt uniqueAngle(pt u, pt v) {
 	pt tmp = v * conj(u);
 	ll g = abs(gcd(real(tmp), imag(tmp)));
diff --git a/geometry/geometry.tex b/geometry/geometry.tex
index d753ed6..95c0adb 100644
--- a/geometry/geometry.tex
+++ b/geometry/geometry.tex
@@ -17,10 +17,10 @@
 
 \begin{algorithm}{Konvexehülle}
 	\begin{methods}
-		\method{convexHull}{berechnet Konvexehülle}{n\*\log(n)}
+		\method{convexHull}{berechnet konvexe Hülle}{n\*\log(n)}
 	\end{methods}
 	\begin{itemize}
-		\item Konvexehülle gegen den Uhrzeigersinn sortiert
+		\item Konvexe Hülle gegen den Uhrzeigersinn sortiert
 		\item nur Eckpunkte enthalten(für alle Punkte = im CCW Test entfernen)
 		\item erster und letzter Punkt sind identisch
 	\end{itemize}
diff --git a/geometry/linesAndSegments.cpp b/geometry/linesAndSegments.cpp
index c86b331..98fe4dc 100644
--- a/geometry/linesAndSegments.cpp
+++ b/geometry/linesAndSegments.cpp
@@ -31,12 +31,12 @@ vector<pt> lineSegmentIntersection(pt p0, pt p1, pt p2, pt p3) {
 	return result;
 }
 
-// Entfernung von Punkt p zur Gearden durch a-b. 2d und 3d
+// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d
 double distToLine(pt a, pt b, pt p) {
 	return abs(cross(p - a, b - a)) / abs(b - a);
 }
 
-// Projektiert p auf die Gerade a-b
+// Projiziert p auf die Gerade a-b
 pt projectToLine(pt a, pt b, pt p) {
 	return a + (b - a) * dot(p - a, b - a) / norm(b - a);
 }
diff --git a/graph/graph.tex b/graph/graph.tex
index 060d157..0f516ac 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -88,7 +88,7 @@
 Sei $d_{i\smash{j}}$ die Distanzmatrix von $G$, dann gibt $d_{i\smash{j}}^k$ die kürzeste Distanz von $i$ nach $j$ mit maximal $k$ kanten an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \min\{a_{ik} \cdot b_{k\smash{j}}\}$
 
 
-Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} + b_{k\smash{j}}$
+Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, dann gibt $a_{i\smash{j}}^k$ die Anzahl der Wege von $i$ nach $j$ mit Länge genau \textcolor{gray}{(maximal)} $k$ an mit der Verknüpfung: $c_{i\smash{j}} = a_{i\smash{j}} \otimes b_{i\smash{j}} = \sum a_{ik} \cdot b_{k\smash{j}}$
 
 \begin{algorithm}{Dynamic Connectivity}
 	\begin{methods}
@@ -175,7 +175,7 @@ Sei $a_{ij}$ die Adjazenzmatrix von $G$ \textcolor{gray}{(mit $a_{ii} = 1$)}, da
 		\method{kuhn}{berechnet Matching}{\abs{V}\*\min(ans^2, \abs{E})}
 	\end{methods}
 	\begin{itemize}
-		\item die ersten [0..n) Knoten in \code{adj} sind die linke Seite des Graphen
+		\item die ersten [0..l) Knoten in \code{adj} sind die linke Seite des Graphen
 	\end{itemize}
 	\sourcecode{graph/maxCarBiMatch.cpp}
 	\begin{methods}
diff --git a/math/math.tex b/math/math.tex
index f9a5ea5..dc0eb00 100644
--- a/math/math.tex
+++ b/math/math.tex
@@ -172,7 +172,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 	\textbf{Wichtig:} Sieb rechts ist schneller für \code{isPrime} oder \code{primes}!

 	

 	\sourcecode{math/linearSieve.cpp}

-	\textbf{\textsc{Möbius} Funtkion:}

+	\textbf{\textsc{Möbius}-Funtkion:}

 	\begin{itemize}

 		\item $\mu(n)=+1$, falls $n$ quadratfrei ist und gerade viele Primteiler hat

 		\item $\mu(n)=-1$, falls $n$ quadratfrei ist und ungerade viele Primteiler hat

@@ -313,16 +313,16 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 \sourcecode{math/piLehmer.cpp}

 }

 

-\begin{algorithm}{Lineare-Recurenz}

+\begin{algorithm}{Lineare Rekurrenz}

 	\begin{methods}

-		\method{BerlekampMassey}{Berechnet eine lineare Recurenz $n$-ter Ordnung}{n^2}

+		\method{BerlekampMassey}{Berechnet eine lineare Rekurrenz $n$-ter Ordnung}{n^2}

 		\method{}{aus den ersten $2n$ Werte}{}

 	\end{methods}

 	\sourcecode{math/berlekampMassey.cpp}

-	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Recurenz.

+	Sei $f(n)=c_{n-1}f(n-1)+c_{n-2}f(n-2)+\dots + c_0f(0)$ eine lineare Rekurrenz.

 	

 	\begin{methods}

-		\method{kthTerm}{Berechnet $k$-ten Term einer Recurenz $n$-ter Ordnung}{\log(k)\cdot n^2}

+		\method{kthTerm}{Berechnet $k$-ten Term einer Rekurrenz $n$-ter Ordnung}{\log(k)\cdot n^2}

 	\end{methods}

 	\sourcecode{math/linearRecurence.cpp}

 	Alternativ kann der \mbox{$k$-te} Term in \runtime{n^3\log(k)} berechnet werden:

@@ -332,7 +332,7 @@ sich alle Lösungen von $x^2-ny^2=c$ berechnen durch:
 		c_{n-1} & c_{n-2} & \smash{\cdots} & \smash{\cdots} & c_0 \\

 		1 & 0 & \smash{\cdots} & \smash{\cdots} & 0 \\

 		0 & \smash{\ddots} & \smash{\ddots} & & \smash{\vdots} \\

-		0 & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\

+		\smash{\vdots} & \smash{\ddots} & \smash{\ddots} & \smash{\ddots} & \smash{\vdots} \\

 		0 & \smash{\cdots} & 0 & 1 & 0 \\

 	\end{pmatrix}^k

 	\times~~

diff --git a/other/other.tex b/other/other.tex
index 808d288..a21eb37 100644
--- a/other/other.tex
+++ b/other/other.tex
@@ -9,7 +9,7 @@
 \end{algorithm}

 

 \begin{algorithm}{Timed}

-	Kann benutzt werdem un randomisierte Algorithmen so lange wie möglich laufen zu lassen.

+	Kann benutzt werden um randomisierte Algorithmen so lange wie möglich laufen zu lassen.

 	\sourcecode{other/timed.cpp}

 \end{algorithm}

 

@@ -23,7 +23,7 @@
 		Bit an Position j flippen & \code{x ^= (1 << j)} \\

 		Anzahl an führenden nullen	($x \neq 0$) & \code{__builtin_clzll(x)} \\

 		Anzahl an schließenden nullen ($x \neq 0$) & \code{__builtin_ctzll(x)} \\

-		Anzahl an bits & \code{__builtin_popcountll(x)} \\

+		Anzahl an \code{1} bits & \code{__builtin_popcountll(x)} \\

 		$i$-te Zahl eines Graycodes & \code{i ^ (i >> 1)} \\

 		\hline

 	\end{tabularx}\\

@@ -259,7 +259,7 @@
 \subsection{Tipps \& Tricks}

 

 \begin{itemize}

-	\item Run Time Error:

+	\item \textbf{Run Time Error:}

 	\begin{itemize}

 		\item Stack Overflow? Evtl. rekursive Tiefensuche auf langem Pfad?

 		\item Array-Grenzen überprüfen. Indizierung bei $0$ oder bei $1$ beginnen?

@@ -267,13 +267,19 @@
 		\item Evtl. Memory Limit Exceeded? Mit \code{/usr/bin/time -v} erhält man den maximalen Speicherverbrauch bei der Ausführung (Maximum resident set size).

 	\end{itemize}

 	

-	\item Strings:

+	\item \textbf{Strings:}

 	\begin{itemize}

 		\item Soll \codeSafe{"aa"} kleiner als \codeSafe{"z"} sein oder nicht?

 		\item bit \code{0x20} beeinflusst Groß-/Kleinschreibung.

 	\end{itemize}

+

+	\item \textbf{Zeilenbasierte Eingabe}:

+	\begin{itemize}

+		\item \code{getline(cin, str)} liest Zeile ein.

+		\item Wenn vorher \code{cin >> ...} benutzt, lese letztes \code{\\n} mit \code{getline(cin, x)}.

+	\end{itemize}

 	

-	\item Gleitkommazahlen:

+	\item \textbf{Gleitkommazahlen:}

 	\begin{itemize}

 		\item \code{NaN}? Evtl. ungültige Werte für mathematische Funktionen, z.B. \mbox{\code{acos(1.00000000000001)}}?

 		\item Falsches Runden bei negativen Zahlen? Abschneiden $\neq$ Abrunden!

@@ -281,7 +287,7 @@
 		\item Kann \code{-0.000} ausgegeben werden?

 	\end{itemize}

 

-	\item Wrong Answer:

+	\item \textbf{Wrong Answer:}

 	\begin{itemize}

 		\item Lies Aufgabe erneut. Sorgfältig!

 		\item Mehrere Testfälle in einer Datei? Probiere gleichen Testcase mehrfach hintereinander.

diff --git a/string/string.tex b/string/string.tex
index 393c2ad..dbea36c 100644
--- a/string/string.tex
+++ b/string/string.tex
@@ -35,7 +35,7 @@
 \begin{algorithm}{\textsc{Manacher}'s Algorithm, Longest Palindrome}
 	\begin{methods}
 		\method{init}{transformiert \code{string a}}{n}
-		\method{manacher}{berechnet Länge der Palindrome}{n}
+		\method{manacher}{berechnet Längen der Palindrome in longest}{n}
 	\end{methods}
 	\sourcecode{string/manacher.cpp}
 \end{algorithm}
@@ -90,7 +90,7 @@
 \begin{algorithm}{Suffix-Array}
 \begin{methods}
 	\method{SuffixArray}{berechnet ein Suffix Array}{\abs{s}\*\log^2(\abs{s})}
-	\method{lcp}{berechnet den longest common prefix}{\log(\abs{s})}
+	\method{lcp}{berechnet Länge des longest common prefix}{\log(\abs{s})}
 	\method{}{von \code{s[x]} und \code{s[y]}}{}
 \end{methods}
 \sourcecode{string/suffixArray.cpp}
diff --git a/tcr.pdf b/tcr.pdf
index 63ebc4a..7114518 100644
--- a/tcr.pdf
+++ b/tcr.pdf