Solved PP
Hochgeladen von
umarg135790Solved PP
Hochgeladen von
umarg135790Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2024-25 Winter Term
Resit Exam
2024-12-10
Time Limit: 90 Minutes Mark:
English (EN): This exam contains 18 pages (including this cover page) and 3 problems. Answer
2 problems. If you answer 3 problems, the best 2 count. Check to see if any pages are missing.
Enter all requested information on the top of this page, and put your seat number on the top of
every page, in case the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
must indicate this and explain why the theorem Problem Points Score
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not
receive full credit. A correct answer, unsup- Total: 50
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
• Write all your source code in Python.
Do not write in the table to the right.
Deutsch (DE): Diese Klausur umfasst 18 Seiten (einschließlich dieses Deckblatts) und 3 Aufgaben
(Problems). Beantworten Sie 2 Aufgaben. Wenn Sie 3 Aufgaben beantworten, zählen die besten 2.
Überprüfen Sie, ob Seiten fehlen. Geben Sie alle geforderten Informationen oben auf dieser Seite
an, und notieren Sie Ihre Platznummer oben auf jeder Seite ein, falls die Seiten getrennt werden.
Algorithms and Data Structures Resit Exam - Page 2 of 18 2024-12-10
In dieser Klausur dürfen Sie nur einen Taschenrechner (kein Computeralgebrasystem) und ein ein-
seitiges handgeschriebenes A4-Notizblatt verwenden.
Es gelten die folgenden Regeln:
• Wenn Sie ein “Grundlagentheorem” verwenden, müssen Sie dies angeben und
erklären warum das Theorem angewendet werden kann.
• Organisieren Sie Ihre Arbeit in einer einigermaßen ordentlichen und kohärenten Weise
in dem vorgesehenen Platz. Arbeiten, die über die ganze Seite verstreut sind und keine klare
Ordnung aufweisen, werden sehr wenige Punkte erhalten.
• Mysteriöse oder nicht belegte Antworten werden nicht die volle Punktzahl er-
halten. Eine richtige Antwort, die nicht durch Berechnungen, Erklärungen oder algebrais-
che Arbeit untermauert ist, wird keine Punkte erhalten; eine falsche Antwort, die durch im
Wesentlichen korrekte Berechnungen und Erklärungen untermauert wird, kann noch Teilpunkte
erhalten.
• Wenn Sie mehr Platz benötigen, verwenden Sie die Rückseite der Seiten; geben Sie deutlich
an, wann Sie dies getan haben.
• Schreiben Sie Ihren gesamten Quellcode in Python.
Schreiben Sie nicht in die Tabelle auf der rechten Seite.
Algorithms and Data Structures Resit Exam - Page 3 of 18 2024-12-10
1. (25 points) EN: Recursion and dynamic programming /
DE: Rekursion und dynamische Programmierung
(a) (4 points) EN: We define Deggendorf numbers as following:
DE: Wir definieren Deggendorf-Zahlen wie folgt:
1 n ∈ {0, 1, 2}
deg(n) = .
deg(n − 1) + deg(n − 2) + deg(n − 3) n≥3
EN: Provide a naive implementation.
DE: Liefern Sie eine naive Implementierung.
Algorithms and Data Structures Resit Exam - Page 4 of 18 2024-12-10
(b) (5 points) EN: Derive the worst-case running time complexity of your naive implementa-
tion.
DE: Leiten Sie die ungünstigste (worst-case) Laufzeitkomplexität Ihrer Implementierung
her.
Algorithms and Data Structures Resit Exam - Page 5 of 18 2024-12-10
(c) (4 points) EN: Visualize the complete recursion tree for deg(4).
DE: Visualisieren Sie den vollständigen Rekursionsbaum für deg(4).
(d) (8 points) EN: Re-implement your algorithm using a top-down dynamic programming
approach without using any auxiliary tools provided by Python.
DE: Reimplementieren Sie Ihren Algorithmus mit einem Top-Down-Ansatz der dynamis-
chen Programmierung, ohne die von Python bereitgestellten Hilfsmittel zu verwenden.
Algorithms and Data Structures Resit Exam - Page 6 of 18 2024-12-10
(e) (4 points) EN: How does Python support you in memoizing function calls? Provide a
brief explanation and re-implement your algorithm using a top-down dynamic program-
ming approach using that auxiliary tool.
DE: Wie unterstützt Sie Python bei der Memoisierung von Funktionsaufrufen? Liefern
Sie eine kurze Erklärung und reimplementieren Sie Ihren Algorithmus mit einem Top-
Down-Ansatz der dynamischen Programmierung unter Verwendung dieses Hilfsmittels.
How Python Supports Memoization
Python offers built-in support for memoization through the functools.lru_cache decorator.
It automatically caches function calls and results based on the input arguments. If the function
is called again with the same arguments, the result is fetched from the cache instead of
recomputing it — significantly improving performance for recursive functions.
Algorithms and Data Structures Resit Exam - Page 7 of 18 2024-12-10
2. (25 points) EN: Quantum computing, fast matrix multiplication and recurrence re-
lations /
DE: Quantencomputing, schnelle Matrizenmultiplikation und Rekurrenzgleichun-
gen
(a) (4 points) EN: The vector representation of a single qubit is:
DE: Die Vektorrepräsentation eines einzelnen Qubit lautet wie folgt:
α
|a⟩ = α|0⟩ + β|1⟩ = .
β
EN: Explain what α and β are and what makes a qubit different to a bit. Also provide
the respective constraints for α and β such that |a⟩ is a valid qubit.
DE: Erklären Sie, was α und β sind und was ein Qubit gegenüber einem Bit unterscheidet.
Liefern Sie auch die respektiven Bedingungen für α und β, sodass |a⟩ ein gültiges Qubit
ist.
Algorithms and Data Structures Resit Exam - Page 8 of 18 2024-12-10
(b) (3 points) EN: What is Grover’s algorithm? Provide a brief explanation of the algorithm
and discuss its speedup compared to a traditional algorithm. Use the O notation in your
explanation.
DE: Was ist der Grover-Algorithmus? Liefern Sie eine kurze Erklärung des Algorith-
mus und diskutieren Sie seine Beschleunigung gegenüber einem traditionellen Algorithmus.
Nutzen Sie die O-Notation in Ihrer Erklärung.
(c) (3 points) EN: Provide the worst-case running time complexity of naive matrix multipli-
cation. Also, provide a brief justification.
DE: Liefern Sie die ungünstigste (worst-case) Laufzeitkomplexität der naiven Matrizen-
multiplikation. Liefern Sie auch eine kurze Begründung dafür.
Algorithms and Data Structures Resit Exam - Page 9 of 18 2024-12-10
(d) (4 points) EN: Let A, B be two square matrices over R. We want to calculate the matrix
product C as:
DE: A, B sind zwei quadratische Matrizen mit Werten aus den reellen Zahlen. Wir
möchten das Matrizenprodukt C wie folgt berechnen:
n ×2n
C = AB A, B, C ∈ R2 .
EN: If the matrices A, B are not of type 2n × 2n we fill the missing rows and columns
with zeros. We partition A, B and C into equally sized block matrices:
DE: Wenn die Matrizen A, B nicht vom Typ 2n × 2n sind, füllen wir die fehlenden
Zeilen und Spalten mit Nullen aus. Wir partitionieren A, B und C in gleich große Block-
matrizen:
A1,1 A1,2 B1,1 B1,2 C1,1 C1,2
A= ,B= ,C= .
A2,1 A2,2 B2,1 B2,2 C2,1 C2,2
EN: Define how to calculate C1,1 , C1,2 , C2,1 and C2,2 .
DE: Definieren Sie, wie C1,1 , C1,2 , C2,1 und C2,2 berechnet werden.
Algorithms and Data Structures Resit Exam - Page 10 of 18 2024-12-10
(e) (4 points) EN: The following 7 auxiliary matrices can be defined:
DE: Die folgenden 7 Hilfsmatrizen können wie folgt definiert werden:
M1 := (A1,1 + A2,2 )(B1,1 + B2,2 ),
M2 := (A2,1 + A2,2 )B1,1 ,
M3 := A1,1 (B1,2 − B2,2 ),
M4 := A2,2 (B2,1 − B1,1 ),
M5 := (A1,1 + A1,2 )B2,2 ,
M6 := (A2,1 − A1,1 )(B1,1 + B1,2 ),
M7 := (A1,2 − A2,2 )(B2,1 + B2,2 ).
EN: Now the Strassen algorithm re-expresses Ci,j 1 :
DE: Nun berechnet der Strassen-Algorithmus Ci,j wie folgt2 :
C1,1 = M1 + M4 − M5 + M7 ,
C1,2 = M3 + M5 ,
C2,1 = M2 + M4 ,
C2,2 = M1 − M2 + M3 + M6 .
EN: Show that C2,1 is calculated correctly.
DE: Zeigen Sie, dass C2,1 korrekt berechnet wird.
1
EN: We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements
of R). The resulting product will be padded with zeroes just like A and B, and should be stripped of the corresponding
rows and columns.
2
DE: Wir wiederholen diesen Divisionsprozess n mal (rekursiv), bis die Submatrizen in Zahlen (Elemente von R)
übergehen. Das resultierende Produkt wird genau wie A und B mit Nullen aufgefüllt und sollte die entsprechenden
Zeilen und Spalten nicht mehr enthalten.
Algorithms and Data Structures Resit Exam - Page 11 of 18 2024-12-10
EN: Continued: / DE: fortgesetzt:
(f) (2 points) EN: Provide the recurrence relation for the Strassen algorithm.
DE: Liefern Sie die Rekurrenzgleichung für den Strassen-Algorithmus.
(g) (5 points) EN: Using the recurrence relation, derive the worst-case running time com-
plexity of the Strassen algorithm.
DE: Nutzen Sie die Rekurrenzgleichung um die ungünstigste (worst-case) Laufzeitkom-
plexität des Strassen-Algorithmus herzuleiten.
Algorithms and Data Structures Resit Exam - Page 12 of 18 2024-12-10
EN: Continued: / DE: fortgesetzt:
Algorithms and Data Structures Resit Exam - Page 13 of 18 2024-12-10
3. (25 points) EN: Trees /
DE: Bäume
(a) (3 points) EN: Mark the trees that are symmetric in the following figure. Trees are sym-
metric if they are equal to their inverse.
DE: Markieren Sie die symmetrischen Bäume in der folgenden Abbildung. Bäume sind
symmetrisch, wenn sie gleich ihrer Invertierung sind.
Tree : 1, 2, 5, 6, and 9 are symmetric
(b) (7 points) EN: Implement a function is symmetric that returns True or False, whether
a tree is symmetric. Note that a node may have 0, 1 or 2 children. Use the TreeNode class
below. It only allows to build a tree structure and ignores node values.
DE: Implementieren Sie eine Funktion is symmetric, die True oder False zurückgibt,
ob ein Baum symmetrisch ist. Beachten Sie, dass ein Knoten 0, 1 oder 2 Kinder haben
kann. Verwenden Sie die Klasse TreeNode unten. Diese erlaubt nur, Baumstrukturen zu
bauen und ignoriert Knotenwerte.
class TreeNode :
def init (self ):
[Link] = None
[Link] = None
def is symmetric (node ):
[...]
Algorithms and Data Structures Resit Exam - Page 14 of 18 2024-12-10
EN: Continued: / DE: fortgesetzt:
Algorithms and Data Structures Resit Exam - Page 15 of 18 2024-12-10
(c) (15 points) EN: Use the ID3 decision tree learning algorithm in order to learn a tree for
the attack label using the following data set. Write out intermediate steps and the result.
DE: Nutzen Sie den ID3-Entscheidungsbaumlernalgorithmus um einen Baum für das La-
bel attack mit dem folgenden Datensatz zu lernen. Schreiben Sie Zwischenschritte und
das Ergebnis aus.
sky air humid wind water forecast attack
1 cloudy warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Algorithms and Data Structures Resit Exam - Page 16 of 18 2024-12-10
EN: Continued: / DE: fortgesetzt:
sky air humid wind water forecast attack
1 cloudy warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Algorithms and Data Structures Resit Exam - Page 17 of 18 2024-12-10
EN: Continued: / DE: fortgesetzt:
sky air humid wind water forecast attack
1 cloudy warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Algorithms and Data Structures Resit Exam - Page 18 of 18 2024-12-10
EN: Continued: / DE: fortgesetzt:
sky air humid wind water forecast attack
1 cloudy warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2024 Summer Term
Exam
2024-07-12
Time Limit: 90 Minutes Mark:
English (EN): This exam contains 17 pages (including this cover page) and 3 problems. Answer
2 problems. If you answer 3 problems, the best 2 count. Check to see if any pages are missing.
Enter all requested information on the top of this page, and put your seat number on the top of
every page, in case the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
must indicate this and explain why the theorem Problem Points Score
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not
receive full credit. A correct answer, unsup- Total: 50
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
• Write all your source code in Python.
Do not write in the table to the right.
Deutsch (DE): Diese Klausur umfasst 17 Seiten (einschließlich dieses Deckblatts) und 3 Aufgaben
(Problems). Beantworten Sie 2 Aufgaben. Wenn Sie 3 Aufgaben beantworten, zählen die besten 2.
Überprüfen Sie, ob Seiten fehlen. Geben Sie alle geforderten Informationen oben auf dieser Seite
an, und notieren Sie Ihre Platznummer oben auf jeder Seite ein, falls die Seiten getrennt werden.
Algorithms and Data Structures Exam - Page 2 of 17 2024-07-12
In dieser Klausur dürfen Sie nur einen Taschenrechner (kein Computeralgebrasystem) und ein ein-
seitiges handgeschriebenes A4-Notizblatt verwenden.
Es gelten die folgenden Regeln:
• Wenn Sie ein “Grundlagentheorem” verwenden, müssen Sie dies angeben und
erklären warum das Theorem angewendet werden kann.
• Organisieren Sie Ihre Arbeit in einer einigermaßen ordentlichen und kohärenten Weise
in dem vorgesehenen Platz. Arbeiten, die über die ganze Seite verstreut sind und keine klare
Ordnung aufweisen, werden sehr wenige Punkte erhalten.
• Mysteriöse oder nicht belegte Antworten werden nicht die volle Punktzahl er-
halten. Eine richtige Antwort, die nicht durch Berechnungen, Erklärungen oder algebrais-
che Arbeit untermauert ist, wird keine Punkte erhalten; eine falsche Antwort, die durch im
Wesentlichen korrekte Berechnungen und Erklärungen untermauert wird, kann noch Teilpunkte
erhalten.
• Wenn Sie mehr Platz benötigen, verwenden Sie die Rückseite der Seiten; geben Sie deutlich
an, wann Sie dies getan haben.
• Schreiben Sie Ihren gesamten Quellcode in Python.
Schreiben Sie nicht in die Tabelle auf der rechten Seite.
Algorithms and Data Structures Exam - Page 3 of 17 2024-07-12
1. (25 points) EN: Recursion, recurrence relations, trees and quantum computing /
DE: Rekursion, Rekurrenzgleichungen, Bäume und Quantencomputing
(a) (4 points) EN: Implement function min max1(data) that returns both, the minimum and
maximum value of a list. Your function must use a loop. Do not use recursion.
DE: Implementieren Sie eine Funktion min max1(data), die sowohl den Minimal- als auch
den Maximalwert einer Liste zurückgibt. Ihre Funktion muss eine Schleife verwenden.
Verwenden Sie keine Rekursion.
Algorithms and Data Structures Exam - Page 4 of 17 2024-07-12
(b) (5 points) EN: Implement function min max2 that returns both, the minimum and max-
imum value of a list. Your function must use recursion. Do not use a loop. Rethink the
signature of min max2.
DE: Implementieren Sie eine Funktion min max2, die sowohl den Minimal- als auch den
Maximalwert einer Liste zurückgibt. Ihre Funktion muss Rekursion verwenden. Verwen-
den Sie keine Schleife. Überdenken Sie die Signatur von min max2.
Algorithms and Data Structures Exam - Page 5 of 17 2024-07-12
(c) (6 points) EN: We define Deggendorf numbers as follows:
DE: Wir definieren Deggendorf-Zahlen wie folgt:
1 n ∈ {0, 1, 2}
deg(n) = .
deg(n − 1) + deg(n − 2) + deg(n − 3) n≥3
EN: Derive the worst-case running time complexity of a naive implementation.
DE: Leiten Sie die Worst-Case-Laufzeitkomplexität einer naiven Implementierung her.
Algorithms and Data Structures Exam - Page 6 of 17 2024-07-12
(d) (7 points) EN: In class, we implemented a binary tree as follows:
DE: In der Vorlesung haben wir einen Binärbaum wie folgt implementiert:
class Node:
def init (self , data ):
[Link] = None
[Link] = None
[Link] = data
def sum(self ):
[...]
EN: Implement method sum that returns the sum of values of all nodes of the tree.
DE: Implementieren Sie die Methode sum, welche die Summe der Werte aller Knoten
des Baums zurückliefert.
Algorithms and Data Structures Exam - Page 7 of 17 2024-07-12
(e) (3 points) EN: What is Grover’s algorithm? Provide a brief explanation of the algorithm
and discuss its speedup compared to a traditional algorithm. Use the O notation in your
explanation.
DE: Was ist der Grover-Algorithmus? Liefern Sie eine kurze Erklärung des Algorith-
mus und diskutieren Sie seine Beschleunigung gegenüber einem traditionellen Algorithmus.
Nutzen Sie die O-Notation in Ihrer Erklärung.
repeated
Algorithms and Data Structures Exam - Page 8 of 17 2024-07-12
2. (25 points) EN: Dynamic data structures and bisection /
DE: Dynamische Datenstrukturen und Bisektion
(a) (4 points) EN: Add exactly one method to class UnsortedTableMap that allows to add
or update a key-value pair. Your method must be easily usable in the following form:
obj[k] = v.
DE: Fügen Sie der Klasse UnsortedTableMap genau eine Methode hinzu, mit der ein
Schlüssel-Wert-Paar hinzugefügt oder aktualisiert werden kann. Ihre Methode muss in der
folgenden Form leicht nutzbar sein: obj[k] = v.
from collections .abc import MutableMapping
class MapBase ( MutableMapping ):
class Item :
slots = ’ key ’, ’ value ’
def init (self , k, v):
self. key = k
self. value = v
def eq (self , other ):
return self. key == other. key
def ne (self , other ):
return not (self == other)
def lt (self , other ):
return self. key < other. key
class UnsortedTableMap ( MapBase ):
def init (self ):
self. table = []
def getitem (self , k):
for item in self. table :
if k == item. key :
return item. value
raise KeyError (’Key Error {0} ’. format (k))
Algorithms and Data Structures Exam - Page 9 of 17 2024-07-12
EN: Continued: / DE: fortgesetzt:
(b) (3 points) EN: Draw the 11-entry hash table that results from using the hash function
h(i) = (3i + 2) mod 11, to hash the keys 13, 41, 19, 88, 23, 94, 11, 39 and 5, assuming colli-
sions are handled by chaining.
DE: Zeichnen Sie die Hash-Tabelle mit 11 Einträgen, die sich aus der Verwendung der
Hash-Funktion h(i) = (3i+2) mod 11, um die Schlüssel 13, 41, 19, 88, 23, 94, 11, 39 und 5 zu
hashen, ergibt, unter der Annahme, dass Kollisionen durch Verkettung behandelt werden.
Algorithms and Data Structures Exam - Page 10 of 17 2024-07-12
(c) (2 points) EN: How can you create a nested dictionary such as d[key1][key2] = value
in Python? Provide a short code example.
DE: Wie kann man in Python ein verschachteltes Dictionary wie d[key1][key2] = value
erstellen? Liefern Sie ein kurzes Code-Beispiel.
(d) (3 points) EN: You will later need the following helper function:
DE: Sie werden später die folgende Hilfsfunktion benötigen:
−1 x<0
sign(x) = 0 x=0 .
1 x>0
EN: Implement this function.
DE: Implementieren Sie diese Funktion.
Algorithms and Data Structures Exam - Page 11 of 17 2024-07-12
(e) (13 points) EN: In mathematics, the bi-
section is a root-finding method that ap-
plies to any continuous function for which
one knows two values with opposite signs.
The method consists of repeatedly bisect-
ing the interval defined by these values
and then selecting the subinterval in which
the function changes sign, and therefore
must contain a root. This process is de-
picted on the right.
Implement a function bisection(f, a, b, tol, max iterations). The parameters
are:
• f: reference to function for which the root shall be found
• a and b: left and right interval boundaries
• tol: tolerance for convergence
• max iterations: maximum number of iterations
Hints:
• When you half the interval, make sure the sign of the values at both boundaries is
different.
• There are different possible ways how to use the tolerance for convergence. Therefore,
also briefly describe how you have exactly used it.
DE: In der Mathematik ist die Bisektion eine Methode zur Nullstellensuche, die auf jede
kontinuierliche Funktion angewendet werden kann, für die man zwei Werte mit entgegenge-
setzten Vorzeichen kennt. Die Methode besteht darin, das durch diese Werte definierte
Intervall wiederholt zu halbieren und dann das Teilintervall auszuwählen, in dem die Funk-
tion das Vorzeichen wechselt und daher eine Nullstelle enthalten muss. Dieser Vorgang
ist rechts abgebildet.
Implementieren Sie eine Funktion bisection(f, a, b, tol, max iterations). Die
Parameter sind:
• f: Referenz zur Funktion, für welche die Nullstelle gefunden werden soll
• a und b: linke und rechte Intervallgrenzen
• tol: Toleranz für Konvergenz
• max iterations: maximale Anzahl an Iterationen
Hinweise:
• Wenn Sie das Intervall halbieren, achten Sie darauf, dass das Vorzeichen der Werte
an beiden Grenzen unterschiedlich ist.
• Es gibt verschiedene Möglichkeiten, die Toleranz für die Konvergenz zu nutzen. Beschreiben
Sie daher auch kurz, wie Sie sie genau verwendet haben.
Algorithms and Data Structures Exam - Page 12 of 17 2024-07-12
EN: Continued: / DE: fortgesetzt:
Algorithms and Data Structures Exam - Page 13 of 17 2024-07-12
EN: Continued: / DE: fortgesetzt:
second method,
Algorithms and Data Structures Exam - Page 14 of 17 2024-07-12
3. (25 points) EN: Sorting algorithms /
DE: Sortieralgorithmen
(a) (3 points) EN: Name three sorting algorithms that are stable. Names only.
DE: Nennen Sie drei Sortieralgorithmen, die stabil sind. Nur die Namen.
1. Merge Sort
2. Bubble Sort
3. Insertion Sort
(b) (5 points) EN: Explain what stability is and provide an example.
DE: Erklären Sie, was Stabilität ist und liefern Sie ein Beispiel.
Algorithms and Data Structures Exam - Page 15 of 17 2024-07-12
(c) (7 points) EN: Merge sort relies on a function that merges two sorted lists. This can be
visualized as following:
DE: Mergesort basiert auf einer Funktion, die zwei sortierte Listen zusammenführt. Dies
kann wie folgt veranschaulicht werden:
EN: Complete the following merge function:
DE: Vervollständigen Sie die folgende Zusammenführungsfunktion:
def merge (S1 , S2 , S):
[...]
Algorithms and Data Structures Exam - Page 16 of 17 2024-07-12
(d) (3 points) EN: Provide the worst-case, best-case and average-case running time complex-
ities for merge sort and quicksort, respectively.
DE: Geben Sie die Worst-Case-, Best-Case- und Average-Case-Laufzeitkomplexitäten für
Mergesort und Quicksort an.
(e) (2 points) EN: In class, we implement bubble sort as follows:
DE: In der Vorlesung haben wir Bubblesort wie folgt implementiert:
def bubble sort (A):
n = len(A)
for i in range(n):
for j in range (n−i−1):
if A[j] > A[j+1]:
tmp = A[j]
A[j] = A[j+1]
A[j+1] = tmp
EN: What is the best-case running time complexity of this implementation? Explain why
and what property you are assuming in the data set in this case.
DE: Was ist die Best-Case-Laufzeitkomplexität dieser Implementierung? Erklären Sie,
warum und von welcher Eigenschaft Sie in diesem Fall im Datensatz ausgehen.
Algorithms and Data Structures Exam - Page 17 of 17 2024-07-12
(f) (5 points) EN: Re-implement bubble sort so that its best-case running time complexity
is O(n).
DE: Implementieren Sie Bubblesort erneut, sodass die Best-Case-Laufzeitkomplexität O(n)
beträgt.
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2023-24 Winter Term
Resit Exam
2024-01-26
Time Limit: 90 Minutes Mark:
English (EN): This exam contains 17 pages (including this cover page) and 3 problems. Answer
2 problems. If you answer 3 problems, the best 2 count. Check to see if any pages are missing.
Enter all requested information on the top of this page, and put your seat number on the top of
every page, in case the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Deutsch (DE): Diese Klausur umfasst 17 Seiten (einschließlich dieses Deckblatts) und 3 Aufgaben
(Problems). Beantworten Sie 2 Aufgaben. Wenn Sie 3 Aufgaben beantworten, zählen die besten 2.
Überprüfen Sie, ob Seiten fehlen. Geben Sie alle geforderten Informationen oben auf dieser Seite
an, und notieren Sie Ihre Platznummer oben auf jeder Seite ein, falls die Seiten getrennt werden.
In dieser Klausur dürfen Sie nur einen Taschenrechner (kein Computeralgebrasystem) und ein ein-
seitiges handgeschriebenes A4-Notizblatt verwenden.
Algorithms and Data Structures Resit Exam - Page 2 of 17 2024-01-26
Es gelten die folgenden Regeln:
• Wenn Sie ein “Grundlagentheorem” verwenden, müssen Sie dies angeben und
erklären warum das Theorem angewendet werden kann.
• Organisieren Sie Ihre Arbeit in einer einigermaßen ordentlichen und kohärenten Weise
in dem vorgesehenen Platz. Arbeiten, die über die ganze Seite verstreut sind und keine klare
Ordnung aufweisen, werden sehr wenige Punkte erhalten.
• Mysteriöse oder nicht belegte Antworten werden nicht die volle Punktzahl er-
halten. Eine richtige Antwort, die nicht durch Berechnungen, Erklärungen oder algebrais-
che Arbeit untermauert ist, wird keine Punkte erhalten; eine falsche Antwort, die durch im
Wesentlichen korrekte Berechnungen und Erklärungen untermauert wird, kann noch Teilpunkte
erhalten.
• Wenn Sie mehr Platz benötigen, verwenden Sie die Rückseite der Seiten; geben Sie deutlich
an, wenn Sie dies getan haben.
Schreiben Sie nicht in die Tabelle auf der rechten Seite.
Algorithms and Data Structures Resit Exam - Page 3 of 17 2024-01-26
1. (25 points) EN: Binary search and bisection /
DE: Binärsuche und Bisektion
(a) (7 points) EN: In class, we discussed the recursive implementation of binary search be-
low. Implement an iterative variation of binary search that has the same running time
complexity.
DE: In der Vorlesung haben wir die unten aufgeführte rekursive Implementierung der
Binärsuche besprochen. Implementieren Sie eine iterative Variation der Binärsuche, welche
die gleiche Laufzeitkomplexität hat.
def search binary (data , target , low=None , high=None ):
if low == None: low = 0
if high == None: high = len(data) − 1
if low > high:
return False
else:
mid = (low + high) // 2 #Or: mid = low + (high−low) // 2
if target == data[mid ]:
return True
elif target < data[mid ]:
return search binary (data , target , low , mid −1)
else:
return search binary (data , target , mid +1, high)
Algorithms and Data Structures Resit Exam - Page 4 of 17 2024-01-26
(b) (3 points) EN: Provide the space complexity of both algorithms and provide explanations
to support your argument. Which one is in-place?
DE: Liefern Sie die Speicherplatzkomplexität beider Algorithmen, sowie Erklärungen um
Ihre Argumentation zu untermauern. Welcher ist in-place?
Algorithms and Data Structures Resit Exam - Page 5 of 17 2024-01-26
(c) (3 points) EN: You will later need the following helper function:
DE: Sie werden später die folgende Hilfsfunktion benötigen:
−1 x<0
sign(x) = 0 x=0 .
1 x>0
EN: Implement this function in Python.
DE: Implementieren Sie diese Funktion in Python.
(d) (12 points) EN: In mathematics, the bi-
section is a root-finding method that ap-
plies to any continuous function for which
one knows two values with opposite signs.
The method consists of repeatedly bisect-
ing the interval defined by these values
and then selecting the subinterval in which
the function changes sign, and therefore
must contain a root. This process is de-
picted on the right.
Implement a function bisection(f, a, b, tol, max iterations). The parameters
are:
• f: reference to function for which the root shall be found
• a and b: left and right interval boundaries
• tol: tolerance for convergence
Algorithms and Data Structures Resit Exam - Page 6 of 17 2024-01-26
• max iterations: maximum number of iterations
Hints:
• When you half the interval, make sure the sign of the values at both boundaries is
different.
• There are different possible ways how to use the tolerance for convergence. Therefore,
also briefly describe how you have exactly used it.
DE: In der Mathematik ist die Bisektion eine Methode zur Nullstellensuche, die auf jede
kontinuierliche Funktion angewendet werden kann, für die man zwei Werte mit entgegenge-
setzten Vorzeichen kennt. Die Methode besteht darin, das durch diese Werte definierte
Intervall wiederholt zu halbieren und dann das Teilintervall auszuwählen, in dem die Funk-
tion das Vorzeichen wechselt und daher eine Nullstelle enthalten muss. Dieser Vorgang
ist rechts abgebildet.
Implementieren Sie eine Funktion bisection(f, a, b, tol, max iterations). Die
Parameter sind:
• f: Referenz zur Funktion, für welche die Nullstelle gefunden werden soll
• a und b: linke und rechte Intervallgrenzen
• tol: Toleranz für Konvergenz
• max iterations: maximale Anzahl an Iterationen
Hinweise:
• Wenn Sie das Intervall halbieren, achten Sie darauf, dass das Vorzeichen der Werte
an beiden Grenzen unterschiedlich ist.
• Es gibt verschiedene Möglichkeiten, die Toleranz für die Konvergenz zu nutzen. Beschreiben
Sie daher auch kurz, wie Sie sie genau verwendet haben.
Repeated
Algorithms and Data Structures Resit Exam - Page 7 of 17 2024-01-26
EN: Continued: / DE: fortgesetzt:
Algorithms and Data Structures Resit Exam - Page 8 of 17 2024-01-26
2. (25 points) EN: Quantum computing, recurrence relations and decision trees /
DE: Quantencomputing, Rekurrenzgleichungen und Entscheidungsbäume
(a) (4 points) EN: The vector representation of a single qubit is:
DE: Die Vektorrepräsentation eines einzelnen Qubit lautet wie folgt:
α
|ai = α|0i + β|1i = .
β
EN: Explain what α and are and what makes a qubit different to a bit. Also provide the
respective constraints for α and β such that |ai is a valid qubit.
DE: Erklären Sie, was α und β sind und was ein Qubit gegenüber einem Bit unterscheidet.
Liefern Sie auch die respektiven Bedingungen für α und β, sodass |ai ein gültiges Qubit
ist.
Repeated
Algorithms and Data Structures Resit Exam - Page 9 of 17 2024-01-26
(b) (6 points) EN: We define Deggendorf numbers as following:
DE: Wir definieren Deggendorf-Zahlen wie folgt:
1 n ∈ {0, 1, 2}
deg(n) = .
deg(n − 1) + deg(n − 2) + deg(n − 3) n≥3
EN: Derive the worst-case running time complexity of a naive implementation.
DE: Leiten Sie die ungünstigste (worst-case) Laufzeitkomplexität einer naiven Implemen-
tierung her.
Repeated
Algorithms and Data Structures Resit Exam - Page 10 of 17 2024-01-26
(c) (15 points) EN: Use the ID3 decision tree learning algorithm in order to learn a tree for
the attack label using the following data set. Write out intermediate steps and the result.
DE: Nutzen Sie den ID3-Entscheidungsbaumlernalgorithmus um einen Baum für das La-
bel attack mit dem folgenden Datensatz zu lernen. Schreiben Sie Zwischenschritte und
das Ergebnis aus.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Repeated
Algorithms and Data Structures Resit Exam - Page 11 of 17 2024-01-26
EN: Continued: / DE: fortgesetzt:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
///
Algorithms and Data Structures Resit Exam - Page 12 of 17 2024-01-26
EN: Continued: / DE: fortgesetzt:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
///
Algorithms and Data Structures Resit Exam - Page 13 of 17 2024-01-26
3. (25 points) EN: Graphs and lists /
DE: Graphen und Listen
(a) (5 points) EN: Provide a formal k-tuple definition of the following graph G:
DE: Liefern Sie eine formale k-Tupel-Definition des folgenden Graphen G:
Algorithms and Data Structures Resit Exam - Page 14 of 17 2024-01-26
(b) (2 points) EN: What is a frontier in the context of search algorithms?
DE: Was ist ein “Grenzgebiet” (Frontier) im Kontext von Suchalgorithmen?
In the context of search algorithms, the frontier refers to:
The set of all nodes that have been discovered but not yet explored.
Explanation:
When a search algorithm explores a state space (like a graph or tree), it starts from an initial state and
expands nodes one at a time.
The frontier is a data structure (often a queue, stack, or priority queue) that keeps track of which nodes to
expand next.
(c) (6 points) EN: In class, we generalized the shortest path search providing the following
interface: shortest path search(start, successors, is goal). Briefly describe the
types of these three parameters and what they do.
DE: In der Vorlesung haben wir die Kürzeste-Pfade-Suche mit der folgenden Schnittstelle
generalisiert: shortest path search(start, successors, is goal). Beschreiben Sie
kurz die Typen der drei Parameter und was sie tun.
Algorithms and Data Structures Resit Exam - Page 15 of 17 2024-01-26
(d) (5 points) EN: Below you find the implementation of shortest path search. Explain
why frontier being a Python list makes this implementation unnecessarily slow. Which
data structure would you use instead? Use the O and Θ notations to support your argu-
ment.
DE: Unten finden Sie die Implementierung von shortest path search. Exklären Sie,
warum frontier als Python-Liste diese Implementierung unnötigerweise langsam macht.
Welche Datenstruktur würden Sie stattdessen nutzen? Nutzen die O- and Θ-Notationen
um Ihre Argumentation zu untermauern.
01: def shortest path search (start , successors , is goal ):
02: ”””Find the shortest path from start state to a state”””
03: ”””such that is goal ( state ) is true .”””
04: if is goal (start ):
05: return [start]
06: # set of states we have visited
explored = set ([ start ])
07: frontier = [ [start] ] # ordered l i s t of paths we have blazed
08: while frontier :
09: path = frontier .pop (0)
10: s = path[−1]
11: for (state , action ) in successors (s). items ():
12: if state not in explored :
13: explored .add(state)
14: path2 = path + [action , state]
15: if is goal (state ):
16: return path2
17: else:
18: frontier . append (path2)
19: return Fail
20: Fail = []
Algorithms and Data Structures Resit Exam - Page 16 of 17 2024-01-26
EN: Continued: / DE: fortgesetzt:
(e) (3 points) EN: Provide a more efficient implementation using the different data structure.
You only need to rewrite a few lines. Clearly reference which lines you are rewriting. You
can omit any imports. For accessing or modifying the different data structure, use the
corresponding ADT’s methods discussed in class.
DE: Liefern Sie eine effizientere Implementierung unter Einsatz einer anderen Daten-
struktur. Sie müssen nur eine wenige Zeilen umschreiben. Verweisen Sie klar darauf,
welche Zeilen Sie umschreiben. Imports können Sie auslassen. Für den lesenden oder mod-
ifizierenden Zugriff auf die andere Datenstruktur nutzen Sie die Methoden des entsprechen-
den ADT, den wir in der Vorlesung besprochen haben.
Algorithms and Data Structures Resit Exam - Page 17 of 17 2024-01-26
(f) (4 points) EN: In class, we discussed the MyArray class. Implement the setitem (self,
k, value) method. It must also be able to handle negative indices.
DE: In der Vorlesung haben wir die Klasse MyArray besprochen. Implementieren Sie
die Methode setitem (self, k, value). Sie muss auch negative Indexe verarbeiten
können.
import ctypes
class MyArray :
def init (self ):
self. n = 0
self. capacity = 1
self. A = self. make array (self. capacity )
def len (self ):
return self. n
def getitem (self , k):
[...]
def append (self , obj ):
[...]
def resize (self , c):
[...]
def make array (self , c):
return (c ∗ ctypes . py object )()
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2023 Summer Term
Exam
2023-07-17
Time Limit: 90 Minutes Mark:
This exam contains 13 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Algorithms and Data Structures Exam - Page 2 of 13 2023-07-17
1. (25 points) Linked lists
(a) (8 points) Implement method add that adds an element at the end of a linked list.
class LinkedList :
class Node :
def init (self , element ):
self. element = element
self. next element = None
def init (self ):
self. head = None
self. size = 0
Algorithms and Data Structures Exam - Page 3 of 13 2023-07-17
(b) (6 points) Implement method remove first that removes the first element of the linked
list. This method will not return anything.
class LinkedList:
class Node:
def __init__(self, element):
[Link] = element
self.next_element = None
def __init__(self):
[Link] = None
[Link] = 0
def add(self, element):
new_node = [Link](element)
if [Link] is None:
[Link] = new_node
else:
current = [Link]
while current.next_element:
current = current.next_element
current.next_element = new_node
[Link] += 1
(c) (7 points) Implement a generator that returns all values of a list when being used as
follows.
lst = LinkedList ()
# . . . add values
for value in lst:
# use value for something
class LinkedList:
class Node:
def __init__(self, element):
[Link] = element
self.next_element = None
def __init__(self):
[Link] = None
[Link] = 0
def add(self, element):
new_node = [Link](element)
if [Link] is None:
[Link] = new_node
Algorithms and Data Structures Exam - Page 4 of 13 2023-07-17
(d) (4 points) Name two benefits of linked lists and array lists, respectively.
Algorithms and Data Structures Exam - Page 5 of 13 2023-07-17
2. (25 points) Decision trees and complexity analysis
(a) (8 points) Provide a pseudo code implementation of the ID3 decision tree learning algo-
rithm that we discussed in class.
Function ID3(examples, attributes, target_attribute):
IF all examples have the same classification THEN
RETURN a leaf node with that classification
END IF
IF attributes is empty THEN
RETURN a leaf node with the most common classification in examples
END IF
root_attribute attribute from attributes with highest information gain
tree create a decision node labeled with root_attribute
FOR each value v of root_attribute DO:
subset subset of examples where root_attribute = v
IF subset is empty THEN
leaf create a leaf node with the most common classification in examples
add branch to tree with label v and leaf
ELSE
subtree ID3(subset, attributes - {root_attribute}, target_attribute)
add branch to tree with label v and subtree
END IF
END FOR
RETURN tree
Algorithms and Data Structures Exam - Page 6 of 13 2023-07-17
(b) (7 points) Describe the approach discussed in class for finding the most important at-
tribute in the ID3 decision tree learning algorithm. Also provide the underlying mathe-
matical definitions in order to support your description.
Algorithms and Data Structures Exam - Page 7 of 13 2023-07-17
(c) (5 points) Use the approach in order to find the root for the attack label using the
following data set. Write out intermediate steps and the result.
sky air humid wind attack
1 sunny warm normal strong +
2 sunny warm high strong +
3 rainy cold high strong -
4 sunny warm high strong +
5 sunny warm normal weak -
6 rainy warm high strong +
Repeated
Algorithms and Data Structures Exam - Page 8 of 13 2023-07-17
(d) (4 points) Explain why analyzing the complexity of an algorithm is usually preferred over
measuring the running time. Provide at least two benefits of complexity analysis.
(e) (1 point) Provide Õ(h(n)) for h(n) = n2.3 log(n) log(log(n)) + log(n).
Algorithms and Data Structures Exam - Page 9 of 13 2023-07-17
3. (25 points) Fast matrix multiplication, recurrence relations and quantum computing
(a) (3 points) Provide the worst-case running time complexity of naive matrix multiplication.
Also, provide a brief justification.
(b) (4 points) Let A, B be two square matrices over R. We want to calculate the matrix
product C as:
n ⇥2n
C = AB A, B, C 2 R2 .
If the matrices A, B are not of type 2n ⇥ 2n we fill the missing rows and columns with
zeros. We partition A, B and C into equally sized block matrices:
✓ ◆ ✓ ◆ ✓ ◆
A1,1 A1,2 B1,1 B1,2 C1,1 C1,2
A= ,B= ,C= .
A2,1 A2,2 B2,1 B2,2 C2,1 C2,2
Define how to calculate C1,1 , C1,2 , C2,1 and C2,2 . # Repeated
Algorithms and Data Structures Exam - Page 10 of 13 2023-07-17
(c) (4 points) The following 7 auxiliary matrices can be defined:
M1 := (A1,1 + A2,2 )(B1,1 + B2,2 ),
M2 := (A2,1 + A2,2 )B1,1 ,
M3 := A1,1 (B1,2 B2,2 ),
M4 := A2,2 (B2,1 B1,1 ),
M5 := (A1,1 + A1,2 )B2,2 ,
M6 := (A2,1 A1,1 )(B1,1 + B1,2 ),
M7 := (A1,2 A2,2 )(B2,1 + B2,2 ).
Now the Strassen algorithm re-expresses Ci,j 1 :
C1,1 = M1 + M4 M5 + M7 ,
C1,2 = M3 + M5 ,
C2,1 = M2 + M4 ,
C2,2 = M1 M2 + M3 + M6 .
Show that C2,1 is calculated correctly.
#Repeated
1
We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of
R). The resulting product will be padded with zeroes just like A and B, and should be stripped of the corresponding
rows and columns.
Algorithms and Data Structures Exam - Page 11 of 13 2023-07-17
(d) (2 points) Provide the recurrence relation for the Strassen algorithm.
#Repeated
(e) (5 points) Using the recurrence relation, derive the worst-case running time complexity of
the Strassen algorithm.
#Repeated
Algorithms and Data Structures Exam - Page 12 of 13 2023-07-17
(f) (4 points) The vector representation of a single qubit is:
↵
|ai = ↵|0i + |1i = .
Explain what ↵ and are and what makes a qubit di↵erent to a bit. Also provide the
respective constraints for ↵ and such that |ai is a valid qubit.
#Repeated
(g) (3 points) What is Grover’s algorithm? Provide a brief explanation of the algorithm and
discuss its speedup compared to a traditional algorithm. Use the O notation in your
explanation.
#Repeated
Algorithms and Data Structures Exam - Page 13 of 13 2023-07-17
Continued:
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2022-23 Winter Term
Resit Exam
2022-12-19
Time Limit: 90 Minutes Mark:
This exam contains 14 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Algorithms and Data Structures Resit Exam - Page 2 of 14 2022-12-19
1. (25 points) Fast matrix multiplication
(a) (3 points) Provide the worst-case running time complexity of naive matrix multiplication.
Also, provide a brief justification.
(b) (2 points) The recurrence relation for naive matrix multiplication is as follows:
T (n) = 8T (n/2) + Θ(n2 )
T (1) = 1.
Explain what the part Θ(n2 ) stands for in naive matrix multiplication.
(c) (5 points) Using the recurrence relation, derive the worst-case running time complexity of
naive matrix multiplication.
Algorithms and Data Structures Resit Exam - Page 3 of 14 2022-12-19
Continued:
(d) (4 points) Let A, B be two square matrices over R. We want to calculate the matrix
product C as:
n ×2n
C = AB A, B, C ∈ R2 .
If the matrices A, B are not of type 2n × 2n we fill the missing rows and columns with
zeros. We partition A, B and C into equally sized block matrices:
A1,1 A1,2 B1,1 B1,2 C1,1 C1,2
A= ,B= ,C= .
A2,1 A2,2 B2,1 B2,2 C2,1 C2,2
Define how to calculate C1,1 , C1,2 , C2,1 and C2,2 .
# Repeated
Algorithms and Data Structures Resit Exam - Page 4 of 14 2022-12-19
(e) (4 points) The following 7 auxiliary matrices can be defined:
M1 := (A1,1 + A2,2 )(B1,1 + B2,2 ),
M2 := (A2,1 + A2,2 )B1,1 ,
M3 := A1,1 (B1,2 − B2,2 ),
M4 := A2,2 (B2,1 − B1,1 ),
M5 := (A1,1 + A1,2 )B2,2 ,
M6 := (A2,1 − A1,1 )(B1,1 + B1,2 ),
M7 := (A1,2 − A2,2 )(B2,1 + B2,2 ).
Now the Strassen algorithm re-expresses Ci,j 1 :
C1,1 = M1 + M4 − M5 + M7 ,
C1,2 = M3 + M5 ,
C2,1 = M2 + M4 ,
C2,2 = M1 − M2 + M3 + M6 .
Show that C1,2 is calculated correctly.
#Repeated
1
We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of
R). The resulting product will be padded with zeroes just like A and B, and should be stripped of the corresponding
rows and columns.
Algorithms and Data Structures Resit Exam - Page 5 of 14 2022-12-19
(f) (2 points) Provide the recurrence relation for the Strassen algorithm.
#Repeated
(g) (5 points) Using the recurrence relation, derive the worst-case running time complexity of
the Strassen algorithm.
#Repeated
Algorithms and Data Structures Resit Exam - Page 6 of 14 2022-12-19
2. (25 points) Sorting algorithms
(a) (2 points) Name two sorting algorithms that are stable. Names only.
Repeated
(b) (2 points) Name two sorting algorithms that are not stable. Names only.
1. Quick Sort
2. Heap Sort
(c) (5 points) Explain what stability is and provide an example.
Algorithms and Data Structures Resit Exam - Page 7 of 14 2022-12-19
(d) (7 points) Merge sort relies on a function that merges two sorted lists. This can be
visualized as follows:
Complete the following merge function:
def merge (S1 , S2 , S):
[...]
#Repeated
Algorithms and Data Structures Resit Exam - Page 8 of 14 2022-12-19
(e) (3 points) Provide the worst-case, best-case and average-case running time complexities
for merge sort and quicksort, respectively.
#Repeat
(f) (2 points) Discuss for what kind of data quicksort may exhibit the worst-case running
time complexity behavior.
#Repeated
(g) (4 points) How could quicksort’s worst-case expected running time complexity be im-
proved? Briefly explain your approach and provide the worst-case and worst-case expected
running time complexities.
Algorithms and Data Structures Resit Exam - Page 9 of 14 2022-12-19
3. (25 points) Binary search, trees and quantum computing
(a) (7 points) In class, we discussed the recursive implementation of binary search below. Im-
plement an iterative variation of binary search that has the same running time complexity.
#Repeated
def search binary (data , target , low=None , high=None ):
if low == None: low = 0
if high == None: high = len(data) − 1
if low > high:
return False
else:
mid = (low + high) // 2 #Or: mid = low + (high−low) // 2
if target == data[mid ]:
return True
elif target < data[mid ]:
return search binary (data , target , low , mid −1)
else:
return search binary (data , target , mid +1, high)
Algorithms and Data Structures Resit Exam - Page 10 of 14 2022-12-19
Continued:
Algorithms and Data Structures Resit Exam - Page 11 of 14 2022-12-19
(b) (15 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
attack label using the following data set. Write out intermediate steps and the result.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
#Repeated
Algorithms and Data Structures Resit Exam - Page 12 of 14 2022-12-19
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Algorithms and Data Structures Resit Exam - Page 13 of 14 2022-12-19
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Algorithms and Data Structures Resit Exam - Page 14 of 14 2022-12-19
(c) (3 points) What is Shor’s algorithm? Provide a brief explanation of the algorithm and
discuss its speedup compared to a traditional algorithm. Use the O notation in your
explanation.
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2022 Summer Term
Exam
2022-07-20
Time Limit: 90 Minutes Mark:
This exam contains 14 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Algorithms and Data Structures Exam - Page 2 of 14 2022-07-20
1. (25 points) Graphs, binary exponentiation, complexity and recurrence relations
(a) (5 points) Provide a formal k-tuple definition of the following graph G:
Algorithms and Data Structures Exam - Page 3 of 14 2022-07-20
(b) (4 points) A trivial recursive definition of the power function follows from the fact that
xn = x × xn−1 for n > 0:
1 n=0
power(x, n) = .
x × power(x, n − 1) otherwise
Implement this function in Python using recursion.
(c) (1 point) Provide the running time complexity of your function.
Algorithms and Data Structures Exam - Page 4 of 14 2022-07-20
(d) (5 points) There is a much faster way to compute the power function using an alternative
definition that employs a squaring technique:
1 n=0
power(x, n) = power(x, n2 )2 if n > 0 is even .
x × power(x, n2 )2 if n > 0 is odd
Let n2 denote the floor of the division (expressed as n // 2 in Python). Implement this
function in Python using recursion.
Algorithms and Data Structures Exam - Page 5 of 14 2022-07-20
(e) (5 points) Derive the worst-case running time complexity of your efficient implementation.
Start by providing the recurrence relation. (Do not use the master theorem.)
Algorithms and Data Structures Exam - Page 6 of 14 2022-07-20
(f) (5 points) Use the master theorem to solve the recurrence relation in order derive the
exact solution. Clearly state which case you use and why.
Algorithms and Data Structures Exam - Page 7 of 14 2022-07-20
2. (25 points) Sorting algorithms
(a) (2 points) Name two sorting algorithms that are stable. Names only.
#Repeated
(b) (2 points) Name two sorting algorithms that are not stable. Names only.
#Repeated
(c) (5 points) Explain what stability is and provide an example.
#Repeated
Algorithms and Data Structures Exam - Page 8 of 14 2022-07-20
(d) (7 points) Merge sort relies on a function that merges two sorted lists. This can be
visualized as follows:
Complete the following merge function:
def merge (S1 , S2 , S):
[...]
#Repeated
Algorithms and Data Structures Exam - Page 9 of 14 2022-07-20
(e) (3 points) Provide the worst-case, best-case and average-case running time complexities
for merge sort and quicksort, respectively.
#Repeated
(f) (2 points) Discuss for what kind of data quicksort may exhibit the worst-case running
time complexity behavior.
(g) (4 points) How could quicksort’s worst-case expected running time complexity be im-
proved? Briefly explain your approach and provide the worst-case and worst-case expected
running time complexities.
Algorithms and Data Structures Exam - Page 10 of 14 2022-07-20
3. (25 points) Trees and quantum computing
(a) (7 points) Implement a function invert that inverts a tree. An example is depicted below.
Note that a node may have 0, 1 or 2 children. Use the TreeNode class below.
From to
class TreeNode :
def init (self , val ):
[Link] = val
[Link] = None
[Link] = None
def invert (node ):
[...]
Algorithms and Data Structures Exam - Page 11 of 14 2022-07-20
(b) (15 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
attack label using the following data set. Write out intermediate steps and the result.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
#Repeated
Algorithms and Data Structures Exam - Page 12 of 14 2022-07-20
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
Algorithms and Data Structures Exam - Page 13 of 14 2022-07-20
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
Algorithms and Data Structures Exam - Page 14 of 14 2022-07-20
(c) (3 points) What is Grover’s algorithm? Provide a brief explanation of the algorithm and
discuss its speedup compared to a traditional algorithm. Use the O notation in your
explanation.
#Repeated
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2021-22 Winter Term
Resit Exam
2021-12-13
Time Limit: 90 Minutes Mark:
This exam contains 15 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Note: This sample exam does not cover all top-
ics discussed towards the end of the term. The
content of the entire course will be relevant for
the final exam.
Algorithms and Data Structures Resit Exam - Page 2 of 15 2021-12-13
1. (25 points) Graphs and lists
(a) (5 points) Provide a formal k-tuple definition of the following graph G:
#Repeated
Algorithms and Data Structures Resit Exam - Page 3 of 15 2021-12-13
(b) (2 points) What is a frontier in the context of search algorithms?
#Repeated
(c) (6 points) In class, we generalized the shortest path search providing the following inter-
face: shortest path search(start, successors, is goal). Briefly describe the types
of these three parameters and what they do.
#Repeated
Algorithms and Data Structures Resit Exam - Page 4 of 15 2021-12-13
(d) (5 points) Below you find the implementation of shortest path search. Explain why
frontier being a Python list makes this implementation unnecessarily slow. Which data
structure would you use instead? Use the O and Θ notations to support your argument.
01: def shortest path search (start , successors , is goal ):
02: ”””Find the shortest path from start state to a state”””
03: ”””such that is goal ( state ) is true .”””
04: if is goal (start ):
05: return [start]
06: explored = set ([ start ]) # set of states we have visited
07: frontier = [ [start] ] # ordered l i s t of paths we have blazed
08: while frontier :
09: path = frontier .pop (0)
10: s = path[−1]
11: for (state , action ) in successors (s). items ():
12: if state not in explored :
13: explored .add(state)
14: path2 = path + [action , state]
15: if is goal (state ):
16: return path2
17: else:
18: frontier . append (path2)
19: return Fail
20: Fail = []
#Repeated
Algorithms and Data Structures Resit Exam - Page 5 of 15 2021-12-13
(e) (3 points) Provide a more efficient implementation using the different data structure. You
only need to rewrite a few lines. Clearly reference which lines you are rewriting. You
can omit any imports. For accessing or modifying the different data structure, use the
corresponding ADT’s methods discussed in class.
Algorithms and Data Structures Resit Exam - Page 6 of 15 2021-12-13
(f) (4 points) In class, we discussed the MyArray class. Implement the setitem (self,
k, value) method. It must also be able to handle negative indices.
import ctypes
class MyArray :
def init (self ):
self. n = 0
self. capacity = 1
self. A = self. make array (self. capacity )
def len (self ):
return self. n
def getitem (self , k):
[...]
def append (self , obj ):
[...]
def resize (self , c):
[...]
def make array (self , c):
return (c ∗ ctypes . py object )()
#Repeated
Algorithms and Data Structures Resit Exam - Page 7 of 15 2021-12-13
2. (25 points) Recursion and dynamic programming
(a) (4 points) We define Deggendorf numbers as following:
1 n ∈ {0, 1, 2}
deg(n) = .
deg(n − 1) + deg(n − 2) + deg(n − 3) n≥3
Implement a naive recursive algorithm in Python.
Algorithms and Data Structures Resit Exam - Page 8 of 15 2021-12-13
(b) (5 points) Derive the worst-case running time complexity of your naive implementation.
#Repeated
Algorithms and Data Structures Resit Exam - Page 9 of 15 2021-12-13
(c) (8 points) Re-implement your algorithm in Python using a top-down dynamic program-
ming approach.
Algorithms and Data Structures Resit Exam - Page 10 of 15 2021-12-13
(d) (8 points) Re-implement your algorithm in Python using a bottom-up dynamic program-
ming approach.
#Repeated
Algorithms and Data Structures Resit Exam - Page 11 of 15 2021-12-13
3. (25 points) Binary search and trees
(a) (7 points) In class, we discussed the recursive implementation of binary search below. Im-
plement an iterative variation of binary search that has the same running time complexity.
def search binary (data , target , low=None , high=None ):
if low == None: low = 0
if high == None: high = len(data) − 1
if low > high:
return False
else:
mid = (low + high) // 2 #Or: mid = low + (high−low) // 2
if target == data[mid ]:
return True
elif target < data[mid ]:
return search binary (data , target , low , mid −1)
else:
return search binary (data , target , mid +1, high)
#Repeated
Algorithms and Data Structures Resit Exam - Page 12 of 15 2021-12-13
Continued:
(b) (3 points) Provide the space complexity for both algorithms including a short justification.
Which of them is in-place?
Algorithms and Data Structures Resit Exam - Page 13 of 15 2021-12-13
(c) (15 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
attack label using the following data set. Write out intermediate steps and the result.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
#Repeated
Algorithms and Data Structures Resit Exam - Page 14 of 15 2021-12-13
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Algorithms and Data Structures Resit Exam - Page 15 of 15 2021-12-13
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2021 Summer Term
Exam
2021-07-20
Time Limit: 90 Minutes Mark:
This exam contains 15 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Algorithms and Data Structures Exam - Page 2 of 15 2021-07-20
1. (25 points) Graphs, recurrence relations and selected algorithms
(a) (3 points) Provide the adjacency matrix of the following graph G:
Repeated
(b) (2 points) What is the frontier in the context of search algorithms?
#Repeated
Algorithms and Data Structures Exam - Page 3 of 15 2021-07-20
(c) (5 points) Below you find the partial implementation of shortest path search discussed
in class. Complete the implementation.
01: def shortest path search (start , successors , is goal ):
02: ”””Find the shortest path from start state to a state”””
03: ”””such that is goal ( state ) is true .”””
04: if is goal (start ):
05: return [start]
06: explored = set ([ start ]) # set of states we have visited
07: frontier = [ [start] ] # ordered l i s t of paths we have blazed
08: while frontier :
09: path = frontier .pop (0)
10: s = path[−1]
11: for (state , action ) in successors (s). items ():
12: if state not in [...]
E1: return Fail
E2:Fail = []
#Repeated
Algorithms and Data Structures Exam - Page 4 of 15 2021-07-20
(d) (2 points) Provide the recurrence relation for merge sort.
#Repeat
(e) (5 points) Manually solve the recurrence relation in order derive the worst-case running
time complexity of merge sort. (Do not use the master theorem.)
#Repeat
Algorithms and Data Structures Exam - Page 5 of 15 2021-07-20
(f) (5 points) Use the master theorem to solve the recurrence relation in order derive the
exact solution. Clearly state which case you use and why.
#Repeat
Algorithms and Data Structures Exam - Page 6 of 15 2021-07-20
(g) (3 points) What is the running time complexity of the Strassen algorithm? Briefly explain
how the algorithm works.
#Repeat
Algorithms and Data Structures Exam - Page 7 of 15 2021-07-20
2. (25 points) Dynamic data structures
(a) (4 points) Briefly explain what a queue is and what its two most important methods do.
Also provide the names of these two methods.
(b) (4 points) If we implement a queue as an array-based Python list, what would happen
if we removed the first element by calling pop(0)? Use the O and Θ notations to support
your arguments.
Algorithms and Data Structures Exam - Page 8 of 15 2021-07-20
(c) (2 points) In class, we studied circular arrays in order to efficiently implement queues.
Implement the first method and raise exceptions when needed.
class MyQueue :
DEFAULT CAPACITY = 10
def init (self ):
self. data = [None] ∗ MyQueue . DEFAULT CAPACITY
self. size = 0
self. front = 0
def len (self ):
return self. size
def is empty (self ):
return self. size == 0
def first(self ):
[...]
def dequeue (self ):
if self. is empty ():
raise Empty(’Queue is empty ’)
answer = self. data [self. front ]
self. data [self. front ] = None
self. front = (self. front + 1) % len(self. data )
self. size −= 1
return answer
def enqueue (self , e):
[...]
def resize (self , cap ):
old = self. data
self. data = [None] ∗ cap
walk = self. front
for k in range (self. size ):
self. data [k] = old[walk]
walk = (1 + walk) % len(old)
self. front = 0
Algorithms and Data Structures Exam - Page 9 of 15 2021-07-20
(d) (8 points) Implement the enqueue method. Also provide a visualization to explain how
your method works.
Algorithms and Data Structures Exam - Page 10 of 15 2021-07-20
(e) (4 points) Add exactly one method to class UnsortedTableMap that allows to add or
update a key-value pair. Your method must be easily accessible in the following form:
obj[k] = v.
from collections .abc import MutableMapping
class MapBase ( MutableMapping ):
class Item :
slots = ’ key ’, ’ value ’
def init (self , k, v):
self. key = k
self. value = v
def eq (self , other ):
return self. key == other. key
def ne (self , other ):
return not (self == other)
def lt (self , other ):
return self. key < other. key
class UnsortedTableMap ( MapBase ):
def init (self ):
self. table = []
def getitem (self , k):
for item in self. table :
if k == item. key :
return item. value
raise KeyError (’Key Error {0} ’. format (k))
#Repeated
Algorithms and Data Structures Exam - Page 11 of 15 2021-07-20
(f) (3 points) Draw the 12-entry hash table that results from using the hash function h(i) =
(4i + 5) mod 12, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 and 5, assuming colli-
sions are handled by chaining.
Algorithms and Data Structures Exam - Page 12 of 15 2021-07-20
3. (25 points) Trees
(a) (6 points) You can represent a tree as a list of list, e.g. [[1], [2, 3], [4, [5, 6, [7,
8, [9, [10, 11, 12]]]]]]. Implement a function flatten(tree) that flattens a tree.
The sample tree would then be turned into the following list: [1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12].
(b) (4 points) What are balanced search trees and what are their benefits? Use the O notation
to support your arguments.
Algorithms and Data Structures Exam - Page 13 of 15 2021-07-20
(c) (15 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
attack label using the following data set. Write out intermediate steps and the result.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 cloudy warm normal weak warm change +
#Repeated
Algorithms and Data Structures Exam - Page 14 of 15 2021-07-20
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 cloudy warm normal weak warm change +
Algorithms and Data Structures Exam - Page 15 of 15 2021-07-20
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 cloudy warm normal weak warm change +
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2020-21 Winter Term
Resit Exam
2020-11-30
Time Limit: 90 Minutes Mark:
This exam contains 15 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Algorithms and Data Structures Resit Exam - Page 2 of 15 2020-11-30
1. (25 points) Search, key-value stores and hash tables
(a) (2 points) What is a frontier in the context of search algorithms?
#Repeated
(b) (8 points) In class, we generalized the lowest cost search providing the following inter-
face: lowest cost search(start, successors, is goal, action cost). Briefly de-
scribe the types of these four parameters and what they do.
Algorithms and Data Structures Resit Exam - Page 3 of 15 2020-11-30
(c) (5 points) Below you find the implementation of shortest path search. Explain why
frontier being a Python list makes this implementation unnecessarily slow. Which data
structure would you use instead? Use the O and Θ notations to support your argument.
01: def shortest path search (start , successors , is goal ):
02: ”””Find the shortest path from start state to a state”””
03: ”””such that is goal ( state ) is true .”””
04: if is goal (start ):
05: return [start]
06: explored = set ([ start ]) # set of states we have visited
07: frontier = [ [start] ] # ordered l i s t of paths we have blazed
08: while frontier :
09: path = frontier .pop (0)
10: s = path[−1]
11: for (state , action ) in successors (s). items ():
12: if state not in explored :
13: explored .add(state)
14: path2 = path + [action , state]
15: if is goal (state ):
16: return path2
17: else:
18: frontier . append (path2)
19: return Fail
20: Fail = []
#Repeated
Algorithms and Data Structures Resit Exam - Page 4 of 15 2020-11-30
(d) (3 points) Provide a more efficient implementation using the different data structure. You
only need to rewrite a few lines. Clearly reference which lines you are rewriting. You
can omit any imports. For accessing or modifying the different data structure, use the
corresponding ADT’s methods discussed in class.
Repeated
Algorithms and Data Structures Resit Exam - Page 5 of 15 2020-11-30
(e) (4 points) Add exactly one method to class UnsortedTableMap that allows to add or
update a key-value pair. Your method must be easily accessible in the following form:
obj[k] = v.
from collections .abc import MutableMapping
class MapBase ( MutableMapping ):
class Item :
slots = ’ key ’, ’ value ’
def init (self , k, v):
self. key = k
self. value = v
def eq (self , other ):
return self. key == other. key
def ne (self , other ):
return not (self == other)
def lt (self , other ):
return self. key < other. key
class UnsortedTableMap ( MapBase ):
def init (self ):
self. table = []
def getitem (self , k):
for item in self. table :
if k == item. key :
return item. value
raise KeyError (’Key Error {0} ’. format (k))
#Repeated
Algorithms and Data Structures Resit Exam - Page 6 of 15 2020-11-30
(f) (3 points) Draw the 11-entry hash table that results from using the hash function h(i) =
(3i + 5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16 and 5, assuming colli-
sions are handled by chaining.
#Repeated with minor changings
Algorithms and Data Structures Resit Exam - Page 7 of 15 2020-11-30
2. (25 points) Recursion and dynamic programming
(a) (4 points) We define DIT numbers as following:
1 n ∈ {0, 1, 2, 3, 4}
dit(n) = .
dit(n − 1) + dit(n − 2) + dit(n − 3) + dit(n − 4) + dit(n − 5) n≥5
Implement a naive recursive algorithm in Python.
#repeated with alteration
Algorithms and Data Structures Resit Exam - Page 8 of 15 2020-11-30
(b) (5 points) Derive the worst-case running time complexity of your naive implementation.
#Repeated
Algorithms and Data Structures Resit Exam - Page 9 of 15 2020-11-30
(c) (8 points) Re-implement your algorithm in Python using a top-down dynamic program-
ming approach.
Algorithms and Data Structures Resit Exam - Page 10 of 15 2020-11-30
(d) (8 points) Re-implement your algorithm in Python using a bottom-up dynamic program-
ming approach.
Algorithms and Data Structures Resit Exam - Page 11 of 15 2020-11-30
3. (25 points) Binary search and trees
(a) (7 points) In class, we discussed the recursive implementation of binary search below. Im-
plement an iterative variation of binary search that has the same running time complexity.
def search binary (data , target , low=None , high=None ):
if low == None: low = 0
if high == None: high = len(data) − 1
if low > high:
return False
else:
mid = (low + high) // 2 #Or: mid = low + (high−low) // 2
if target == data[mid ]:
return True
elif target < data[mid ]:
return search binary (data , target , low , mid −1)
else:
return search binary (data , target , mid +1, high)
#Repeated
Algorithms and Data Structures Resit Exam - Page 12 of 15 2020-11-30
(b) (18 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
WillWait label using the following data set. Write out intermediate steps and the result.
You only need to execute the algorithm for one level below the root. Then add as many
leaves to the root as possible. Indicate where subtrees need to be learned.
Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait
x(1) T F F T Some $$$ F T French 0-10 T
x(2) T F F T Full $ F F Thai 30-60 F
x(3) F T F F Some $ F F Burger 0-10 T
x(4) T F T T Full $ T F Thai 30-60 T
x(5) T F T F Full $$$ F T French >60 F
x(6) F T F T Some $$ T T Italian 0-10 T
x(7) F T F F None $ T F Burger 0-10 F
x(8) F F F T Some $$ T T Thai 0-10 T
x(9) F T T F Full $ T F Burger >60 F
x(10) T T T T Full $$$ F T Italian 10-30 F
x(11) F F F F None $ F F Thai 0-10 F
x(12) T T T T Full $ F F Burger 30-60 T
Algorithms and Data Structures Resit Exam - Page 13 of 15 2020-11-30
Continued:
Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait
x(1) T F F T Some $$$ F T French 0-10 T
x(2) T F F T Full $ F F Thai 30-60 F
x(3) F T F F Some $ F F Burger 0-10 T
x(4) T F T T Full $ T F Thai 30-60 T
x(5) T F T F Full $$$ F T French >60 F
x(6) F T F T Some $$ T T Italian 0-10 T
x(7) F T F F None $ T F Burger 0-10 F
x(8) F F F T Some $$ T T Thai 0-10 T
x(9) F T T F Full $ T F Burger >60 F
x(10) T T T T Full $$$ F T Italian 10-30 F
x(11) F F F F None $ F F Thai 0-10 F
x(12) T T T T Full $ F F Burger 30-60 T
Algorithms and Data Structures Resit Exam - Page 14 of 15 2020-11-30
Continued:
Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait
x(1) T F F T Some $$$ F T French 0-10 T
x(2) T F F T Full $ F F Thai 30-60 F
x(3) F T F F Some $ F F Burger 0-10 T
x(4) T F T T Full $ T F Thai 30-60 T
x(5) T F T F Full $$$ F T French >60 F
x(6) F T F T Some $$ T T Italian 0-10 T
x(7) F T F F None $ T F Burger 0-10 F
x(8) F F F T Some $$ T T Thai 0-10 T
x(9) F T T F Full $ T F Burger >60 F
x(10) T T T T Full $$$ F T Italian 10-30 F
x(11) F F F F None $ F F Thai 0-10 F
x(12) T T T T Full $ F F Burger 30-60 T
Algorithms and Data Structures Resit Exam - Page 15 of 15 2020-11-30
Continued:
Alt Bar Fri Hun Pat Price Rain Res Type Est WillWait
x(1) T F F T Some $$$ F T French 0-10 T
x(2) T F F T Full $ F F Thai 30-60 F
x(3) F T F F Some $ F F Burger 0-10 T
x(4) T F T T Full $ T F Thai 30-60 T
x(5) T F T F Full $$$ F T French >60 F
x(6) F T F T Some $$ T T Italian 0-10 T
x(7) F T F F None $ T F Burger 0-10 F
x(8) F F F T Some $$ T T Thai 0-10 T
x(9) F T T F Full $ T F Burger >60 F
x(10) T T T T Full $$$ F T Italian 10-30 F
x(11) F F F F None $ F F Thai 0-10 F
x(12) T T T T Full $ F F Burger 30-60 T
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2020 Summer Term
Sample Exam
2020-07-XX
Time Limit: 90 Minutes Mark:
This exam contains 15 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Note: This sample exam does not cover all top-
ics discussed towards the end of the term. The
content of the entire course will be relevant for
the final exam.
Algorithms and Data Structures Sample Exam - Page 2 of 15 2020-07-XX
1. (25 points) Graphs and lists
(a) (5 points) Provide a formal k-tuple definition of the following graph G:
#Repeated
Algorithms and Data Structures Sample Exam - Page 3 of 15 2020-07-XX
(b) (2 points) What is a frontier in the context of search algorithms?
#Repeated
(c) (6 points) In class, we generalized the shortest path search providing the following inter-
face: shortest path search(start, successors, is goal). Briefly describe the types
of these three parameters and what they do.
#Repeated
Algorithms and Data Structures Sample Exam - Page 4 of 15 2020-07-XX
(d) (5 points) Below you find the implementation of shortest path search. Explain why
frontier being a Python list makes this implementation unnecessarily slow. Which data
structure would you use instead? Use the O and Θ notations to support your argument.
01: def shortest path search (start , successors , is goal ):
02: ”””Find the shortest path from start state to a state”””
03: ”””such that is goal ( state ) is true .”””
04: if is goal (start ):
05: return [start]
06: explored = set ([ start ]) # set of states we have visited
07: frontier = [ [start] ] # ordered l i s t of paths we have blazed
08: while frontier :
09: path = frontier .pop (0)
10: s = path[−1]
11: for (state , action ) in successors (s). items ():
12: if state not in explored :
13: explored .add(state)
14: path2 = path + [action , state]
15: if is goal (state ):
16: return path2
17: else:
18: frontier . append (path2)
19: return Fail
20: Fail = []
#Repeated
Algorithms and Data Structures Sample Exam - Page 5 of 15 2020-07-XX
(e) (3 points) Provide a more efficient implementation using the different data structure. You
only need to rewrite a few lines. Clearly reference which lines you are rewriting. You
can omit any imports. For accessing or modifying the different data structure, use the
corresponding ADT’s methods discussed in class.
#Repeated
Algorithms and Data Structures Sample Exam - Page 6 of 15 2020-07-XX
(f) (4 points) In class, we discussed the MyArray class. Implement the setitem (self,
k, value) method. It must also be able to handle negative indices.
import ctypes
class MyArray :
def init (self ):
self. n = 0
self. capacity = 1
self. A = self. make array (self. capacity )
def len (self ):
return self. n
def getitem (self , k):
[...]
def append (self , obj ):
[...]
def resize (self , c):
[...]
def make array (self , c):
return (c ∗ ctypes . py object )()
#Repeat
Algorithms and Data Structures Sample Exam - Page 7 of 15 2020-07-XX
2. (25 points) Recursion and dynamic programming
(a) (4 points) We define Deggendorf numbers as following:
1 n ∈ {0, 1, 2}
deg(n) = .
deg(n − 1) + deg(n − 2) + deg(n − 3) n≥3
Implement a naive recursive algorithm in Python.
#Rept
Algorithms and Data Structures Sample Exam - Page 8 of 15 2020-07-XX
(b) (5 points) Derive the worst-case running time complexity of your naive implementation.
#Rept
Algorithms and Data Structures Sample Exam - Page 9 of 15 2020-07-XX
(c) (8 points) Re-implement your algorithm in Python using a top-down dynamic program-
ming approach.
Rept
Algorithms and Data Structures Sample Exam - Page 10 of 15 2020-07-XX
(d) (8 points) Re-implement your algorithm in Python using a bottom-up dynamic program-
ming approach.
Algorithms and Data Structures Sample Exam - Page 11 of 15 2020-07-XX
3. (25 points) Binary search and trees
(a) (7 points) In class, we discussed the recursive implementation of binary search below. Im-
plement an iterative variation of binary search that has the same running time complexity.
def search binary (data , target , low=None , high=None ):
if low == None: low = 0
if high == None: high = len(data) − 1
if low > high:
return False
else:
mid = (low + high) // 2 #Or: mid = low + (high−low) // 2
if target == data[mid ]:
return True
elif target < data[mid ]:
return search binary (data , target , low , mid −1)
else:
return search binary (data , target , mid +1, high)
#Repeated
Algorithms and Data Structures Sample Exam - Page 12 of 15 2020-07-XX
Continued:
(b) (3 points) Provide the space complexity for both algorithms including a short justification.
Which of them is in-place?
Algorithms and Data Structures Sample Exam - Page 13 of 15 2020-07-XX
(c) (15 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
attack label using the following data set. Write out intermediate steps and the result.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
#Repeated
Algorithms and Data Structures Sample Exam - Page 14 of 15 2020-07-XX
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
#Repeated
Algorithms and Data Structures Sample Exam - Page 15 of 15 2020-07-XX
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy cold high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
6 rainy warm high strong warm change -
Deggendorf Institute of Technology Student ID:
Department of Applied Computer Science
Algorithms and Data Structures Seat Number:
Professor Patrick GLAUNER
2020 Summer Term
Exam
2020-07-30
Time Limit: 90 Minutes Mark:
This exam contains 15 pages (including this cover page) and 3 problems. Answer 2 problems. If
you answer 3 problems, the best 2 count. Check to see if any pages are missing. Enter all requested
information on the top of this page, and put your seat number on the top of every page, in case
the pages become separated.
You may only use a non-CAS calculator and a one-sided handwritten A4 notes sheet in this exam.
The following rules apply:
• If you use a “fundamental theorem” you
Problem Points Score
must indicate this and explain why the theorem
may be applied.
1 25
• Organize your work, in a reasonably neat and
coherent way, in the space provided. Work scat- 2 25
tered all over the page without a clear ordering
will receive very little credit. 3 25
• Mysterious or unsupported answers will not Total: 50
receive full credit. A correct answer, unsup-
ported by calculations, explanation, or algebraic
work will receive no credit; an incorrect answer
supported by substantially correct calculations and
explanations might still receive partial credit.
• If you need more space, use the back of the pages;
clearly indicate when you have done this.
Do not write in the table to the right.
Algorithms and Data Structures Exam - Page 2 of 15 2020-07-30
1. (25 points) Graphs, binary exponentiation and dynamic data structures
(a) (5 points) Provide a formal k-tuple definition of the following graph G:
Algorithms and Data Structures Exam - Page 3 of 15 2020-07-30
(b) (4 points) A trivial recursive definition of the power function follows from the fact that
xn = x × xn−1 for n > 0:
1 n=0
power(x, n) = .
x × power(x, n − 1) otherwise
Implement this function in Python using recursion.
#Repeated
(c) (1 point) Provide the running time complexity of your function.
Algorithms and Data Structures Exam - Page 4 of 15 2020-07-30
(d) (5 points) There is a much faster way to compute the power function using an alternative
definition that employs a squaring technique:
1 n=0
power(x, n) = power(x, n2 )2 if n > 0 is even .
x × power(x, n2 )2 if n > 0 is odd
Let n2 denote the floor of the division (expressed as n // 2 in Python). Implement this
function in Python using recursion.
Algorithms and Data Structures Exam - Page 5 of 15 2020-07-30
(e) (5 points) Derive the worst-case running time complexity of your efficient implementation.
Algorithms and Data Structures Exam - Page 6 of 15 2020-07-30
(f) (5 points) In class, we discussed the MyArray class. Implement the insert(self, k,
value) method. It must only be able to handle indices 0 or greater, not negative indices.
import ctypes
class MyArray :
def init (self ):
self. n = 0
self. capacity = 1
self. A = self. make array (self. capacity )
def len (self ):
return self. n
def getitem (self , k):
[...]
def append (self , obj ):
[...]
def resize (self , c):
[...]
def make array (self , c):
return (c ∗ ctypes . py object )()
Algorithms and Data Structures Exam - Page 7 of 15 2020-07-30
2. (25 points) Recursion and dynamic programming
(a) (4 points) We define Bavarian numbers as following:
1 n ∈ {0, 1, 2, 3}
bav(n) = .
bav(n − 1) + bav(n − 2) + bav(n − 3) + bav(n − 4) n≥4
Implement a naive recursive algorithm in Python.
Algorithms and Data Structures Exam - Page 8 of 15 2020-07-30
(b) (5 points) Derive the worst-case running time complexity of your naive implementation.
Algorithms and Data Structures Exam - Page 9 of 15 2020-07-30
(c) (8 points) Re-implement your algorithm in Python using a top-down dynamic program-
ming approach.
Algorithms and Data Structures Exam - Page 10 of 15 2020-07-30
(d) (8 points) Re-implement your algorithm in Python using a bottom-up dynamic program-
ming approach.
Algorithms and Data Structures Exam - Page 11 of 15 2020-07-30
3. (25 points) Trees
(a) (7 points) Implement a function invert that inverts a tree. An example is depicted below.
Note that a node may have 0, 1 or 2 children. Use the TreeNode class below.
From to
class TreeNode :
def init (self , val ):
[Link] = val
[Link] = None
[Link] = None
def invert (node ):
[...]
#Repeated
Algorithms and Data Structures Exam - Page 12 of 15 2020-07-30
Continued:
(b) (3 points) Provide the worst-case space complexity of your inversion algorithm, assuming
the tree may not necessarily be balanced. Is your algorithm in-place?
Algorithms and Data Structures Exam - Page 13 of 15 2020-07-30
(c) (15 points) Use the ID3 decision tree learning algorithm in order to learn a tree for the
attack label using the following data set. Write out intermediate steps and the result.
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
#Repeated
Algorithms and Data Structures Exam - Page 14 of 15 2020-07-30
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
Algorithms and Data Structures Exam - Page 15 of 15 2020-07-30
Continued:
sky air humid wind water forecast attack
1 sunny warm normal strong warm same +
2 sunny warm high strong warm same +
3 rainy warm high strong warm change -
4 sunny warm high strong cool change +
5 sunny warm normal weak warm same -
Das könnte Ihnen auch gefallen
- L1 - 4.3 L"sung Vertiefung KapitalrechnerNoch keine BewertungenL1 - 4.3 L"sung Vertiefung Kapitalrechner3 Seiten
- Lösungsvorschlag Zu Tutorienblatt 06Noch keine BewertungenLösungsvorschlag Zu Tutorienblatt 067 Seiten
- Entwurf Und Analyse Von AlgorithmenNoch keine BewertungenEntwurf Und Analyse Von Algorithmen2 Seiten
- Grundlagen Der Algorithmusgestaltung LösungenNoch keine BewertungenGrundlagen Der Algorithmusgestaltung Lösungen111 Seiten
- BTS 2024 Mathematik C1 Korrektur ReluNoch keine BewertungenBTS 2024 Mathematik C1 Korrektur Relu4 Seiten
- Selbsteinschätzung Nr. 1 - Überprüfung Der VersucheNoch keine BewertungenSelbsteinschätzung Nr. 1 - Überprüfung Der Versuche12 Seiten
- Korrektur Der Wettbewerbe 2011 2019Noch keine BewertungenKorrektur Der Wettbewerbe 2011 201936 Seiten
- Verschiedene Fragen Zu VerhältnissenNoch keine BewertungenVerschiedene Fragen Zu Verhältnissen4 Seiten
- Aufgabe Nachtragskalkulation 2 - AusgewogenheitNoch keine BewertungenAufgabe Nachtragskalkulation 2 - Ausgewogenheit1 Seite
- Finanzen I Klausur Mit Loesung WS 2014 (Powered by Raute Wirtschaft)Noch keine BewertungenFinanzen I Klausur Mit Loesung WS 2014 (Powered by Raute Wirtschaft)25 Seiten
- Abiturpruefung Mathematik 2021 Pruefungsteil BNoch keine BewertungenAbiturpruefung Mathematik 2021 Pruefungsteil B12 Seiten
- Jahresplanung Mathematik 1. Jahr SBNoch keine BewertungenJahresplanung Mathematik 1. Jahr SB9 Seiten
- Prüfung Am Ende Der Jahrgangsstufe 10 Mathematik: Allgemeine ArbeitshinweiseNoch keine BewertungenPrüfung Am Ende Der Jahrgangsstufe 10 Mathematik: Allgemeine Arbeitshinweise15 Seiten
- Vorlesung 1 Integration Algebraischer FunktionenNoch keine BewertungenVorlesung 1 Integration Algebraischer Funktionen10 Seiten