Wissensfragen_Aufgaben.tex

\documentclass{scrartcl}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{enumerate}

\begin{document}
\section*{Wissensfragen: Aufgaben}
\begin{enumerate}[(1)]

\item Nennen Sie zwei in der Vorlesung vorgestellte Algorithmen, die nach dem Greedy-Prinzip arbeiten. Begründen Sie kurz, warum.

\item Nennen Sie einen Vorteil und einen Nachteil von Mergesort gegenüber Quicksort.

\item Was bedeutet Stabilität bei Sortieralgorithmen? Nennen Sie eine Situation, in der man die Stabilität ausnutzen kann.

\item Was muss für eine Hashtabelle mit Verkettung gelten, damit der Aufwand für die Suche nach einem Element O(1) beträgt?

\item \begin{enumerate}[(a)]
\item Was bedeutet der Begriff \glqq amortisierte Analyse\grqq?
\item Nennen Sie ein Beispiel für eine Operation, die in der amortisierten Analyse eine bessere Laufzeit hat als im Worst Case. Geben Sie zusätzlich die beiden Laufzeiten an. Eine Begründung ist nicht notwendig.
\item Nennen Sie eine Gemeinsamkeit und einen Unterschied zwischen amortisierter Analyse und Average-Case-Laufzeit.
\end{enumerate}
\end{enumerate}
\end{document}