1. Welche Rechenregeln für Logarithmen gibt es?
2. Vereinfache die folgenden Terme:
   • $\log_2(8)$
   • $\log_3(1)$
   • $\log_2(n^4)$
   • $\log_{10}\left(\frac{1}{n^2}\right)$
   • $2^{\log_4(n)}$
   • $\log_n(n)$
   • $\log_a(b) \cdot \log_b(n)$
   • $\log_2(4n^3)$
   • $\log_2(\sqrt{n})$
   • $\log_2\left( \sum_{i=0}^n i \right)$
   • $\log_3\left(\prod_{i=1}^n 3^i \right)$
   • $\sum_{i=1}^n n \cdot i$
   • $\sum_{k=0}^n 2^{-k}$
   • $\sum_{k=1}^{\frac{n}{2}} 4^{-k}$
   • $\sum_{i=1}^n \frac{2}{i} <\underline{\qquad}$
3. Wahr oder falsch? Begründe deine Antwort.
   • $1 = \Theta(3)$
   • $2 = \Omega(1)$
   • $3 = \omega(2)$
   • $n = \omega(1)$
   • $f = \mathcal{O}(g)$ und $g = \mathcal{O}(f) \iff f = \Theta(g)$
   • $\sum_{k=0}^n 2^{-k} = \mathcal{O}(1)$
   • $\log_2(n) = \Theta(\log_8(n))$
   • $2^{\log_2(2n)} = \mathcal{O}(n^2)$
   • $f_1 = \Omega(g_1)$ und $f_2 = \Omega(g_2) \implies f_1 + f_2 = \Omega(g_1 + g_2)$
   • $f = o(g) \iff f = \mathcal{O}(g)$
   • $f(n) = g(\frac{n}{2}) \implies f = \Omega(g)$
   • $f = o(g) \implies 2^f = o(2^g)$

Welchen Wert hat k in Abhängigkeit von n nach der Ausführung des Programms?

1. k = 1
   for i=1,2,...,n
       k = k + 1

2. k = 1
   for i=1,2,...,n
       k = k + 1
   for j=1,2,...,100
       k = k + 2

3. k = 1
   for i=1,2,...,n*n
       k = k + 2

4. k = 1
   for i=n,n/2,n/4...,1
       k = k + 1

5. k = 1
   for i=1,2,...,n
       k = k + i

6. k = 1
   while i < n
       i = i + i
       k = k + 1

7. i = 0
   k = 0
   while i < n
       i = i + k
       k = k + 1

8. k = 1
   for i=sqrt(n), 2sqrt(n),...,n
      k = k + 1

Umgekehrt: Schreibe Pseudocode mit den folgenden Laufzeiten:

1. $\Theta(1)$
2. $\Theta(n)$
3. $\Theta(n^3)$
4. $\Theta(2^n)$
5. $\Theta(\sqrt{n})$
6. $\Theta(\log{n})$
7. $\Theta(\log{n^3})$
8. $\Theta(n!)$

Aufstellen:

1. def f(n):
       if n == 1
           return 1
       else
           return n + f(n-1)

2. def g(n):
       if n > 1:
           return g(n/2)

Lösen:

1. $T(1) = 0$ und $T(n) = 2 T(\frac{n}{2}) + \frac{n}{2}$ für $n > 1$
2. $T(2) = 1$ und $T(n) = T(\frac{n}{2}) + n - 1$ für $n > 2$

• Was ist ein Array?
• Wie sieht ein Array im Arbeitsspeicher aus?
• Wie lang dauert ein Zugriff (lesen oder schreiben) auf das n. Element A[n]? Wieso?
• Schreibe ein Programm in Pseudocode, das ein gegebenes Array A[1,…,n] mit den Werten 2, 4,…, 2n befüllt.
• Schreibe ein Programm in Pseudocode, das die Summe der Einträge dieses Arrays ausgibt.

• Was ist eine Liste?
• Wie sieht eine Liste im Arbeitsspeicher aus?
• Wie unterscheiden sich Arrays und Listen?
• Welche Zeiger und Funktionen hat die Listen-Implementierung aus der Vorlesung zur Verfügung?
• Wie lange dauert es, das größte Element einer aufsteigend (absteigend) sortierten Liste zu finden?
• Wie lange dauert das Einfügen der Zahl 7 in eine (un)sortierte Liste?
• Wieso ist binäre Suche auf Listen keine gute Idee?
• Schreibe ein Programm in Pseudocode, das beide Aufgaben (sortiert und unsortiert) erledigt.
• Die Datenstruktur Liste aus der Vorlesung ist eine einfach verkettete Liste, d.h. jedes Element hat nur einen Zeiger next auf seinen Nachfolger in der Liste. Erweitere die Datenstruktur, sodass auch jeder Vorgänger über einen Zeiger erreicht werden kann. Welche Veränderungen ergeben sich für die Funktionen insert und remove?

• Was ist ein Stack?
• Wie lange dauert ein Zugriff auf das oberste/unterste Element?
• Beschreibe, wie mit einer Liste ein Stack implementiert werden kann.
• Schreibe ein Programm, das einen Stack A als Eingabe erhält und den Stack B ausgibt, wobei B die Elemente aus A in umgekehrter Reihenfolge enthält.
• Erweitere die Datenstruktur Stack um die Funktion bottom(), die das unterste Element des Stacks in Laufzeit O(1) ausgibt.
• Bonusfrage: Wie werden Stacks in Programmiersprachen beim Aufruf von Funktionen verwendet?

• Was ist eine Queue?
• Befolgen Queues das Prinzip LIFO oder FIFO?
• Beschreibe die Situation im Supermarkt an der Kasse mithilfe einer Queue.
• Wie würde sich das Einkaufen verändern, wenn Supermarkt-Kassen wie Stacks funktionieren würden?
• Welche Algorithmen aus der Vorlesung verwenden Queues? Wieso?
• Schreibe ein Programm in Pseudocode, das eine Liste L erhält und den Wert jedes Listenelements in eine Queue einfügt.