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))
What does it mean if the asymptotic notation appears on the left-hand side of an equation?
No matter how the anonymous functions are chosen on the left of the euqual sign, there is a way to choose the anonymous functions on the right side of the equal sign to make the equation valid.
What is o-notation used for?
To characterize an upper bound that is not asymptotically tight.
o-notation (formal)
o(g(n)) = { f(n): for any positive constant c>0, there exists a constant n0>0 such that 0<=f(n)<cg(n) for all n>=n0}.
ω-notation (formal)
ω(g(n)) = { f(n): for any positive c>0, there exists a constant n0>0 such that 0<=cg(n)< f(n) for all n>=n0}/
Transitivity in asymptotic comparisons
f(n) = ASYMPTOTIC THING(g(n)) and g(n) = SAME ASYMPTOTIC SIGN(h(n)) imply f(n) = SAME AS. THING(h(n))
Binary logarithm
lg n = log2n
Natural logarithm
ln n = loge(n)
lg^k (n) =
(lg n)^k
What is the running time of any comparison sort for a regular case?
THETA (n lg n)
Full binary tree
A tree in which each node is either a leaf or has both children
Decision tree
A full binary tree in which each internal node indicates a comparison. The length of the longest simple path from the root to any leaf is the worst-case number of comparisons.
A binary tree of height h has no more than … leaves.
2^h
What does counting sort do?
It determines for each input element the number of elements less than or equal to hat element and places the element in the correct position in the output array.
COUNTING-SORT(array A, int n, int k)
Make new arrays B[1:n] and C[0:k];
for i=0 to k {C[i] =0}
for j=1 to n {C[A[j]] ++;}
for i = 1 to k {C[i] = C[i] + C[i-1]}
for j=n downto 1 {B[ C[A[j]]] = A[j]; C[A[j]]–;}
return B
Is counting sort stable?
yes
RADIX-SORT(array A, int n, int d)
for i = 1 to d {sort array A[1:n] on digit i with a stable sorting algorithm, usually CS}
What does bucket sort do?
It assumes that the input is drawn from a uniform distribution. Interval [0,1] is divided into n equal-sized subintervals and n input numbers distributed in the buckets. Sorts each bucket and then adds together.
What is the average running time of bucket sort?
O(n)
BUCKET-SORT(array A, int n)
Make new array B[0:n-1]
for i=0 to n-1 {make B[i] empty list;}
for i =1 to n {insert A[i] into list B[FLOOR(n*A[i]-1];}
for i =0 to n-1 {sort list B[i] with insertion sort;}
concatenate lists
return concatenated list
Wat voor aanpassing doe je als je counting sort voor letters ipv ints gebruikt?
C[A[i] - ‘letter’] ++; ipv C[A[i]]++;
Welke sorteeralgoritmes sorteren in-situ?
- Quicksort
- Insertion sort
- Heapsort
welke sorteeralgoritmes sorteren niet in-situ?
- Counting sort
- Bucket sort
- Merge sort
Wat betekent x»_space; 16?
Een bitshift van 16. Geeft 16 nullen + de meest significante (1e) bits van getal x.
Welke twee dingen moet je aantonen bij het bewijzen van ‘elke vorm van comparison sort gebruikt OMEGA(n lg n) vergelijkngen’?
- Een comparison heeft 2 mogelijke uitkomsten
- Het algoritme moet minimaal n! verschillende dingen kunnen doen, want n! verschillende inputvolgorden moeten op een andere manier herschikt worden.
Hoeveel knopen zitten er maximaal op laag V van een tree?
2^V, want elke knoop heeft max 2 knopen onder zich
Recursie
Een ontwerptechniek waarbij je je eigen product vast gebruikt door te doen alsof je kleinere problemen al opgelost hebt.
Hoeveel tijd kost het vermenigvuldigen van n-digit getallen?
Theta(n^2), maar kan ook sneller.
Rekenregel ‘Domeinsplitsing’
Als p<=r<=q, dan geldt SUM(i=p;i=r-1) A[i]
= SUM(i=p;i=r-1) A[i] + SUM(i=r;i=q-1) A[i].
Recurrente betrekking
Definieert de waarde van een functie in termen van de waarde(n) voor kleinere parameter(s). Ook wel de Z-formule.
Hoeveel kost het ritsen van n keys?
Theta (n)
Uit welke twee onderdelen bestaat een recurrente betrekking?
- Randvoorwaarde
- Voortgangsvergelijking
Welke drie dingen zijn onbelangrijk bij het asymptotisch oplossen van een recurrente betrekking?
- De randvoorwaarde
- Afronden bij delen
- Exacte voorwaarden van extra termen
Wat is wél belangrijk bij het asymptotisch oplossen van een recurrente betrekking?
Hoe vaak je in recursie gaat.
Given a sequence a_1 to a_n of numbers, where n is a nonnegative integer, the
finite sum of a_1 to a_n can be expressed as:
SUM (k=1; k=n) a_k
What is the value of a summation for n < start value?
0
What happens if the limit of a summation does not exist?
The series diverges.
What happens if the limit of a summation does exist?
The series converges.
How do you express the arithmetic series 1+2+3+…+n with a formula?
SUM(k=1; k=n) k
= n(n+1) / 2
What is the formula for the sum of squares?
n(n+1)(2n+1)
- - -
6
What is the formula for the sum of cubes?
(n^2)* (n+1)^2
—– ——– ——
4
What is the formula for this series: 1 + x + x^2 + x^3 + … + x^n?
(x^(n+1)) - 1
- - - - -
x-1
What is the harmonic series?
1 + 1/2 + 1/3 + … + 1/n
What does it mean when a sum telescopes?
Each of the terms is added in and subtracted out exactly once.
How do you convert a formula with a product to a formula with a summation?
lg (PRODUCT a_k) = SUM( lg a_k)
Sommatievariabele
De variabele die elke iteratie verandert, is gebonden en heeft buiten de sommatie geen betekenis.
Term-formule
De formule binnen een sommatie die de termwaarde beschrijft afhankelijk van de sommatievariabele.
Rekenkundige rij
Een rij getallen waarbij het verschil van opeenvolgende termen constant is.
Rekenkundige reeks
De sommatie van een rekenkundige rij.
Constant
Niet afhankelijk van de index-variabele.
Meetkundige reeks
Een reeks getallen waarin het quotient van opeenvolgende termen constant is.
Als de eerste term van een meetkundige reeks waarde A heeft en de groeifactor is r, dan is de sommatie:
SOM(i=0, n-1) A * (r^i)
Vuistregel meetkundige reeks
(volgende-eerste) / (groeifactor-1)
SOM(i=0, oneindig) i* (x^i) = … als |x|<1
x / (x-1)^2
Constante factor regel
SOM(i=p, q) C * A_i =
C * SOM(i=p,q) A_i
Constante term regel
SOM(i=p, q) C =
(q-p+1) * C
Leeg domein regel
SOM(i=p, p-1) A_i=
0
Eenpuntsregel
SOM(i=p, p) A_i=
A_p
Termsplitsing regel
SOM(i=p, q) (A_i + B_i) =
SOM(i=p, q) A_i + SOM(i=p, q) B_i
Domeinsplitsing regel
SOM(i=p, q) A_i =
SOM(i=p, r) A_i + SOM(i=r+1, q) A_i
Afsplitsen regel
SOM(i=p, q) A_i =
SOM(i=p, q-1) A_i + A_q
Hernoemen regel
SOM(i=p, q) A_i =
SOM(j=p, 1) A_j
Dummy-transformatie regel
SOM(i=p, q) A_i =
SOM (i=pi(p), pi(q)) A_((pi^-1)*i)
Wat doe je bij dummy-transformatie?
De term die eerst nummer i heeft, geef je nummer pi(i) De eerste en laatste term waren eerst nummer p en q, maar worden pi(p) en pi(q). In de termformule reken je het nieuwe nummer pi(i) eerst terug naar i met pi^-1.
Wat is er bijzonder wanneer de sommatievariabele in de noemer van een breuk staat?
Het is onoplosbaar. Er bestaat geen simpelere uitdrukking voor, dus meot je het harmonisch getal gebruiken.
Harmonisch getal
Hn, is SOM(i=1, n) 1/i
Incremental method
For each element A[i], insert it into its proper place in the subarray A[1:i], having already sorted the subarray A[1:i-1].
When is a recurrence well-defined?
If there is at least one function that satisfies the statement of the recurrence.
Dynamic set
A set that can change over time.
Dictionary
A dynamic set that supports the operations of insertion, deletion or set membership checking.
What two categories of operations on a dynamic set exist?
- Queries
- Modifying operations
Recurrence
An equation that describes a function in terms of its value on other, typically smaller, arguments.
When is a recurrence T(n) algorithmic?
If, for every sufficiently large threshold constant n_0>0,
for all n<n_0, we have T(N) = THETA(1) and
for all n>=n_0, every path of recursion terminates in a defined base case within a finite number of recursive invocations.
What are the four methods described for solving recurrences?
- Substitution
- Recursion-tree
- Master theorem
- Akra-Bazzi
Dense matrix
A matrix where most of the n^2 entries are not 0.
Sparse matrix
A matrix where most of the n^2 entries are 0 and the non-zero entries can be stored more compactly.
The matrix product C = A * B is an nxn matrix, where…
the (i,j)-th entry of C is given by
c_ij = SUM(k=1,n) a_ik * b_kj
MATRIX-MULTIPLY(A, B, C, n)
for(i=1 to n)
{for (j=1 to n)
{for(k=1 to n)
{c_ij = c_ij + a_ik*b_kj}
}
}
What is the running time of MATRIX-MULTIPLY(A, B, C, n)?
THETA(n^3)
MATRIX-MULTIPLY-RECURSIVE(A, B, C, n)
if (n==1) {c_11 = c_11 + a_11*b_11; return;}
Partition A, B and C into n/2 x n/2 matrices.
MMR(A_11, B_11, C_11, n/2);
MMR(A_11, B_12, C_12, n/2);
enz.
What recurrence describes the running time of Strassen’s algorithm?
T(n) = 7T(n/2) + THETA(n^2)
What are the two steps of the substitution method?
- Guess the form of the solution using symbolic constants.
- Use mathematical induction to show that the solution works, and find the constants.
What does a recursion tree node represent?
The cost of a single subproblem somwhere in the set of recursive function invocations.
Driving function
f(n) in the recurrence form of the master theorem, it encompasses the cost of dividing the problem before recursion
1st case of the master theorem
If there exists a constant epsilon>0 such that f(n) = O(n^(logb(a-epsilon)), then T(n) = THETA(n^(logb(a)).
2nd case of the master theorem
If there exists a constant k>=0 such that f(n) = THETA(n^(log_b(a)) * lg^k(n)), then T(n) = THETA(n^log_b(a) * lg^(k+1) * n).
3rd case of the master theorem
If there exists a constant epsilon>0 such that f(n) = OMEGA(n^log_b(a+epsilon)), and if f(n) satisfies the regularity condition af(n/b) <= cf(n) for some constant c<1 and all sufficiently large n, then T(n) = THETA(f(n)).
Watershed function
n^log_b(a) in the master theorem. THe comparison between this function and the driving function f(n) determines the case of the master theorem
lg(n^2) ==
2lg(n)
2lg(n) ==
lg(n^2)
lg(n) ==
in termen van 10
lg(10) * 10log(n)
Waarom is max(f(n), g(n)) = OMEGA(f(n) + g(n))?
Max(f(n), g(n)) is minstens de helft van f(n)+g(n), dus max(f(n), g(n)) >= 1/2(f(n) + g(n)) en dat is de definitie van OMEGA(), namelijk f(n) >= cg(n) met c=1/2.
Θ(lg n) = Θ(10log n), is dit waar of onwaar?
Waar, want logaritmen met verschillende grondtallen verschillen maar een constante factor en zijn dus dezelfde orde van grootte.
lg(n!) = THETA(…)
THETA(n lg n)
lg( (n^2)!) = THETA(…)
THETA(n^2 lg (n^2)) = THETA (n^2lg(n))
Wat is de complexiteit van bucket sort als de keys uniform verdeeld zijn?
THETA(n)
Abstracte datastructuur
Een soort interface: benoemt wat de datastructuur kan & liefst ook wat de complexiteit per methode is.
Fysieke datastructuur
Zegt hoe de datastructuur werkt, beschrijft memory en methoden.
Statische datastructuur
Vaste omvang en directe toegang
Dynamische datastructuur
Flexibele omvang en plaatsing, indirecte toegang.
Hoe zijn objecten opgeslagen in een dynamische datastructuur?
Ze bevatten inhoud en een verwijzing naar de volgende.
Wat is de prestatie van de operaties van List?
Efficiente Add en Enumeratie en dure Remove en directe toegang.
Wat is de complexiteit van methodes op Dictionary<Key, Value>?
O(1) voor Add, Remove en Contains.
Bij een 0-based array die begint op geheugenplek a met elementen van b bytes, welke bytes worden in beslag genomen door element i?
Bytes a+b(i-s) tot a+b(i-s+1)-1
How is an m x n matrix stored in row-major order?
By row. In a one-dimensional array: first half of the entries are the upper row, second half of the entries the lower row for a matrix with two rows.
How is an m x n matrix stored in column-major order?
By column, in a one-dimensional array with the first numbers the first column etc.
How do you find element M[i,j] in matrix M when it is stored in a row-major one-dimensional array?
It’s at array index s+(n(i-s)) + (j-s)
With s= the start index of the matrix.
How do you find element M[i,j] in matrix M when it is stored in a row-major one-dimensional array?
It’s at array index s+(n(i-s)) + (j-s)
With s= the start index of the matrix.
How do you find element M[i,j] in matrix M when it is stored in a column-major one-dimensional array?
Index at s+(m(j-s)) + (i-s).
When s=0, how do you find the index of element M[i,j] in a single-array?
ni+j for row-major and i+mj for column-major.
Block representation
A way of storing matrixes in which the matrix is divided into blocks and each block is stored contiguously.
What are the basic operations on a stack?
Push and pop
What attributes does a stack have?
S.top is the most recently inserted element and S.size is the size of the array.
When is a stack empty?
When S.top= 0.
When does a stack underflow?
Upon an attempt to pop an empty stack.
When does a stack overflow?
If S.top exceeds S.size.
How much time do STACK-EMPTY, PUSH and POP take?
O(1)
STACK-EMPTY(S)
If S.top ==0 {return true}
Else {return false}
PUSH(S,x)
If S.top== S.size {error ‘overflow’}
Else {S.top= S.top +1;
S[S.top] = x}
POP(S)
If STACK-EMPTY(S) {error ‘underflow’}
Else { S.top = S.top -1;
Return S[S.top+1]}
What basic operations does a queue have?
Enqueue and dequeue
What attributes does a queue have?
Head and tail and Q.size
When is a queue empty?
When Q.head== Q.tail
When is the queue full?
When Q.head=Q.tail +1
Or
Both Q.head =1 and Q.tail = Q.size
Linked List
Data structure in which the objects are arranged in a linear order.
What are linked lists sometimes also called?
Search lists
How is the order in a linked list determined?
By a pointer in each object
Element of doubly linked list L
An object with an attribute ‘key’and two pointer attributes: ‘next’ and ‘prev’. May also contain satellite data.
When is an element the first element in a linked list?
When x.prev =NIL.
When is an element the last element in a linked list?
If x.next = NIL.
When is a linked list empty?
If L.head = NIL.
What three parameters describe a linked list?
- Singly/doubly linked
- Sorted or not
- Circular or not
Singly linked linked list
Linked list in which each element has a next pointer but no prev pointer.
Sorted linked list
A linked list in which the linear order of the list corresponds to the linear order of keys stored in elements of the list. Minimum element is head of ht elist and maximum element is the tail.
Circular linked list
A linked list in which the prev pointer of the head of the list points to the tail and the next pointer of the tail of the list points to the head.
How much time does LIST-SEARCH take?
THETA(n) in the worst case, since it may have to search the entire list.
What does LIST-PREPEND do?
It adds element x to the front of the linked list.
