Übungen SS2017 - Sommersemester PDF

Preview

Summary

Sommersemester...

Description

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, M. Maack, M. Rau, C. Schulze, N. Wechselberg

10. April 2017

Präsenzaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 1

Aufgabe 1.1 (O-Notation) Beweisen oder widerlegen Sie die folgenden Aussagen: 1. 2n ∈ O(n), 2.

1 n

∈ O(1),

3. n ∈ O(1) Aufgabe 1.2 (Vollständige Induktion) Sei n ∈ N. Beweisen Sie per Induktion: n−1

∑ (2i + 1) = n2 i=0

. Aufgabe 1.3 (Laufzeit) Geben Sie für den folgenden Algorithmus die Anzahl der Operationen an und bestimmen Sie die Laufzeit gemäß der O -Notation. Algorithmus M AT M ULT (A, B) 1 2 3 4 5 6

for for

7 8

for

9 10

od

11 12 13 14

od od return

to

do do

to to

do

CHRISTIAN-ALBRECHTS-UNIVERSITÄT ZU KIEL Institut für Informatik, Arbeitsgruppe Algorithmen und Komplexität Prof. Dr. K. Jansen, K.-M. Klein, M. Maack, M. Rau, C. Schulze, N. Wechselberg

17. April 2017

Präsenzaufgaben zur Vorlesung »Algorithmen und Datenstrukturen« Blatt 2

Präsenzaufgabe 2.1 (Sortieren) Sortieren Sie die Sequenz [7, 3, 5, 4, 1, 2, 8, 6] mittels Insertion Sort und mittels Selection Sort Algorithmus INSERTION - SORT (A)

Algorithmus SELECTION - SORT (A)

1 2 3 4 5

1 2 3

6 7

4 5

8 9

for

15

else

do

6 7

fi od od

for

for if

to

do

to

do then

8 9 10 11

16 17

do

while if A[j]...