Datastructuren Flashcards
INFODS van universiteit Utrecht
Satellite data
The data associated with the keys in an input array for the sorting problem.
Record
A key and satellite date together.
How does insertion sort work with a stack of cards?
Start with an empty left hand and a pile of cards on the table.
Pick up the first card and put it in your left hand.
At every time step, remove one card from the pile on the table and compare it to the right-most card in your left hand. Go from right to left until you find a card that is lower or equal than the card you picked. Insert the card you picked on the right of this card.
What does the insertion sort algorithm take as input?
An array A containing the data and an integer n representing the number of keys.
INSERTION-SORT(A, n)
for i=2 to i=n
…key = A[i]
…j = i-1
…while j>0 and A[j] > key
… … A[j+1] = A[j]
… … j = j-1
…A[j+1] = key
What does the input array A look like at each iteration of the for-loop in insertion sort?
The subarray A[1:i-1] is the sorted ‘left hand’ and the subarray A[i+1:n] is the unsorted ‘pile on the table’.
What three things do you need to prove when using a loop invariant?
- Initialization
- Maintenance
- Termination
How do you prove initialization for a loop invariant?
Prove that the loop invariant is true prior to the first loop.
How do you prove maintenance for a loop invariant?
Prove that, if the loop invariant is true before an iteration, then it will be true before the next iteration.
How do you prove termination for a loop invariant?
Prove that the loop terminates, and that the loop invariant gives a useful property when the loop terminates.
In a loop of ‘for i=2 to i=n’, what is the value of ‘i’ when the loop terminates?
i = n+1
Wat is het verschil tussen databases en datastructuren?
Bij databases bemoei je je niet met details van opslag, maar stop je vragn ‘aan de data’ in de SQL-query. Bij datastructuren probeer je beste organisatie van je data te vinden terwijl je rekening houdt met vragen die je gaat stellen.
Wat zijn de kosten van operaties in een ongesorteerde rij?
Toevoegen is makkelijk, O(1).
Zoeken is makkelijk maar tijdrovend, want je moet het query-element vergelijken met elk element, O(n).
Enumeratie
Een bepaalde handeling met elk element doen.
Wat zijn de kosten van toevoegen en zoeken in een gesorteerde rij?
Toevoegen is duur, want alles wat groter is dan x moet 1 plek opschuiven en dan moet je x daaronder invoegen, O(n). Zoeken kan snel, je kunt stoppen als je een el >x ziet.
Wat zijn de 4 componenten van een loop?
- Initialisatie
- Conditie
- Body
- Terminatie
Wat is de rekentijd van Binair zoeken?
O(lg n), logaritmisch.
Hoe bewijs je een statement ‘A=B’ met inductie?
Herschrijf één kant stapsgewijs. Zet per stap de motivatie tussen {accolades}.
Hoe bewijs je een eigenschap ‘voor alle natuurlijke getallen’ met inductie?
- Neem n=0 en bewijs dat LHS en RHS tot hetzelfde herleid worden.
- Neem aan dat P(n) is waar en bewijs dat als P(n), dan P(n+1).
Wat zijn de onderdelen van de inductiestap ‘Als P(n), dan P(n+1) bewijzen?
- Isoleer de LHS van de inductiehypothese in de LHS van het ‘te bewijzen’.
- Vervang binnen de expressie de LHS door de RHS van de inductiehypothese.
- Werk naar de RHS van het ‘te bewijzen’ toe.
What is the worst-case running time of Quicksort?
THETA(n^2)
What is the expected running time of Quicksort if all elements are distinct?
O(n lg n)
What are the three steps in the divide-and-conquer method?
- Divide an array A[p:r] in A[p : q-1] and A[q+1 : r]. The pivot is q.
- Call the algorithm recursively to each subarray.
- Combine the subarrays into A.
QUICKSORT(A, p, r)
if (p<r)
{ q = PARTITION(A,p,r);
QUICKSORT(A,p,q-1);
QUICKSORT(A, q+1, r);
}
PARTITION(A,p,r)
x = A[r];
i = p-1;
for(j=p to r-1)
{ if(A[j]<=x)
{ i++;
exchange A[i] with A[j]
}
exchange A[i+1] with A[r]
return i+1;
}
Stabiel (algoritme)
Een sorteeralgoritme waarbij records met gelijke keys in dezelfde volgorde blijven staan.
Comparison sort algoritme
Een sorteeralgoritme dat elementen verplaatst op basis van onderling vergelijken.
Is insertion sort stabiel?
Ja, als je stopt bij een key die gelijk is aan x en niet <x.
Wat is de complexiteit van insertion sort?
O(n^2)
Wanneer kun je insertion sort wél gebruiken?
Bij een array met ong. max. 20 keys, of als de keys al ongeveer op volgorde staan.
Wat is de invariant van selection sort?
Na i ronden bevat A[0 : i-1] de kleinste keys in oplopende volgorde.
Wat is de variant in Quicksort?
(s-r), de omvang van het onbekende stuk.
In welke drie groepen worden termen verdeeld bij de analyse van algoritmen?
- Exponentieel
- Polynomiaal
- Logaritmisch
Exponentieel
Met n in de exponent. De term met het hogere grondtal is leidend.
Polynomiaal
Een macht van n, de term met de hogere exponent is leidend.
Logaritmisch
Een macht van lg n. Grondtal maakt niet uit, een macht van n binnen de lg ook niet. Een macht van de log maakt wel uit.
Asymptotic efficiency
How the running time of an algorithm increases with the size of the input in the limit.
O-notation (informal)
Characterizes an upper bound on the asymptotic behavior of a function.
Ω-notation
Characterizes a lower bound on the asymptotic behavior of a function
Ω-notation (formal)
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0<=cg(n)<=f(n) for all n>=n0}.
Θ-notation (informal)
Characterizes a tight bound on the asymptotic behavior of a function.
Θ-notation (formal)
Θ(g(n)) = { f(n): there exist positive constants c1, c2 and n0 such that 0<=c1g(n)<=f(n)<=c2g(n) for all n>=n0}
O-notation (formal)
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0<=f(n)<=cg(n) for all n>=n0}
[theorem] For any two functions f(n) and g(n), we have f(n) = Θ(g(n)) if and only if…
f(n) = O(g(n)) and f(n) = Ω(g(n))
