Datastructuren Flashcards
INFODS van universiteit Utrecht (450 cards)
1
Q
Satellite data
A
The data associated with the keys in an input array for the sorting problem.
2
Q
Record
A
A key and satellite date together.
3
Q
How does insertion sort work with a stack of cards?
A
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.
4
Q
What does the insertion sort algorithm take as input?
A
An array A containing the data and an integer n representing the number of keys.
5
Q
INSERTION-SORT(A, n)
A
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
6
Q
What does the input array A look like at each iteration of the for-loop in insertion sort?
A
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’.
7
Q
What three things do you need to prove when using a loop invariant?
A
- Initialization
- Maintenance
- Termination
8
Q
How do you prove initialization for a loop invariant?
A
Prove that the loop invariant is true prior to the first loop.
9
Q
How do you prove maintenance for a loop invariant?
A
Prove that, if the loop invariant is true before an iteration, then it will be true before the next iteration.
10
Q
How do you prove termination for a loop invariant?
A
Prove that the loop terminates, and that the loop invariant gives a useful property when the loop terminates.
11
Q
In a loop of ‘for i=2 to i=n’, what is the value of ‘i’ when the loop terminates?
A
i = n+1
12
Q
Wat is het verschil tussen databases en datastructuren?
A
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.
13
Q
Wat zijn de kosten van operaties in een ongesorteerde rij?
A
Toevoegen is makkelijk, O(1).
Zoeken is makkelijk maar tijdrovend, want je moet het query-element vergelijken met elk element, O(n).
14
Q
Enumeratie
A
Een bepaalde handeling met elk element doen.
15
Q
Wat zijn de kosten van toevoegen en zoeken in een gesorteerde rij?
A
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.
16
Q
Wat zijn de 4 componenten van een loop?
A
- Initialisatie
- Conditie
- Body
- Terminatie
17
Q
Wat is de rekentijd van Binair zoeken?
A
O(lg n), logaritmisch.
18
Q
Hoe bewijs je een statement ‘A=B’ met inductie?
A
Herschrijf één kant stapsgewijs. Zet per stap de motivatie tussen {accolades}.
19
Q
Hoe bewijs je een eigenschap ‘voor alle natuurlijke getallen’ met inductie?
A
- 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).
20
Q
Wat zijn de onderdelen van de inductiestap ‘Als P(n), dan P(n+1) bewijzen?
A
- 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.
21
Q
What is the worst-case running time of Quicksort?
A
THETA(n^2)
22
Q
What is the expected running time of Quicksort if all elements are distinct?
A
O(n lg n)
23
Q
What are the three steps in the divide-and-conquer method?
A
- 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.
24
Q
QUICKSORT(A, p, r)
A
if (p<r)
{ q = PARTITION(A,p,r);
QUICKSORT(A,p,q-1);
QUICKSORT(A, q+1, r);
}
25
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;
}
26
Stabiel (algoritme)
Een sorteeralgoritme waarbij records met gelijke keys in dezelfde volgorde blijven staan.
27
Comparison sort algoritme
Een sorteeralgoritme dat elementen verplaatst op basis van onderling vergelijken.
28
Is insertion sort stabiel?
Ja, als je stopt bij een key die gelijk is aan x en niet
29
Wat is de complexiteit van insertion sort?
O(n^2)
30
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.
31
Wat is de invariant van selection sort?
Na i ronden bevat A[0 : i-1] de kleinste keys in oplopende volgorde.
32
Wat is de variant in Quicksort?
(s-r), de omvang van het onbekende stuk.
33
In welke drie groepen worden termen verdeeld bij de analyse van algoritmen?
1. Exponentieel
2. Polynomiaal
3. Logaritmisch
34
Exponentieel
Met n in de exponent. De term met het hogere grondtal is leidend.
35
Polynomiaal
Een macht van n, de term met de hogere exponent is leidend.
36
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.
37
Asymptotic efficiency
How the running time of an algorithm increases with the size of the input in the limit.
38
O-notation (informal)
Characterizes an upper bound on the asymptotic behavior of a function.
39
Ω-notation
Characterizes a lower bound on the asymptotic behavior of a function
40
Ω-notation (formal)
Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0<=cg(n)<=f(n) for all n>=n0}.
41
Θ-notation (informal)
Characterizes a tight bound on the asymptotic behavior of a function.
42
Θ-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}
43
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}
44
[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))
45
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.
46
What is o-notation used for?
To characterize an upper bound that is not asymptotically tight.
47
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)=n0}.
48
ω-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}/
49
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))
50
Binary logarithm
lg n = log2n
51
Natural logarithm
ln n = loge(n)
52
lg^k (n) =
(lg n)^k
53
What is the running time of any comparison sort for a regular case?
THETA (n lg n)
54
Full binary tree
A tree in which each node is either a leaf or has both children
55
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.
56
A binary tree of height h has no more than ... leaves.
2^h
57
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.
58
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
59
Is counting sort stable?
yes
60
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}
61
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.
62
What is the average running time of bucket sort?
O(n)
63
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
64
Wat voor aanpassing doe je als je counting sort voor letters ipv ints gebruikt?
C[A[i] - 'letter'] ++; ipv C[A[i]]++;
65
Welke sorteeralgoritmes sorteren in-situ?
1. Quicksort
2. Insertion sort
3. Heapsort
66
welke sorteeralgoritmes sorteren niet in-situ?
1. Counting sort
2. Bucket sort
3. Merge sort
67
Wat betekent x >> 16?
Een bitshift van 16. Geeft 16 nullen + de meest significante (1e) bits van getal x.
68
Welke twee dingen moet je aantonen bij het bewijzen van 'elke vorm van comparison sort gebruikt OMEGA(n lg n) vergelijkngen'?
1. Een comparison heeft 2 mogelijke uitkomsten
2. Het algoritme moet minimaal n! verschillende dingen kunnen doen, want n! verschillende inputvolgorden moeten op een andere manier herschikt worden.
69
Hoeveel knopen zitten er maximaal op laag V van een tree?
2^V, want elke knoop heeft max 2 knopen onder zich
70
Recursie
Een ontwerptechniek waarbij je je eigen product vast gebruikt door te doen alsof je kleinere problemen al opgelost hebt.
71
Hoeveel tijd kost het vermenigvuldigen van n-digit getallen?
Theta(n^2), maar kan ook sneller.
72
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].
73
Recurrente betrekking
Definieert de waarde van een functie in termen van de waarde(n) voor kleinere parameter(s). Ook wel de Z-formule.
74
Hoeveel kost het ritsen van n keys?
Theta (n)
75
Uit welke twee onderdelen bestaat een recurrente betrekking?
1. Randvoorwaarde
2. Voortgangsvergelijking
76
Welke drie dingen zijn onbelangrijk bij het asymptotisch oplossen van een recurrente betrekking?
1. De randvoorwaarde
2. Afronden bij delen
3. Exacte voorwaarden van extra termen
77
Wat is wél belangrijk bij het asymptotisch oplossen van een recurrente betrekking?
Hoe vaak je in recursie gaat.
78
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
79
What is the value of a summation for n < start value?
0
80
What happens if the limit of a summation does not exist?
The series diverges.
81
What happens if the limit of a summation does exist?
The series converges.
82
How do you express the arithmetic series 1+2+3+...+n with a formula?
SUM(k=1; k=n) k
= n(n+1) / 2
83
What is the formula for the sum of squares?
n(n+1)(2n+1)
- - -
6
84
What is the formula for the sum of cubes?
(n^2)* (n+1)^2
----- -------- ------
4
85
What is the formula for this series: 1 + x + x^2 + x^3 + ... + x^n?
(x^(n+1)) - 1
- - - - -
x-1
86
What is the harmonic series?
1 + 1/2 + 1/3 + ... + 1/n
87
What does it mean when a sum telescopes?
Each of the terms is added in and subtracted out exactly once.
88
How do you convert a formula with a product to a formula with a summation?
lg (PRODUCT a_k) = SUM( lg a_k)
89
Sommatievariabele
De variabele die elke iteratie verandert, is gebonden en heeft buiten de sommatie geen betekenis.
90
Term-formule
De formule binnen een sommatie die de termwaarde beschrijft afhankelijk van de sommatievariabele.
91
Rekenkundige rij
Een rij getallen waarbij het verschil van opeenvolgende termen constant is.
92
Rekenkundige reeks
De sommatie van een rekenkundige rij.
93
Constant
Niet afhankelijk van de index-variabele.
94
Meetkundige reeks
Een reeks getallen waarin het quotient van opeenvolgende termen constant is.
95
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)
96
Vuistregel meetkundige reeks
(volgende-eerste) / (groeifactor-1)
97
SOM(i=0, oneindig) i* (x^i) = ... als |x|<1
x / (x-1)^2
98
Constante factor regel
SOM(i=p, q) C * A_i =
C * SOM(i=p,q) A_i
99
Constante term regel
SOM(i=p, q) C =
(q-p+1) * C
100
Leeg domein regel
SOM(i=p, p-1) A_i=
0
101
Eenpuntsregel
SOM(i=p, p) A_i=
A_p
102
Termsplitsing regel
SOM(i=p, q) (A_i + B_i) =
SOM(i=p, q) A_i + SOM(i=p, q) B_i
103
Domeinsplitsing regel
SOM(i=p, q) A_i =
SOM(i=p, r) A_i + SOM(i=r+1, q) A_i
104
Afsplitsen regel
SOM(i=p, q) A_i =
SOM(i=p, q-1) A_i + A_q
105
Hernoemen regel
SOM(i=p, q) A_i =
SOM(j=p, 1) A_j
106
Dummy-transformatie regel
SOM(i=p, q) A_i =
SOM (i=pi(p), pi(q)) A_((pi^-1)*i)
107
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.
108
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.
109
Harmonisch getal
Hn, is SOM(i=1, n) 1/i
110
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].
111
When is a recurrence well-defined?
If there is at least one function that satisfies the statement of the recurrence.
112
Dynamic set
A set that can change over time.
113
Dictionary
A dynamic set that supports the operations of insertion, deletion or set membership checking.
114
What two categories of operations on a dynamic set exist?
1. Queries
2. Modifying operations
115
Recurrence
An equation that describes a function in terms of its value on other, typically smaller, arguments.
116
When is a recurrence T(n) algorithmic?
If, for every sufficiently large threshold constant n_0>0,
for all n=n_0, every path of recursion terminates in a defined base case within a finite number of recursive invocations.
117
What are the four methods described for solving recurrences?
1. Substitution
2. Recursion-tree
3. Master theorem
4. Akra-Bazzi
118
Dense matrix
A matrix where most of the n^2 entries are not 0.
119
Sparse matrix
A matrix where most of the n^2 entries are 0 and the non-zero entries can be stored more compactly.
120
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
121
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}
}
}
122
What is the running time of MATRIX-MULTIPLY(A, B, C, n)?
THETA(n^3)
123
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.
124
What recurrence describes the running time of Strassen's algorithm?
T(n) = 7T(n/2) + THETA(n^2)
125
What are the two steps of the substitution method?
1. Guess the form of the solution using symbolic constants.
2. Use mathematical induction to show that the solution works, and find the constants.
126
What does a recursion tree node represent?
The cost of a single subproblem somwhere in the set of recursive function invocations.
127
Driving function
f(n) in the recurrence form of the master theorem, it encompasses the cost of dividing the problem before recursion
128
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)).
129
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).
130
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 a*f(n/b) <= c*f(n) for some constant c<1 and all sufficiently large n, then T(n) = THETA(f(n)).
131
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
132
lg(n^2) ==
2lg(n)
133
2lg(n) ==
lg(n^2)
134
lg(n) ==
in termen van 10
lg(10) * 10log(n)
135
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.
136
Θ(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.
137
lg(n!) = THETA(...)
THETA(n lg n)
138
lg( (n^2)!) = THETA(...)
THETA(n^2 lg (n^2)) = THETA (n^2lg(n))
139
Wat is de complexiteit van bucket sort als de keys uniform verdeeld zijn?
THETA(n)
140
Abstracte datastructuur
Een soort interface: benoemt wat de datastructuur kan & liefst ook wat de complexiteit per methode is.
141
Fysieke datastructuur
Zegt hoe de datastructuur werkt, beschrijft memory en methoden.
142
Statische datastructuur
Vaste omvang en directe toegang
143
Dynamische datastructuur
Flexibele omvang en plaatsing, indirecte toegang.
144
Hoe zijn objecten opgeslagen in een dynamische datastructuur?
Ze bevatten inhoud en een verwijzing naar de volgende.
145
Wat is de prestatie van de operaties van List?
Efficiente Add en Enumeratie en dure Remove en directe toegang.
146
Wat is de complexiteit van methodes op Dictionary?
O(1) voor Add, Remove en Contains.
147
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
148
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.
149
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.
150
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.
151
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.
152
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).
153
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.
154
Block representation
A way of storing matrixes in which the matrix is divided into blocks and each block is stored contiguously.
155
What are the basic operations on a stack?
Push and pop
156
What attributes does a stack have?
S.top is the most recently inserted element and S.size is the size of the array.
157
When is a stack empty?
When S.top= 0.
158
When does a stack underflow?
Upon an attempt to pop an empty stack.
159
When does a stack overflow?
If S.top exceeds S.size.
160
How much time do STACK-EMPTY, PUSH and POP take?
O(1)
161
STACK-EMPTY(S)
If S.top ==0 {return true}
Else {return false}
162
PUSH(S,x)
If S.top== S.size {error 'overflow'}
Else {S.top= S.top +1;
S[S.top] = x}
163
POP(S)
If STACK-EMPTY(S) {error 'underflow'}
Else { S.top = S.top -1;
Return S[S.top+1]}
164
What basic operations does a queue have?
Enqueue and dequeue
165
What attributes does a queue have?
Head and tail and Q.size
166
When is a queue empty?
When Q.head== Q.tail
167
When is the queue full?
When Q.head=Q.tail +1
Or
Both Q.head =1 and Q.tail = Q.size
168
Linked List
Data structure in which the objects are arranged in a linear order.
169
What are linked lists sometimes also called?
Search lists
170
How is the order in a linked list determined?
By a pointer in each object
171
Element of doubly linked list L
An object with an attribute 'key'and two pointer attributes: 'next' and 'prev'. May also contain satellite data.
172
When is an element the first element in a linked list?
When x.prev =NIL.
173
When is an element the last element in a linked list?
If x.next = NIL.
174
When is a linked list empty?
If L.head = NIL.
175
What three parameters describe a linked list?
1. Singly/doubly linked
2. Sorted or not
3. Circular or not
176
Singly linked linked list
Linked list in which each element has a next pointer but no prev pointer.
177
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.
178
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.
179
How much time does LIST-SEARCH take?
THETA(n) in the worst case, since it may have to search the entire list.
180
What does LIST-PREPEND do?
It adds element x to the front of the linked list.
181
HOw much time does LIST-PREPEND take?
O(1)
182
What does LIST-INSERT do?
It splices a new element x in to the list, immediately following the pointer y to an object in the list. O(1) time.
183
What do you need to do in order to delete an element with a given key from a linked list?
First call LIST-SEARCH to retrieve a pointer to the element. Then call LIST-DELETE.
184
How much time does it take to delete an element with a given key from a linked list?
THETA(n), because LIST-DELETE of O(1) and LIST_SEARCH with THETA(n).
185
Are insertion and deletion faster on doubly linked lsits or on arrays?
On doubly linked lists.
186
Sentinel
A dummy object that allows us to simplify boundary conditions.
187
What is important to remember when working with L.nil as a sentinel in a linked list?
You should never delete the sentinel L.nil unless you are deleiting the entire list.
188
What attributes do elements in a binary tree have?
p (= parent), left and right.
188
When is element x the root of a binary tree?
When x.p = NIL
188
How can you find the root of an entire binary tree T?
By the attribute T.root.
188
When is a binary tree empty?
When T.root = NIL.
188
What is the left-child, right-sibling representation?
A way to represent trees with arbitrary numbers of children using only O(n) space for any n-node rooted tree.
188
What pointers does an element in the left-child, right-sibling representation have?
x.left-child points to the leftmost child of node x and x.right-sibling points to the sibling of x immediately to its right.
188
LIST-SEARCH'(L,k) voor Linked list met sentinel dus
L.nil.key = k
x = L.nil.next
while x.key !=k {x = x.next}
if x==L.nil {return NIL}
else {return x}
188
LIST-INSERT(x,y) for list with sentinel
x.next = y.next
x.prev = y
y.next.prev = x
y.next = x
188
LIST-DELETE(x) for list with sentinel
x.prev.next = x.next
x.next.prev = x.prev
189
LIST-DELETE(L,x)
if x.prev != NIL {x.prev.next = x.next}
else {L.head = x.next}
if x.next != NIL {x.next.prev = x.prev}
189
LIST-INSERT(x,y)
x.next = y.next
x.prev = y
if y.next != NIL {y.next.prev = x}
y.next = x
189
LIST-PREPEND(L,x)
x.next = L.head
x.prev = NIL
if L.head != NIL {L.head.prev =x}
L.head = x
189
LIST-SEARCH(L,k)
x = L.head
while x!= NIL and x.key != k {x=x.next}
return x
189
ENQUEUE(Q,x)
Q[Q.tail] = x
if Q.tail == Q.size {Q.tail =1}
else {Q.tail = Q.tail +1}
189
DEQUEUE(Q)
x = Q[Q.head]
if Q.head == Q.size {Q.head = 1}
else {Q.head = Q.head +1}
return x
190
Waar worden stack en queue voor gebruikt?
Om tijdelijke informatie op te slaan tijdens het uitvoeren van een berekening.
191
Hoveel tijd kost items toevoegen en deleten in een stack of queue?
O(1)
192
Welke methode gebruik je om het bovenste element van een stack te bekijken zonder het te verwijderen?
Top
193
Wat is het geheugengebruik van een stack wnr je em gebruikt voor recursie?
O(recursiediepte)
194
Random variable
A function from a finite or countably infinite sample space S to the real numbers.
195
For a random variable X and a real number x, we define the event X given that x to be ...
{s IN S such that X(s) = x},
so
Pr{X=x} = SUM(s IN S such that X(s) = x) of Pr{s}
196
What is the function describing the probability density function of the random variable X?
f(x) = Pr { X = x}
197
Joint probability density function
f(x,y) = Pr {X = x and Y = y} for X and Y.
198
When do we define two random variables X and Y to be independent?
if for all x and y, the events X =x and Y = y are independent.
Pr { X = x and Y = y} = Pr{X = x} Pr { Y= y}
199
Linearity of expectation
Says that the expectation of the sum of two random variables is the sum of their expectations.
200
When is a function f(x) convex?
If
f(lambda*x + (1-lambda)*y)
<=
lambda*f(x) +(1-lambda)f(y)
for all x and y and for all 0<=lambda<=1
201
Jensen's inequality
When a convex function f(x) is applied to a random variable X,
E[f(X)] >= f(E[X]) provided that the expectations exist and are finite.
202
How do you calculate the variance of a random variable X with mean E[X]?
Var[X] = E[ (X-E[X])^2 ]
=...
= E[X^2] - (E^2)[X]
203
How do we denote the variance of X?
sigma^2
204
Bernoulli trial
An experiment with only two possible outcomes: success with probability p and failur with probability q=1-p.
205
What do we mean when we speak of Bernoulli trials collectively?
The trials are mutually independent and each has the same probability p for succes.
206
What two important distributions arise from Bernoulli trials?
1. Geometric distribution
2. Binomial distribution
207
Geometric distribution
A probability distribution satisfying the equation
Pr{X = k} = (q^(k-1)) * p
208
How do you calculate how many trials occur before a success for a sequence of Bernoulli trials?
Define the random variable X to be the number of trials needed.
X has values in range {1, 2, ...} and for k>=1,
Pr{X=k} = ((q^(k-1)) * p since k-1 failures occur before the first success.
Assume q<1, then E[X] = 1/p. So 1/p trials necessary before success ocurs.
209
Binomial distribution
A probability distribution satisfying the equation
Pr{X=k} = (n over k) * (p^k) * (q^(n-k)).
210
How many successes occur during n Bernoulli trials where a success occurs with probability p and failure with probability 1=1-p?
Since there are (n over k ) ways to pick which k of the n trials are successes, probability of each is (p^k) * (q^(n-k)).
n* p
211
Counting theory
Tries to answer the question 'how many?' without enumerating all the choices, so for example how many x by a function of n.
212
Rule of sum
The number of ways to choose one element from one of two disjoint sets is the sum of the cardinalities of the sets.
213
Rule of product
The number of ways to choose an ordered pair is the number of ways to choose the first element * the number of ways to choose the second element.
214
Permutation
An ordered sequence of all the elements of a set, with each element appearing exactly once. So all the possible orderings of elements from a set are permutations.
215
How can we express the number of k-combinations of an n-set?
In terms of the number of k-permutations of an n-set, since every subset of the set that is a combination of k elements, is also a permutation of a subset with those k elements.
216
How many permutations of its elements does every k-combination of an n-set have?
k! permutations, each of which is a distinct k-permutation of the n-set.
217
What is the number of k-combinations of an n-set, defined in terms of k?
The number of k-permutations divided by k!, because every k-permutation also has k! permutations.
218
What is the equation for the amount of k-combinations of an n-set?
n!
- - -
k! * (n-k)!
219
0! =
1
220
What does the notation (n k), the fraction without fraction line, denote?
The number of k-combinations of an n-set.
221
What is the equation of (n choose k)?
n!
- - -
k! * (n-k)!
222
Binomial coefficients
the (n choose k) thing, a fraction without lines. Denotes how many combinations of size k you can make of a set of size n.
223
Binomial theorem
(x+y)^n =
SUM(k=0 to n) (n choose k) * (x^k) * (y^(n-k)).
224
What is de binomial theorem if x = y = 1?
(x+1)^n is then 2^n and
= SUM(k=0 to n) (n choose k)
225
For 1<=k<=n, the lower bound for (n choose k) is
(n/k)^k
226
For 1<=k<=n, the upper bound of (n choose k) is
(n^k) / k!
, which is
((e*n)/k)^k
227
How to finish this according to Stirling's approximation?
k! >=
k! >= (k/e)^k
228
For 0<=k<=n, what is the upper bound of (n choose k)?
<= (n^n) / ( (k^k) * ((n-k)^(n-k))
229
H(lambda) entropy function
= -lambda
*
lg(lambda) - (1-lambda)
*
lg(1-lambda).
229
For k = lambda*n with 0<= lambda <= 1, what is the upper bound of (n choose k)?
(n choose k) = (n choose lambda*n).
<= 2^(n * H(lambda))
with H(lambda) is the entropy function
230
Null event
The event EMPTY
231
When are two events A and B mutually exclusive?
When A INTERSECTION B = EMPTY
232
Probability distribution Pr{} on a sample space S
A mapping from events of S to real numbers, satisfying the probability axioms.
233
Probability axioms
1. Pr{A} >=0 for any event A.
2. Pr{S} = 1.
3. Pr{A UNION B} = Pr{A} + Pr{B} for any two mutually exclusive events A and B.
234
Discrete probability distribution
A probability distribution that is defined over a finit or countably finite sample space.
235
What is the conditional probability of an event A given that another event B occurs?
Pr{A|B} = Pr{A INTERSECTION B} / Pr{B}
236
When are two events A and B interdependent?
Pr{ A INTERSECTION B} = Pr{A}*Pr{B}.
237
Bayes's theorem
Pr{A|B} = Pr{A}*Pr{B|A} / Pr{B}
238
Hoe maak je van een standaard stack een MinStack die alle methodes in O(1) doet? statische methode:
Gebruik twee arrays: K en M. K is de normale array van de stack en K[i] geeft de i-de key. M[i] bevat het minimum van de eerste i+1 keys.
239
Hoe maak je van een standaard stack een MinStack die alle methodes in O(1) doet?
Dynamische methode:
Geef nodes naast attributen als .key en .prev nu ook een attribuut .mink.
Mink is de laagste van deze en voorgaande keys.
Bij de Push(x) methode: geen mink van de x de waarde min(key, prev.mink).
240
Hoe bereken je hoeveel permutaties je kunt maken met n letters?
n!
de factorial
241
Wat groeit sneller: de faculteit of c^n met c een positieve constante?
de faculteit.
242
Als je 3 manieren hebt waarop een rijtje letters kan veranderen, hoeveel mogelijke permutaties heb je dan na k stappen?
3^k permutaties.
243
Wat is 0! ?
1
244
Een leeg product heeft waarde...
1
245
Waarom groeit de faculteit sneller dan alle exponentiële functies?
De c^n groeit in elke stap met een factor c, de n! groeit met een steeds grotere groeifactor en begint in te lopen op c^n zodra n>c en wordt uiteindelijk groter.
246
Met welke groeifactor groeit n! ongeveer?
Ongeveer n/e.
247
Hoe definieer je de faculteit n! volgens Stirling's formule?
n! = WORTEL(2*pi*n) * ((n/e)^n)
248
k-uit-n permutatie
Een rijtje van k verschillende elementen uit een verzameling van n elementen. Volgorde maakt uit, dus zelfde elementen in andere volgorde is een andere permutatie.
249
Hoe bereken je het aantal mogelijke combinaties van 1e, 2e en 3e prijswinnaars bij een groep van 25 schaatsers?
Voor de 1e plaats heb je 25 mogelijkheden, dan nog 24 voor de 2e en 23 voor de 3e plek. Aantal mogelijke combinaties is dus
25*24*23 = 13800
250
Formele definitie van het aantal k-uit-n permutaties.
P(n,k) is het aantal k-uit-n permutaties.
P(n,k) = n * (n-1) * (n-2) * ... * (n-k+1).
251
Waar is P(n,k) gelijk aan?
n! / (n-k)!
252
Wat is de definitie van het speciale geval P(n,n)?
P(n,n) = n! = n^_n
253
Wat betekent n^_n (laatste n is onderstreept)?
x^_n = x(x-1)^(_n-1_) en x^_0 = 1.
het is gewoon n! voor een niet-negatieve integer n.
254
k-uit-n combinatie
Een deelverzameling van k elementen uit een verzameling van n. Volgorde maakt NIET uit, dus verschillende volgordes tellen als één deelverzameling.
255
Hoe definieer je een k-uit-n combinatie?
C(n,k) = (n over k)
= P(n,k) / P(k,k)
= n! / (k! * (n-k))!
256
Combinatorisch argument
Een argument waarin je rechtstreeks soorten verzamelingen telt en uitsplitst.
257
Wat is de stelling van de driehoek van Pascal?
1. (n over 0) = 1 en (n over n) =1.
2. (n over k ) = (n-1 over k-1) + (n-1 over k) als 0
258
Kleine stelling van Fermat
Als p een priemgetal is, dan is voor elke gehele a a^p - a deelbaar door p.
259
Binomium van Newton
(x+y)^n = SUM(k=0 to n) (n over k) * (x^(n-k)) * y^k
260
BC (afkorting)
biniomiaal coëfficient
261
Wat geeft de binomiaal coëfficient (n over k) weer?
Het aantal combinaties van k elementen uit n.
262
Experiment (kansrekening)
Een proces met meerdere mogelijke uitkomsten, welke het wordt komt tijdens het experiment aan het licht.
263
Uitkomstenruimte (kansrekening)
De verzameling S van mogelijke uitkomsten
264
Gebeurtenis (kansrekening)
Deelverzameling E van uitkomstenruimte S.
265
Kansmaat
Een kansmaat of kansverdeling op S is een functie Pr: S -> R(eals), zodanig dat
1. FORALL s in S: Pr(s) >0.
2. SUM(all s in S) Pr(s) =1.
266
Voorwaardelijke kans
De voorwaardelijke kans Pr(E|F) is de kans op E die je krijgt als je de kans op E bepaalt binnen de deelverzameling van S die aan F voldoet.
267
E en F zijn onafhankelijk als...
Pr(E|F) = Pr(E).
268
Regel van Bayes
Pr(F|E) = Pr(E|F) * (Pr(F) / Pr(E))
269
Stochast
Een toekenning van numerieke waarden aan de uitkomsten van een experiment.
270
Stelling van lineariteit van verwachting
E(X+Y) = E(X) + E(Y)
271
Wat is de productregel voor onafhankelijke gebeurtenissen?
E(X*Y) = E(X) * E(Y)
272
What is the running time of heapsort?
O(n lg n)
273
Heapsort has the same running time as ...
Merge sort
274
Does heapsort sort in place?
Yes.
275
Heap data structure
An array object that we can view as a nearly complete binary tree.
276
How does a heap relate to the array object it is stored in?
An array A[0:n] representing a heap may contain many elements, but only the elements in A[0:A.heap-size-1] with 0<= A.heap-size <= n are valid elements of the heap.
277
What does A.heap-size represent?
How many elements in the heap are stored within array A.
278
PARENT(i) in a heap
return FLOOR(i/2)
279
LEFT(I) ni a heap
return 2i
280
RIGHT(i) in a heap
return 2i+1
281
How is the LEFT(i) of a heap element constructed using the bit representation of that element?
The binary representation is shifted to the left by one bit position.
282
Left bit shift
The most-significant bit is lost, and a 0 bit is inserted on the other end. Written as '<<'.
EX: 0010 << 1 becomes 0100
283
What does a single left bit shift do to a binary number?
It multiplies it by 2.
EX: 0010 << 1 becomes 0100
0010 = 2 and 0100 = 4.
284
How is the RIGHT(i) procedure done using operations on the binary representation of element i?
The binary representation of i is shifted left by one bit position and then 1 is added.
285
How is the PARENT(i) procedure done using operations on binary representation of element i?
The binary representation of i is shifted right by one bit position.
286
What happens when you shift a binary representation right by one bit position?
The least significant bit is lost and a 0 is inserted on the other end. Divides a number by 2.
EX: 0101 >> 1 becomes 0010
0101 is 5 and 0010 is 2, so this takes FLOOR(5/2).
287
What are the two kinds of binary heaps?
max-heaps and min-heaps.
288
Max-heap property
A[PARENT(i)] >= A[i]
A parent's value is always bigger or equal than the kid's value.
289
Where is the smallest element in a min-heap?
At the root.
290
Min-heap property
A [PARENT(i)] <= A[i]
So parent is always smaller or equal to the kid.
291
Definition of height of a node in a heap
The number of edges on the longest simple downward path from the node to a leaf.
292
Definition: height of a heap
The height of its root.
293
What is the height of a heap of n elements?
THETA(lg n), since it is based on a complete binary tree.
294
What is the running time of MAX_HEAPIFY?
O(lg n)
295
What is the key to maintaining the max-heap property?
MAX_HEAPIFY
296
What is the running time of BUILD-MAX-HEAP?
Linear time
297
What does BUILD-MAX-HEAP do?
It produces a max-heap from an unordered input array.
298
What is the running time of HEAPSORT?
O(n lg n)
299
What does MAX-HEAPIFY assume when it is called?
That the binary trees rooted at LEFT(i) and RIGHT(i) are maxheaps, but that A[i] might be smaller than its children.
300
What does MAX-hEAPIFY do?
It lets the value at A[i] 'float down' in the max-heap so that the subtree rooted at index i obeys the max-heap property.
301
What happens in each step of the MAX-HEAPIFY procedure?
The index of largest of the elements A[i], A[LEFT(i)] and A[RIGHT(i)] is stored in 'largest'. If A[i] == largest, then the subtree rooted at node i is already a max-heap. If not, then positions i and largest swap so that node i and its children satisfy the max-heap property. Ten recursively on subtree rooted at largest, since it might violate the mh property.
302
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if(l <= A.heap-size and A[l]>A[i])
{largest = l}
else {largest = i}
if (r<= A.heap-size and A[r] > A[largest])
{ largest = r}
if(largest != i)
{ exchange A[i] with A[largest]
MAX-HEAPIFY (A, largest) }
303
What recurrence describes the running time of MAX-HEAPIFY?
T(n) <= T(2n/3) + THETA(1)
304
What is the running time of MAX-HEAPIFY on a node of height h?
O(h)
305
BUILD-MAX-HEAP (A, n)
A.heap-size = n
for (i = FLOOR(n/2) down to 1)
{MAX-HEAPIFY(A, i) }
306
What is the loop invariant of BUILD-MAX-HEAP?
At the start of each iteration of the for loop of lines 2-3, each node i+1, i+2, ..., n is the root of a max-heap.
307
HEAPSORT(A, n)
BUILD-MAX-HEAP(A,n)
for (i=n down to 1)
{ exchange A[0] with A[i]
A.heap-size = A.heap-size -1
MAX-HEAPIFY(A, 0) }
308
What does INSERT(S, x, k) do in a priority queue?
It inserts the element x with key k into the set S, which is equivalent to the operation S = S UNION WITH {x}.
309
Handles
Additional information stored in the objects that give enough information to perform mapping from objects to and from array indices.
310
MAX-HEAP-MAXIMUM(A)
if A.heap-size <1
error "heap underflow"
return A[0]
311
MAX-HEAP-EXTRACT-MAX(A)
max = MAX-HEAP-MAXIMUM(A)
A[0] = A[A.heap-size]
A.heap-size = A.heap-size -1
MAX-HEAPIFY (A, 0)
return max
312
MAX-HEAP-INCREASE-KEY(a,x,k)
if (k< x.key)
{ error "new key is smaller than current key"}
x.key = k
find index i in array A where object x occurs
while (i>0 and A[PARENT(i)].key < A[i].key)
{Exchange A[i] with A[PARENT(i)], updating info that maps priority queue objects to array indices.
i = PARENT(i) }
313
MAX-HEAP-INSERT(A, x, n)
if(A.heap-size == n)
{ error "heap overflow" }
A.heap-size = A.heap-size +1
k = x.key
x.key = -infinity
A[A.heap-size] = x
ma[ x to index heap-size in the array
MAX-HEAP-INCREASE-KEY(A, x, k)
314
In hoeveel tijd realiseert de heap insert en extract_min?
O(lg n)
315
Event simulatie
Berekent wat er gebeurt in een systeem.
316
Hoe kun je een heap het beste in een C# array implementeren?
Laat A[0] ongebruikt.
317
SOM (i=0 to infinity) x^i
1 / (1-x)
318
Bernoulli trials: Als U een rijtje is met k maal Successes en n-k maal Failures, dan is Pr(U) =
Pr(U) = p^k * q^(n-k)
Want p is kans op success en q is kans op failure.
319
Miller + Rabin stelling
ALs p is samengesteld, dan Pr(p| a^p -a) <= 1/4.
320
Pr(Aantal successen is k) =
(n over k) * p^k * q^(n-k)
321
Wat houdt de geometrische verdeling in?
Het is de kans dat een aantal van k tests nodig is voor het eerste succes.
322
Hoe bereken je hoeveel tests nodig zijn om een success te behalen?
Gebruik de geometrische verdeling. Voor het aantal tests A geldt Pr(A=k) = q^(k-1) * p
323
Negatief binomiale verdeling
De kans dat je het m-de succes boekt in poging n.
324
Hoeveel rijtjes zijn er met het m-de succes op plaats n?
(n-1 over m-1) rijtjes.
325
De kans dat je het m-de succes boekt in poging n, Pr(A=n) =
(n-1 over m-1) * p^m * (1-p)^m
326
Als je herhaaldelijk trekt uit een verzameling met n elementen, duurt het ... trekkingen tot je een specifieke waarde ziet?
n trekkingen
327
Hoeveel trekkingen duurt het voordat je een botsing ziet in een verzameling met n elementen?
ROOT(2*n) trekkingen.
328
Hoeveel trekkingen duurt het voordat je alles hebt gezien in een verzameling met n elementen?
n * h_n trekkingen.
329
Variantie
De verwachting van het kwadraat van de afwijking van het gemiddelde.
330
Wat zijn twee voordelen van het gebruik van de variantie in kansrekenen?
1. Positieve en negatieve afwijkingen tellen allemaal positief door het kwadrateren.
2. Het is linear voor onafhankelijke stochasten.
331
KVP (afkorting)
Key-value-pair
332
Wanneer kun je een hash tabel gebruiken voor een dictionary?
Als je uitsluitend via bekende keys toegang wilt.
333
Wat is het voordeel van een hash tabel gebruiken bij een dictionary?
Het biedt insert, delete en search operaties in O(1) tijd.
334
Wanneer moet je zoekboom gebruiken voor een dictionary?
Wanneer je ingewikkeldere operaties wilt zoals max, hoeveelheid intermediate keys enzo.
335
Wat is het gevolg van een zoekboom gebruiken voor dictionary?
Operaties en queries worden in O(lg n) tijd gedaan.
336
Wanneer kun je direct adressing gebruiken bij hashen?
Als de keys allemaal uit een kleine verzameling U = {0, .., m-1} komen én elke key maar 1 keer kan voorkomen.
337
Hoe gebruik je direct adressing voor hashen?
Gebruik een array van lengte m (Voor universum van keys van 0 t/m m-1) met pointers naar de satelliet data.
338
Wat kun je doen bij hashen als er geen satellite data is, maar alleen de aanwezigheid van de key telt?
Een bit-array gebruiken.
339
Wat is het geheugengebruik van een array bij hashen?
O(m) voor een universum van keys {0, ..., m-1}. Is onafhankelijk van het daadwerkelijk aanwezige aantal keys (n).
340
Hoe doe je hashen wanneer de verzameling van mogelijke keys te groot is voor een array?
Maak een hash-functie H: U -> {0, ..., m-1} die aan elke mogelijke key een getal H(k) < m geeft.
341
Waar wordt key k opgeslagen wanneer je een hash functie gebruikt om te hashen?
Op locatie A[H(k)]
342
Waarom moet je een key expliciet opslaan bij hashen met een Hash functie?
Omdat meerdere keys dezelfde waarde van H hebben.
343
Hoe doe je hashing met hash functie in C#?
De basis is de HashCode, je doe telkens H = HashCode % m
344
Wat zijn de twee typen botsingen bij hashen met een hash functie?
1. Verschillende x en y met dezelfde HashCode.
2. De HashCode verschilt, maar m is een deler van het verschil dus HC(X) is niet HC(y), HC(x) % m is wel HC(y) % m.
345
Wat gebeurt er als er een botsing/collission plaatsvindt bij hashing met hash functie?
Meerdere KVP's hashen naar dezelfde locatie.
346
Noem twee oplossingen voor collissions bij hashen?
1. Chaining
2. Open adressing
347
Hoe los je botsingen bij hashen op met chaining?
Maak per locatie een lijstv an KVP's. C# doet dit ook.
348
Hoe los je botsingen bij hashen op met open adressing?
Wijk bij een botsing uit naar alternatieve locaties binnen de array.
349
Load factor alpha
Het gemiddelde aantal keys per locatie bij hashen.
350
Hoe bereken je de load factor alpha?
alpha = n/m met n = aantal keys en m = aantal locaties om de keys op te slaan.
351
Waarom wil je de load factor alpha klein houden bij hashen?
Zodat het geen probleem is om bij chaining een inefficiente datastructuur (list) te gebruiken.
352
Hoe werkt Insert(k,v) bij hashing met chaining?
h = H(k);
A[h].Add(k,v);
353
Hoe werkt Delete(k) bij hashing met chaining?
h = H(k);
A[h].RemoveKey(k);
354
Hoe werkt Search(k) bij hashing met chaining?
h = H(k);
A[h].Contains(k);
355
Wat is array A bij hashing met chaining?
List[m],
dus een array van lijste van key-value-pairs
356
Hoe bereken je de gemiddelde tijd voor onsuccescol zoeken bij hashen?
H(k) is willekeurig, dus telt het gemiddelde aantal keys over de lijsten.
357
Hoe bereken je gemiddelde tijd voor succesvol zoeken bij hashen?
Elke key telt even vaak , dus het gemiddelde aantal per lijst over de keys
358
Wat is duurder bij hashen met chaining: succesvol of onsuccesvol zoeken?
Succesvol zoeken
359
Wat betekent het dat de hash functie deterministisch is?
Als een key k opnieuw wordt aangeboden en H weer uitgerekend, dan komt er hetzelfde uit.
360
Waarom is voor een nieuwe key, elke lijst even waarschijnlijk als uitkomst van de hash functie?
Bij een random key x is Pr(H(x)=i) = 1/m.
361
Waarom is er voor twee keys kans 1/m om in dezelfde lijst terecht te komen?
De hash functie is onafhankelijk, dus voor random x en y geldt Pr(H(x)=H(y)) = 1/m.
362
Wat is de eis voor de load factor alpha bij hashing met open adressing?
Alpha moet kleiner zijn dan 1.
363
Wat is een voordeel van open adressing bij hashen?
Er zijn minder pointers, dus met evenveel geheugen kun je m groter maken en blijft alpha relatief klein.
364
ProbeSequence
De reeks posities die de hash functie voor een key k levert bij hashen met open adressing.
365
Hoe werkt insert(k) bij hashen met open adressing?
k wordt op de eerste lege plek in de probesequence gezet.
i=0;
while( A[H_i(k)] != NIL) {i++;}
A[H_i(k)] = (k,v);
366
Wat gebeurt er als key k op positie H_i(k) wordt gezet?
Alle posities H_j(k) voor j
367
Hoe werkt zoeken bij hashen met open adressing?
De probesequence wordt afgelopen tot er een lege plek is waar key k niet voorkomt, of er een key k gevonden is.
368
Waarom moet je bij delete in hashing met open adressing, de key vervangen door een DEL?
Anders wordt de probingsequence onderbroken en gaat de search operatie foute antwoorden geven omdat ie een lege plek vind waar de key niet is, terwijl ie misschien verderop in te tabel wel te vinden is.
369
Hoeveel plekken moet je ongeveer bekijken voordat je een lege ziet bij hashing met open adressing waarbij een fractie alpha van de plekken bezet is?
1 / (1-alpha)
370
Wat is de kans dat de lengte van lijst b gekwadrateerd wordt bij een hashtabel van n keys en m lijsten en functie H zodat Pr(H(x_i) = b) = 1/m?
Stel we geven het event H(x_i) = b waarde 1 en anders 0.
Lengte van b is de som van x_i voor alle waardes tussen 1 en n. Het kwadraat hiervan is dan dus de som van kans dat in lijst b voor alle x tussen 1 en n keer deze som. De kans dat beide in lijst b zitten, is de gegeven kans van 1/(m^2).
E(L^2) = n * 1/m + (n(n-1))* 1/(m^2).
371
Definitie: een binaire boom delta is...
a. leeg
b. een knoop met een key en twee bomen.
372
Wat is een lege boom in c#?
Een null-pointer
373
Zoekboom-eigenschap
Alle keys in de linkerboom zijn kleinergelijk dan de wortel en de keys in de rechterboom zijn grotergelijk dan de wortel.
374
Wat is de hoogte van een lege boom?
-1
375
Hoe kun je een eigenschap van alle bomen bewijzen?
Met inductie over de structuur van de boom:
1. Geldt voor een lege boom
2. Eigenschap P voor een knoop met deelbomen l en r volgt uit P(l) en P(r).
376
Hoeveel keys bevat een boom met hoogte h maximaal?
2^(h+1) -1 keys
377
Wat is de hoogte van een boom met n keys minimaal?
lg(n+1)-1
378
Geef het algoritme om alle keys in een Boom b te printen, op volgorde van klein naar groot:
*PrintAlles
if (b == null) {return;}
PrintAlles ( b.left);
Print b.key;
Printalles (b.right);
379
Morse-tekens: hoeveel letters M(l) zijn er van lengte l, uitgedrukt met recursie?
M(l) = M(l-1) + M(l-2).
380
Een AVL-boom is...
1. Leeg, met alleen een blad
2. Een knoop met twee deelbomen, elk een AVL-boom.
381
Wat is de hoogte van een AVL-boom?
Het aantal nivo's met interne knopen
382
Wat is de omvang van een AVL-boom?
Het aantal bladen.
383
Wat is het minimale aantal bladen A(h) van een AVL-boom met hoogte h?
A(h) = Integraal van (h+2)
A(h) = A(h-1) + A(h-2)
384
Stel een AVL-boom met b bladen heeft hoogte h. Dan is de definitie van A(h):
b >= A(h) = Integraal (h+2)
385
Geef de definitie van de rij Fibonaccie-getallen
1. f_0 = 0 en f_1 = 1;
2. f_n = f_(n-1) + f_(n-2) voor alle n>=2.
386
Hoe bereken je de gemene deler van een breuk a/b met Euclides?
Euclides(a,b)
{
while(b != 0)
{ (a,b) = (b, a%b); }
return a;
}
387
Fibonaccie sommatie eigenschap: delta(f_i) =
f_(i+1) - f_i
= f_(i-1)
388
Wat is de som van de eerste n Fibonaccie-getallen?
Som(i=0 to n-1)f_i = Differentiatie van 0 tot n (f_(i+1))
= f_(n+1) - f_1
= f_(n+1) - 1
389
f_-1 =...
1
390
Wat is er speciaal aan iets met inductie bewijzen over Fibonacci-getallen?
Je hebt vaak twee basisgevallen, omdat de karakteriserende relatie pas geldt vanaf f_2.
391
De Fibonacci-getallen met oneven coëfficienten sommeren tot...
Het volgende Fibonacci-getal.
392
Twee opeenvolgende Fibonacci's kwadrateren en optellen geeft...
Weer een Fibonaccie getal.
393
f_(2n+1)=
f_(n+(n+1))
= f_(n+1) * f_(n+1) + f_n * f_n
= f_(n^2) + f_(n+1)^2
394
Lineare combinatiestelling (idee)
Voor elke getallen A en B voldoet de rij f_n = (A*(phi^n) + B*(phi^-n)) aan de relatie f_n = f_(n-1) + f_(n-2).
395
f_n = ...
1/(wortel 5) * ((phi^n) - (phi^-n))
396
Voor alle n>= is f_n de...
op integers afgeronde waarde van 1/wortel 5 * phi^n.
397
Hoe bereken je wanneer je het Fibonacci-getal x hebt?
1/wortel 5 * phi^n = x
geeft
n = phi_log(x*wortel5)
398
Recurrentie Relatie
Een definitie van een rij getallen, die de waarde "a_n" beschrijft in termen van eerdere getallen in de rij.
399
Wat moet je doen om een recurrentie relatie compleet te maken?
Eén of meer begingetallen bij zetten.
400
Wanneer is een recurrentie relatie linear?
Als de vorige getallen alleen met iets worden vermenigvuldigd en opgeteld.
401
Wanneer is een recurrentie relatie homogeen?
Als er alleen maar termen zijn die een veelvoud van vorige getallen zijn.
402
Wanneer is de recurrentie relatie constante coëfficienten?
De getallen waarmee je vermenigvuldigd zijn niet afhankelijk van n.
403
Wanneer is een recurrentie relatie graad k?
Als de waarde alleen afhangt van de k waarden ervoor. Je hebt dan k startwaarden nodig.
404
Met welke twee stappen los je de recurrentie relatie a_n = c_1*a_(n-1) + c_2*a_(n-2) op?
1. Bepaal alpha zodat alpha^n een oplossing is van de recurrente betrekking.
2. Van de algemene oplossing c*alpha(1 to n) + d*(alpha 2 to n) kun je c en d tunen om aan startwaarden te voldoen.
405
Hoe bepaal je alpha bij de eerste stap van het oplossen van een recurrentie relatie a_n = c_1*a_(n-1) = c_2*a_(n-2)?
Uit de rr hierboven aal je alpha^2 - c_1*alpha -c_2 = 0.
Dit los je op met de abc-formule.
406
Lineare Combinatiestelling (definitie)
Als alpha(1 to n) = c_1*alpha(1 to n-1) = c_2*alpha(n-2) en
alpha(n to 2) = c_1*alpha(2 to n-1) + c_2*alpha(2 to n-2),
dan voldoet voor elke combo getallen C en D de rij a_n = C*alpha(1 to n) + D*alpha(2 to n) aan de relatie a_n = c_1*a_(n-1) + c_2*a_(n-2).
407
Als je a_0 en a_1 hebt, kun je de formule voor a_n exact vinden door...
a_0 = C *alpha(1 to 0) + D*alpha(0 to 2) = C+D
en
a_1 = C*alpha(1 to 1) + D*alpha(2 to 1) = C*alpha_1 + D*alpha_2.
408
Als alpha een dubbel nulpunt is van het karakteristieke polynoom, dan...
is ook a_n = n*(alpha^n) een oplossing.
409
phi_log(n) =
4.78 * 10_log(n)
= 1.44...lg(n)
410
f_n golvende=
1/wortel5 * (phi^n)
met phi=(1+wortel5)/2
411
b_log(a) is de oplossing van x voor de vergelijking
b^x =a
412
b^x = a uitgedrukt in log geeft...
b^(b_log(a)) = a
of x = b_log(a).
413
b^(b_log(a_1)) + b^(b_log(a_2)) =
b^(b_log(a_1)) * b^(b_log(a_2))
414
b^(b_log(a_1) * b^(b_log(a_2) =
a_1 * a_2 volgens de def van log, nl b^(b_log(a)) = a.
415
b_log(a_1*a_2) ==
b_log(a_1) + b_log(a_2)
416
Productregel voor log
b_log(a_1*a_2) = b_log(a_1) + b_log(a_2)
417
b_log(x^y) ==
y * b_log(x)
418
b^(y* b_log(x)) ==
b^ (b_log(x) * y)
419
b^ (b_log(x)*y) ==
(b^b_log(x)) ^y
420
Grondtal conversie bij logarithmes
b_log(a) =
c_log(a) / c_log(b)
421
b_log(1) =
0
422
b_log(b) =
1
423
b_log(a) is positief als...
a en b aan dezelfde kant van 1 liggen.
424
b_log(a) is negatief als...
als de ene kleiner en de andere groter dan 1 is.
425
lg^2 (x) ==
(lg(x))^2
426
b_log(a) == -...
-b_(log(1/a) of
-(1/b)_log(a).
427
Even functie
f is een even functie als de Taylorreeks van f alleen even machten van x heeft.
428
Als f een even functie is, dan is f(x) ==
f(-x).
429
Wat is de wet voor het vinden van Taylor-coëfficienten?
a_k = f (afgeleide k) (0) / k!
430
Neem f(x) = e^x. Dan f(0) =
e^0 = 1
431
Taylorreeks
Beschrijft een functie f als
f(x) = SOM(alle k) a_k * x^k
432
Wat is de verwachting van het aantal successen in een Bernoulli-reeks?
n*p met n = aantal trials en p = kans op success.
433
Je gooit met een 6kantige dobbelsteen tot je 3 verschillende uitkomsten hebt gezien. Hoeveel keer moet je verwacht gooien?
Noem x_i = verwacht aantal worpen voor waarde i.
De eerste waarde zie je zeker bij je eerste worp, dus x_1 = 1.
Voor de 2e waarde heb je succeskans 5/6, dus aantal worpen verwacht is x_2 = 6/5.
Dan volgt x_3 = 6/4.
Verwacht aantal worpen is dus 1 + 6/5 + 6/4 = 3.7.
434
Is een functie altijd even of oneven?
Nee. Er zijn functies die zowel niet spiegelsymetrisch in de y-as zijn (even) en niet puntsymmetrisch in de oorsprong (oneven).
435
Is er een functie die even én oneven is?
Ja.
436
-
Key Links
-
Subjects
-
Company
-
Find Us
-
