Datastructures Flashcards
(381 cards)
1
Q
Randomized algorithm
A
An algorithm whose behavior is not only determined by the input, but also by the values by a random number generator.
2
Q
Give the formal definition of the sorting problem
A
Input: A sequence of n numbers (a1, …, an)
Output: A permutation (a’1, …, a’n) of the input sequence such that a’1 <_ … <_ a’n.
3
Q
The instance of a problem consists of…
A
the input needed to compute a solution to the problem.
4
Q
When is an algorithm for a computational problem correct?
A
When it halts for every problem instance and outputs the correct solution.
5
Q
What does n! denote?
A
The factorial function.
For n=6, n! = 6 x 5 x 4 x 3 x 2 x 1
6
Q
data structure
A
A way to store and organize data in order to facilitate access and modification.
7
Q
How much time does the algorithm insertion sort take to sort n items?
A
c1 * n^2
with c1 = constant
8
Q
How much time does the algorithm merge sort take to sort n items?
A
c2 * n * log2(n)
with c2 = constant
9
Q
keys
A
the numbers to be sorted in the sorting problem
10
Q
What is the form of the input in the sorting problem?
A
An array with n elements.
11
Q
satellite data
A
The data that the input keys are associated with.
12
Q
record
A
The key and the satellite data.
13
Q
insertion sort
A
An algorithm for sorting a small number of elements. A key is compared to each value and inserted when a value is encountered that is less or equal to the key.
14
Q
What are the 3 things you need to show in a loop invariant?
A
1) initialization
2) maintenance
3) termination
15
Q
What are objects composed of?
A
attributes
16
Q
Analyzing an algorithm
A
Predicting the resources an algorithm requires.
17
Q
RAM
A
Random-Access Machine
18
Q
What 3 instructions does the RAM model contain?
A
1) arithmetic
2) data movement
3) control
19
Q
What are arithmetic instructions? (7)
A
add, subtract, multiply, divide,
remainder, floor, ceiling
20
Q
What are data movement instructions? (3)
A
load, store, copy
21
Q
What are control instructions?
A
conditional and unconditional branch, subroutine call and return.
22
Q
What are the data types in the RAM model?
A
integer, floating point and character
23
Q
How do we assume integers are represented as data?
A
As c * log2 (n) bits
with c = a constant bigger than or equal to 1.
24
Q
DIvide-and-conquer method
A
Breaking the problem into several subproblems that are similar to the original, but smaller in size. Solve the problems recursively and combine the solutions to create solution to original problem.
25
Recusive algorithm
An algorithm that calls itself repeatedly to solve a related problem.
26
Permutatie
Ordening. Aantal is gelijk aan de factorial.
27
Postconditie
Beschrijft wat het betekent voor de output om correct te zijn.
28
Conditie C
De while/if/for opdracht
29
Body B
Wat er in de loop staat.
30
Terminatie T
De return opdracht van algoritme.
31
Theta-notation means...
Roughly proportional
32
When do we consider one algorithm to be more efficient than another?
When its worst case running time has a lower order of growhth.
33
Geef de stappen voor bewijs met inductie voor een statement als
'Voor alle gehele getallen n>_ b geldt de eigenschap P(n)'.
1) We gebruiken inductie. Definieer P(n) = eigenschap.
2) Basisstap: bewijs dat P(b) geldt.
3) Inductiestap: bewijs dat voor een willekeurig getal >_b, zeg k, als P(k), dan P(k+1).
4) Concludeer waar voor alle n>_b.
33
Harmonische sommatie
Convergeert monotoon naar nul, maar bereikt 0 nooit.
34
Inductieve inferentie
De redeneermethode waarmee je uit een aantal voorbeelden een algemene regels probeert op te stellen. Niet logisch.
35
Deductieve inferentie
Een redeneermethode die leidt tot logisch geldende conclusies.
36
PROP
De verzameling propositielogsiche formules.
37
Rekenkundige reeks
Een sommatie van opeenvolgende termen met een constant verschil.
38
Meetkundige reeks
Een sommatie van opeenvolgende termen met een constante verhouding.
39
Harmonische reeks
Voor positieve, gehele n is het nde harmonishe getal de som van 1/1, 1/2, 1/3... tot 1/n.
40
Lineariteit in sommaties
De sommatie van (c*a.k + b.k) is gelijk aan
c* de sommatie van a.k + de sommatie van b.k
41
De sommatie van kwadraten is gelijk aan...
(n(n+1)(2n+1) ) / 6
42
De sommatie van n^3 is gelijk aan...
(n^2 * (n+1)^2) / 4
43
Geometrische reeks
De sommatie 1 + x + x^2 + x^3 + x^... + x^n
44
De geometrische sommatie is gelijk aan...
(x^(n+1) - 1) / (x-1)
45
When is a function f(n) monotonically increasing?
If m <_ n implies f(m) <_ f(n).
46
When is a function f(n) monotonically decreasing?
If m<_n implies f(m) >_ f(n).
47
When is a function f(n) strictly increasing?
If m < n implies f(m) < f(n).
48
When is a function f(n) strictly decreasing?
If m< n implies f(m) > f(n).
49
Wat is |_x_|?
The greatest integer less than or equal to x.
50
Wat is |- x -|?
The least integer greater than or equal to x.
51
What property do the floor and ceiling function have?
They are monotonically increasing.
52
Floor & ceiling property:
For any integer n, we have
|_n_| = n = |- n -|
53
Floor & ceiling property.
For any real number x, we have
x-1 < |_x_| <_ x <_ |-x-| < x+1
54
|_-x_| ==
minus |-x-|
55
minus |_x_| ==
|- -x -|
56
For any real number x >_ 0 and integers a,b > 0, we have
|- (|- x/a -|) / b -| =...
|- x / ab -|
57
For any real number x>_0 and integers a,b >0, we have
|_ (|_ x/a _|) / b _| ==
|_ x / ab _|
58
For any real number x>0 and integers a,b>0, we have:
|- a/b -| <_ ...
(a + (b-1)) / b
59
For any real number x>0 and integers a,b>0, we have:
|_ a/b _| >_ ...
(a - (b-1)) / b
60
For any integer n and real number x, we have:
|_ n+x _| ==
n + |_x_|
61
For any integer n and real number x, we have:
|- n+x -| ==
n + |-x-|
62
For any integer a and any positive integer n, the value a mod n is...
the remainder of the quotient a/n.
63
a mod n ==
a - n |_ a/n _|
64
If (a mod n) = (b mod n), we write...
and say...
a = b (mod n)
a is equivalent to b, modulo n.
65
Given a nonnegative integer d, a polynomial in n of degree d is a function p(n) of the form...
p(n) = SUM(i=0, d) a.i * (n^i)
66
What are the coefficients of the polynomial
p(n) = SUM(i=0, d) a.i * (n^i)
for a nonnegative integer d?
The constants a.0, a..., a.d. With a.d not equal to zero.
67
A polynomial is asymptotically positive if and only if...
a.d > 0
68
For an asymptotically positive polynomial p(n) of degree d, we have p(n) ==
THETA (n^d)
69
For any real constant a>_0, the function n^a is ...
monotonically increasing.
70
For any real constant a<_0, the function n^a is...
Monotonically decreasing.
71
We say that a function f(n) is polynomially bounded if...
f(n) == O (n^k) for some constant k.
72
For all real a>0, m and n, we have:
a^0 =
1
73
For all real a>0, m and n, we have:
a^1 =
a
74
For all real a>0, m and n, we have:
a^(-1) =
1/a
75
For all real a>0, m and n, we have:
(a^m) ^n =
a ^ mn
or
(a^n) ^m
76
For all real a>0, m and n, we have:
(a^m)(n^m) =
a^(m+n)
77
For all n and a>_1, the function a^n is...
monotonically increasing in n
78
We assume 0^0 =
1
79
For all real constants a>1 and b, we can relate the rates of growth of polynomials and exponentials by...
LIM(n to infinity) of (n^b) / (a^n) = 0
and n^b = o(a^n).
80
Any exponential function with a base strictly greater than 1 grows...
faster than a polynomial functino.
81
For all real x, we have
e^x =
1 + x + ((x^2)/2!) + ((x^3)/3!) + .... =
SUM(i=0, infinity) (x^i)/i!
82
For all real x, we have the inequality x+1 <_ ...
e^x
Equality , so z+1 = e>x, holds only when x=0.
83
When |x| <_ 1, we have the approximation with e^x:
1+x <_ e^x <_ 1 + x + x^2
84
When x->0, the approximation of e^x by x+1 is...
e^x = x + 1 + THETA(x^2)
85
lg n ==
log.2 n
86
Binary logarithm
lg n
log.2 n
87
Natural logarithm
ln n
log.e n
88
Exponentiation
lg^k n
(lg n )^k
89
lg^k n ==
(lg n)^k
90
lg lg n ==
lg(lg n)
91
Composition
lg lg n
lg(lg n)
92
For any constant b>1, the function log.b n is undefined if
n<_0
93
For any constant b>1, the function log.b n is strictly increasing if
n>0
94
For any constant b>1, the function log.b n is negative if
0 < n < 1
95
For any constant b>1, the function log.b n is positive if...
n>1
96
For any constant b>1, the function log.b n is zero if...
n=1.
97
For all real a>0, b>0, c>0 and n, we have...
a =
b^(log.b a)
98
For all real a>0, b>0, c>0 and n, we have..
log.c (ab) ==
log.c a + log.c b
99
For all real a>0, b>0, c>0 and n, we have...
log.b (a^n) =
n log.b a
100
For all real a>0, b>0 and c>0, we have
log.b a =
log.c a / log.c b
or
1/ (log.a b)
101
For all real a>0, b>0, c>0 and n, we have..
log.b (1/a) =
-log.b a
102
For all real a>0, b>0, c>0 and n, we have..
a^(log.b c) =
c^(log.b a)
103
Changing the base of a logarithm from one constant to another changes the value of the logarithm...
by only a constant factor.
104
For x>-1, the inequalites with logarithms hold...
x/(1+x) <_ ln (1+x) <_ x
105
A function f(n) is polylogarithmically bounded for some constant k if f(n) =...
(running time thing)
O(lg^k n)
106
For all real constants a>0 and b, we have...
lg.b n =
o(n^a)
107
The factorial n! is recursively
defined for n>_0 as
1 if n=0
n(n-1)! if n>0
108
Give Stirling's approximation,
n! =
ROOT(2pi*n) * (n/e)^n * (1 + THETA(1/n))
109
n! = o..
o(n^n)
110
n! = omega(...
omega(2^n)
111
lg(n!) = theta(..
theta(n lg n)
112
For all n>_1 it holds that
n! =
ROOT(2pi*n) * (n/e)^n * e^(alpha.n)
with
1/(12n+1) < alpha.n < 1/12n
113
We define the Fibonacci numbers F.i for i>_0 as ...
0 if i=0
1 if i=1
F.(i-1) + F.(i-2) if i>-2
114
golden ratio
phi
115
conjugate of the golden ratio
phi met een dakje erop
116
Phi (golden ratio) =
(1+ROOT(5)) /2
117
(phi)^ =
(conjugate of golden ratio)
(1-ROOT(5))/2
118
In golden ratios,
F.i =
(phi.i - phi.i^) / ROOT(5)
119
Substitution method in 2 steps
1) Guess the form of the solution using symbolic constants.
2) Use mathematical induction to show that the solution works and find the constants
120
Master recurrence
Describes the running time of a divide-and-conquer algorithm that divides a problem of size n into a subproblems, each of size n/b < n.
121
How much time does the divide-and-conquer algorithm take to solve each subproblem?
T(n/b) time, with n= the size of the original problem and b= the size of the subproblem.
122
What does the driving function f(n) entail?
The cost of dividing a problem into subproblems and the cost of combining the solution to get a final solution.
123
For a>0, b>1 and T(n) = aT(n/b) + f(n), what is the first part of the master theorem?
If there exists a constant epsilon>0 such that f(n) = O(n^(log.b a - epsilon)), then T(n) = THETA(n^(log.b a)).
124
For a>0, b>1 and T(n) = aT(n/b) + f(n), what is the second part 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)).
125
For a>0, b>1 and T(n) = aT(n/b) + f(n), what is the third part 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) additionally satisfies the regularity condition, then T(n) = THETA(f(n)).
126
Regularity condition for f(n) in the master theorem.
a f(n/b) <_ c f(n)
for some constant c<1 and all sufficiently large n.
127
Watershed function
n^(log.b a)
128
How do you use the master method?
Determine which of the three cases applies and then write down the answer.
129
Geef drie voorbeelden van het verdeel-en-heers algoritme:
binair zoeken
merge sort
quicksort
130
What is the worst-case running time of the quicksort algorithm on an input array of n numbers?
THETA(n^2).
131
Why is quicksort often the best algorithm for sorting?
The expected running time is THETA(n lg n) when all numbers are distinct, and the constant factors in that notation are small.
132
comparison sorts
Algorithms that determine the sorted order only based on comparing input elements.
133
Algoritme
Een oplossing voor een computationeel probleem, gedefinieerd als een relatie tussen input en output.
134
Een algoritme is niet hetzelfde als een ... in C#.
Een methode
135
Een datastructuur is niet hetzelfde als een ... in C#
een object
136
Linear zoeken
Bij het begin beginnen en doorgaan tot het eind of totdat je x gevonden hebt.
137
ZOEK-LINEAR (A,x)
i=0
while i < A.length
if A[i] == x
return i
i++1
return -1
138
Hoelang duurt ZOEK-LINEAR (A,x) voor een bepaalde x en A.length = n?
Als x niet in A: n vergelijkingen
Als x in A: n vergelijkingen of 1 vergelijking (ligt aan positie van x in A) of n/2 vergelijkingen (gemiddelde optie).
139
Hoe werkt binair zoeken globaal?
Zet index i helemaal links en index j helemaal rechts. Zoek het midden (m). Als xm, gooi linkerhelft weg. Herhaal totdat i==j-1.
140
BINAIR-ZOEKEN (A, x)
i = 0
j= A.length -1
while i < j
m = |_ (i+j) / 2 _|
if A[m] < x
i = m+1
else
j = m
if A[i] == x
return i
else
return -1
141
Correctheid
De juiste output bij de juiste input.
142
Loop invariant
Als P(k) betekent dat eigenschap P waar is voorafgaand aan iteratie k van de loop, dan is P een loop invariant als P(k) geldt voor alle k >_1.
143
Hoe gebruik je inductie om een loop invariant te bewijzen?
Basisstap: Bewijs dat de loop invariant geldt in iteratie 0 of 1.
Inductisstap: te bewijzen is als P(k), dan P(k+1). Neem aan dat P(k). Bewijs P(k+1) door te gebruiken dat P(k) en P(+1) = P(k+1).
144
Hoe toon je terminatie van een loop aan?
Beargumenteer dat de variant 0 wordt.
145
INSERTION-SORT (A)
for j = 2 to A.length
..... key = A[j]
.... i = j-1
.... while i>0 and A[i] > key
.... .... A[i+1] = A[i]
.... .... i = i-1
.... A[i+1] = key
146
Wat is de invariant van insertion sort?
Voorafgaand aan iteratie k>_1 van de for-opdracht bevat de subarray A[1...k] de elementen die in A[1...k] zaten, maar dan gesorteerd.
147
ARRAY-SOM(A)
som = 0
teller = 0
while teller < A.length
som = som + A[teller]
teller = teller + 1
return som
148
Dingen die je optelt
Termen
149
Dingen die je vermenigvuldigt
factoren
150
Als de objecten in een rij getallen zijn, dan is een reeks...
de sommatie van de termen van de rij.
151
Lege sommatie
Een sommatie van bijv i=1 tot i=0. Uitkomst is 0.
152
truc van Gauss
SOM(i=1, n) van i is gelijk aan
(n(n+1)) / 2
153
Asymptotic efficiency
How the running time of an algorithm increases with the sice of the input.
154
O-notation
Characterizes an upper bound on the asymptotic behavior of a function, based on the highest-order term.
155
Omega-notation
Characterizes a lower bound on the asymptotic behavior of function
156
O-notation (formal)
O(g(n)) = { f(n): there exists positive consonants c and n0 such that 0<_f(n)<_gc(n) for all n>_n0}
157
Omega-notation (formal)
Omega(g(n)) = {f(n): there exist positive consonants c and n0 such that 0<_cg(n)<_f(n) for al n>_n0}
158
Theta-notation (formal)
Theta(g(n)) = {f(n): there exists positive consonants c1, c2 and n0 such that 0<_c1g(n)<_f(n)<_c2g(n) for all n>_n0}
159
kleine o-notatie
o(g(n)) = {f(n): for any positive constant c>0 there exists a constant n0>0 such tat 0<_f(n)<_cg(n) for all n>_n0}
160
kleine omega-notatie
omega(g(n)) = {f(n): for any positive constant c>0, there exist a constant n0>0 such that 0<_cg(n)_n0}
161
f(n) = THETA(g(n)) en g(n) = THETA(h(n)) imply
f(n) = THETA(h(n))
162
f(n) = O(g(n)) and g(n) = O(h(n)) imply
f(n) = O(h(n))
163
f(n) = OMEGA(g(n)) and g(n) = OMEGA(h(n)) imply
f(n) = OMEGA(h(n))
164
f(n) = o(g(n)) and g(n) = o(g(n)) imply
f(n) = o(h(n))
165
f(n) = omega(g(n)) and g(n)= omega(h(n)) imply
f(n)= omega(h(n))
166
Reflecivity: f(n) =
THETA or O or OMEGA (f(n))
167
What is the upper bound on the worst case running time of merge sort & heap sort?
O(n lg n)
168
What is the upper bound of the average running time of quicksort?
O(n lg n)
169
Any comparison algorithm requires ... comparisons in the worst case.
OMEGA(n lg n)
170
Counting sort assumes that each of the n input elements is...
an integer in the range 0 to k for some positive integer k.
171
Counting sort runs in ... time.
THETA (n+k)
172
When k=O(n), counting sort runs in ... time.
THETA(n)
173
What is the average-case running time of bucket sort?
O(n)
174
Eenpuntsregel
SOM(i=p, p) van a.i = a.p
175
Hoe bereken je makkelijk het resultaat van een sommatie als f(i) linear is?
(aantal elementen * (eerste + laatste)) / 2
176
b^a * b^c ==
b^(a+c)
177
b^ (a*c) ==
(b^a)^c of
(b^c)^a
178
(b^a) / (b^c) ==
b ^(a-c) of
b^a * b^-c
179
b^(log.b c * log.c b) ==
b^1
180
log.b c * log.c b =
1
181
a^(log.b c) ==
c^(log.b a)
182
Termenverdeling: exponentieel
n in de exponent
183
Termverdeling: logaritmisch
een macht van lg n
184
Termverdeling: polynomiaal
een macht van n
185
Termverdeling relatie:
logaritmisch < polynomiaal < exponentieel
186
Wat is de formule voor de telescoopsom?
SOM (k=1, n) van a.k - a.(k-1)
a.n - a.0
(want elke term wordt precies 1x toegevoegd en weggehaald)
187
Wat is een recurrente betrekking?
Een functie-vorm die de waarde van de functie voor input n in termen van de waarde van de functie voor input m
188
in place sorteren
Gebruik niet meer dan een constante hoeveelheid geheugen buiten de array.
189
Wat zijn 6 comparison sort algoritmes?
1) Insertion sort
2) Selection sort
3) Bubble sort
4) Merge sort
5) Heapsort
6) Quicksort
190
Noem de 3 lineare sorteeralgoritmen
1) Counting sort
2) Radix sort
3) Bucket sort
191
Het Master theorem is alleen toepasbaar als geldt...
T(n) = a* T(n/b) + f(n)
192
Welke aannname doet Counting Sort?
Alle n keys komen uit een (kleine) verzameling
193
Welke aanname doet Bucket sort over de input?
De n input-keys zijn uniform verdeeld over [0, 1)
194
What is the worst-case running time of Quicksort on an input array of n numbers?
THETA(n^2)
195
How is an array stored?
As a contiguous sequence of bytes in memory.
196
If the first element of an array has index s, the array starts at memory adress a and each element occupies b bytes, then the i-th element occupies bytes ... through ...
Bytes a+b(i-s) through a+b(i-s+1)-1
197
Pointer
Something that is used to occupy a spot in an array when the objects in the array have varying size. The pointers all have the same size, but refer to the actual object. This way the adress of an element in the array can still easily be calculated
198
Block representation
The matrix is divided into blocks and each block is stored contiguously.
199
In a stack, the element deleted from the set is...
the one most recently inserted.
200
In a queue, the element deleted is...
the one that has been in the set for the longest time.
201
Where is a new element enqueued in a queue?
At the tail.
202
What is at the head of a queue?
The element that has been there the longest and that will be dequeued next.
203
How much time do the enqueue and dequeue operations take?
O(1)
204
ENQUEUE(Q,x)
Q[Q.tail] = x;
if Q.tail == Q.size
... Q.tail =1
else
... Q.tail ++
205
DEQUEUE(Q,x)
x = Q[Q.head]
if Q.head == Q.size
... Q.head = 1
else
... Q.head ++
return x
206
Linked list
A data structure in which the objects are arranged in linear order. Order is determined by pointers in each object.
207
Search lists
Another name for linked lists.
208
Each element of a doubly linked list is...
an object with an attribute key and two pointer attributes: next and prev.
209
(linked lists) if x.prev = NIL, then...
the element x has no predeccesor and is therefore the head.
210
(linked lists) if x.nect = NIL, then,..
the element x has no successor and is therefore the tail, the last element.
211
Singly linked list
Each element has a next pointer but no prev pointer.
212
Sorted list
The linear order of the list corresponds to the linear order of keys stored in elements of the list.
213
Unsorted list
The elements can appear in any order.
214
Circular list
The prev pointer of the head of the list points to the tail.
215
What does the List-prepend procedure do?
When the key attirbute of an element x is already set, this procedure adds x to the front of the list.
216
What is the running time of Heapsort?
O(nlgn)
217
Does heapsort sort in place?
Yes.
218
ADS
Abstracte datastructuur
219
Abstracte datastructuur
Geeft aan wat het kan en niet hoe. Gebruik is gescheiden van implementatie.
220
Hoe bekijk je het bovenste element zonder die te verwijderen in een stack?
PEEK()
221
Hoe check je of een stack leeg is?
STACK_EMPTY()
222
Hoe krijg je de index van het bovenste element in een stack?
S.top
223
IN wat voor tijd gebeuren de operaties op een stack?
Constante tijd
224
Op welke twee manieren kun je een stack implementeren?
Als array of als list.
225
Wanneer is er stack overflow?
Als top = s-1 met s=size.
226
HOeveel kost een verdubbelinng van de array bij stackoverflow?
Bij een size=c kost dat O(c)
227
Hoeveel tijd kost een push operatie in een stack van een array gemiddeld?
O(1)
228
Geamortiseerde tijd
Gemiddeld O(1)
229
Hoeveel tijd kosten de operaties op een queue?
Constante tijd
230
OP welke manieren kun je een queue implementeren?
Als array of als linked list.
231
Hoe implementeer je een queue als array?
Gebruik tellers head en tail
232
Wat is ENQUEUE() bij queau implementatie als array?
Q[tail++] = x
233
Wat is DEQUEUE() bij queue implementatie als array?
return Q[head++]
234
Wat is COUNT() bij queue implementatie als array
return (tail-head)
235
Wat doe je bij stackoverflow bij een queue die geïmplementeerd is als array?
Verdubbel de grootte van de array en stapel alle elementen over van de eerste naar de tweede array. Gemiddeld O(1) tijd.
236
Wat is de dictionary in CLRS?
Een dynamische verzameling objecten met de operaties INSERT(S, x), DELETE(S, x) en SEARCH(S, k).
237
INSERT(S, x) bij dictionary
voeg element x toe aan dictionary S
238
DELETE(S, x)
verwijder element x uit dictionary S
239
SEARCH(S, k) dictionary
return element x met key k uit dictionary S (of NIL)
240
element x in dictionary volgens CLRS
een pointer naar een object. Als er naar een element geen pointer meer bestaat, dan is het element weg!
241
MINIMUM(S) en MAXIMUM(S) bij dynamische verzameling S
returnt het element met de kleinste of grootste key.
242
SUCCESSOR(S,x) of PREDECESSOR(S, x) in dynamische verzameling
returnt element met kleinste key >_ x.key of grootste key <_ x.key.
243
Statische datastructuur
Data zit in een array, met vaste en gereserveerde omvang en directe toegang.
244
Dynamische datastructuur
Er is structuur aangebracht met pointers, flexibele omvang, maar indirecte toegang
245
Directe toegang
A[i] opvragen kost O(1) tijd. Elementen zijn aaneengesloten opgeslagen met bekende grootte.
246
Indirecte toegang
Maak objecten (=nodes) met een key en koppel ze aan elkaar met verwijzingen (prev en next)
247
(binary) heap datastructure
An array object that we can view as a nearly complete binary tree. Each node of the tree corresponds to an element in the arrya,
248
Max-heap property
In a max-heap: the property that for every node i other than the root,
A[PARENT(i)] => A[i]
249
Min-heap
Organized such that for every node i other than the root,
A[PARENT(i)] <= A[i]
250
What kind of heaps does the heapsort algorithm use?
Max-heaps.
251
In what time does the MAX-HEAPIFY procedure run?
O(lg n)
252
In how much time does the BUILD-MAX-HEAP procedure run?
linear time, so O(n)
253
What does MAX-HEAPIFY assume?
That the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps, but that A[i] might be smaller than its children (thus violating the max-heap property)
254
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.
255
Can you build a max-heap from an unordered array in linear time?
Yes
256
HEAPSORT(A,n)
BUILD-MAX-HEAP(A,n)
for i=n downto 2
... Exchange A[1] with A[i]
... A.heap-size = A.heap-size - 1
... MAX-HEAPIFY(A,1)
257
Priority queue
A data structure for maintaining a set S of elements, each with an associated value called a key.
258
What operations does the MAX-PRIORITY QUEUE support?
INSERT(S, x, k)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S,x,k)
259
handles
additional information stored in the objects and heap elements that give enough information to perform the mapping.
260
PARENT(i) of heap node i
return FLOOR(i/2)
261
LEFT(i) of node i in heap
return 2i
262
RIGHT(i) of node i in heap
return 2i+1
263
Hoe hangt de heap-hoogte af van het aantal keys n?
h = FLOOR(lg n)
264
idee van MAX-HEAP-INSERT
een key toevoegen aan een heap
265
A.length bij heap implementatie als array
De lengte van de array A.
266
A.heap-size bij de heap implementatie als array
Het aantal elementen van de heap in A
267
Waarvoor gebruik je MAX-HEAP-INSERT?
Om een key toe te voegen aan een heap.
268
Wanneer gebruik je MAX-HEAPIFY?
Om de max-heap eigenschap te herstellen.
269
Wanneer gebruik je BUILD-MAX-HEAP?
Als je een max-heap van een array wil maken.
270
Wat doet HEAPSORT?
Sorteert een gegeven array met behulp van een heap.
271
MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if (l<=A.heap-size and A[l]>A[i])
{grootste = l}
else {grootste = i}
if (r<= A.heap-size and A[r] > A[grootste])
{grootste = r}
if (grootste != A[i])
{ wissel A[i] en A[grootste]
MAX-HEAPIFY(A, grootste) }
272
Hoeveel van de n elementen in een heap zijn leaves?
De laatste CEILING(n/2) elementen.
273
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = FLOOR(A.length/2) down to 1
{MAX-HEAPIFY(A, i) }
274
Hoe sorteer je een array A met het heap-idee?
1) Maak van A een heap met BUILD-MAX-HEAP.
2) Doe herhaaldelijk:
a) De grootste staat vooraan, wissel A[1] en A[A.heap-size].
b) Verlaag A.heap-size met 1.
c) Doe MAX-HEAPIFY(A,1).
275
HEAPSORT(A)
BUILD-MAX-HEAP(A)
for (i=A.length downto 2)
{ wissel A[1] en A[i]
A.heap-size = A.heap-size-1
MAX-HEAPIFY(A, 1) }
276
What is the average time to search for an element in a hash table?
O(1)
277
When do hash tables become an effective alternative to directly adressing an array?
When the number of keys actually stored is small relative to the total number of possible keys.
278
Collision
An event in which more than one key map to the same array index.
279
Direct adressing
A technique that works well when the universe U of keys is reasonably small.
280
Direct-adress table
An array used to represent a dynamic set in which each element has a distinct key drawn from the universe U.
Denoted by T[0:m-1]. Each position corresponds to a key.
281
Slot k in direct-adress table
Points to an element in the set with key k. T[k] = NIL if the set contains no element with key k.
282
Independent uniform hash function
An ideal hash function that has an output h(k) that is randomly and independently chosen uniformly from the range {0, 1, ..., m-1} for each possible input k in domain U, and after that each h(k) call returns that same value.
283
Random oracle
Another term for the independent uniform hash function.
284
Chaining
Each nonempty slot points to a linked list and all the elements that hash to the same slot go into that slot's linked list.
Slot j contains a pointer to the head of the list of all stored elements with hash value j.
285
CHAINED-HASH-INSERT(T,x)
LIST-PREPEND(T[h(x.key)], x)
286
CHAINED-HASH-SEARCH(T,k)
return LIST-SEARCH(T[h(k)], k)
287
CHAINED-HASH-DELETE(T,x)
LIST-DELETE(T[h(x.key)],x)
288
Given a hash table T with m slots that stores n elements, the load factor alpha for T is...
n/m
the average number of lements stored in a chain.
289
Random variable Z
How many elements appear in the list prior to the element being searched for.
290
Static hashing
Trying to provide a single hash function that works well on any data.
291
Division method (for creating hash functions)
Maps a key k into one of m slots by taking the remainder of k/m.
h(k) = k mod m
292
Multiplication method for creating hash functions
Multiply the key k by a constant A in range 0
293
Wat bepaalt vooral de average-case tijd bij hashen?
Of de hash-functie de keys uniform verdeelt
294
Hoe kan je een search tree gebruiken?
Als een dictionary of een priority queue.
295
Hoe snel zijn de worst-case operaties op een searchtree?
THETA (lg n)
296
Als een zoekboom een lineare ketting van n nodes is, dan lopen de operaties in ... tijd.
THETA(n)
297
Wat heeft elke node in een binaire zoekboom?
Een key, satellite data, left right and p (pointer to parent).
298
For een node x in een binaire zoekboom, de keys in de linker subtree zijn
<= x.key
299
In een binaire zoekboom zijn de keys van de rechter-subboom van key x..
=> xkey.
300
Telt de wortel van een binare zoekboom mee in de hoogte?
Nee.
301
Wat doet INORDER-TREE-WALK(x)?
Print de key van de wortel van een subboom na zn linker subboom en zonder zn rechtersubboom. Is recursief.
302
INORDER-TREE-WALK(x)
if x!= NIL
... INORDER-TREE-WALK(x.keft)
print(x.key)
INORDER-TREE-WALK(x.right)
303
HOeveel tijd kost INORDER-TREE-WALK(x) ?
Lineare tijd.
304
TREE-SEARCH(x,k)
if x==NIL or k == x.key
{ return x}
if k
305
Wat doet de TREE-SEARCH(x,k) procedure?
Met een pointer x naar de wortel van een subtree en een key k geeft deze procedure de pointer naar een node met key k, als die bestaat in de subtree.
306
ITERATIVE-TREE-SEARCH(x,k)
while x != NIL and k != x.key
{ if k
307
TREE-MINIMUM(x)
while x.left != NIL
{ x = x.left}
return x
308
TREE-MAXIMUM(x)
while x.right != NIL
{ x = x.right}
return x
309
Hoe snel zijn TREE-MINIMUM(x) en TREE-MAXIMUM(x)?
O(h) voor hoogte h
310
Successor of a node (in a binary (sub)tree)
The next node visited in an inorder tree walk.
311
TREE-SUCCESSOR(x)
if x.right != NIL
{ return TREE-MAXIMUM(x.right)}
else
{ y = x.p
while y != NIL and x == y.right
{ x = y
y = y.p}
}
return y
312
TREE-INSERT(T,z)
x = T.root
y = NIL
while (x!=NIL)
{ y = x
if z.key
313
Wat zijn de 3 case bij het verwijderen van een node z uit een binaire zoekboom T?
1) Z heeft geen kinderen. Dan vervang je z met NIL als kind van zn parent.
2) Z heeft 1 kind. Dan neemt dat kind de plaats van z in en wordt het kind van z's ouder.
3) Z heeft 2 kinderen. Z's opvolger y neemt dan z's positie in. De rest van de rechtersubboom wordt subboom van y en de linkersubboom ook.
314
TRANSPLANT(T, u , v)
if u.p == NIL {T.root = v}
elif u == u.p.left {u.p.left = v}
else {u.p.right = v}
if v != NIL {v.p = u.p}
315
Wat doet TRANSPLANT(T, u, v)
Vervangt een subboom geworteld in node u met de subboom geworteld in node v.
316
TREE-DELETE(T,z)
if z.left == NIL {TRANSPLANT(T,z,z.right)}
elif z.right == NIL {TRANSPLANT(T,z,z.left)}
else {y = TREE-MINIMUM(z.right)
if y != z.right
{ TRANSPLANT(T,y,y.right)
y.right = z.right
y.right.p = y}
TRANSPLANT(T,z,y)
y.left = z.left
y.left.p = y
}
317
simple path
all vertices are distinct
318
cycle in directed graph
A path where v.0 = v.k (with k nodes) that contains at least one edge
319
acyclic graph
graph without simple cycles
320
connected graph
if every vertex is reachable from all other vertices
321
strongly connected graph
every two vertices are reachable from another (directed)
322
forest
acyclic undirected graph
323
(free) tree
connected acyclic undirected graph
324
dag
directed acyclic graph
325
rooted tree
a free tree in which one of the vertices is distinguished from the others, namely the root.
326
Hoeveel kost retrieval in de SortedDictionary klasse?
O(log n)
327
Welke twee klassen hebben vergelijkbare object modellen en O(log n) retrieval tijd?
SortedDictionary en
SortedList
328
In welke twee aspecten verschillen de SortedDictionary en de
SortedList klasse?
Het geheugengebruik en de snelheid van invoegen en verwijderen.
329
Wat is het verschil in geheugengebruik tussen SortedDictionary en
SortedList ?
SortedList gebruikt minder geheugen dan SortedDictionary.
330
Wat is het verschil in snelheid van invoegen en verwijderen voor ongesorteerde data tussen de SortedDictionary en de
SortedList ?
SortedDictionary is met O(log n) sneller dan SortedList met O(n).
331
Welke van SortedDictionary en SortedList is sneller als het gaat om gesorteerde data invoegen en verwijderen?
SortedLIst
332
Boom
Een verbonden, a-cyclische, ongerichte graaf.
333
Graaf
Een paar (V,E) met
V= een verzameling knopen
Bij ongericht
E = een verzameling van verzamelingen knopen: { {u,v} | u,v in V AND u != v}"
Bij gericht:
E = een binaire relatie E subset V x V, verzameling geordende paren {(u,v) | u,v in V}
334
Binaire zoekboom
Een binaire boom zodat elke knoop een waarde/key bevat en voor alle knopen in het linkerkind y van knoop x geldt y.key<=x.key en voor alle knopen z in rechterkind van x geldt z.key>=x.key.
335
Diepte van knoop x in binaire zoekboom
De aftsnad vanaf de root met root=0.
336
Hoogte van knoop x in een binaire zoekboom
De lengte van het langste pad van x naar een leaf.
337
Wat is de hoogte van een lege boom?
-1
338
Hoeveel knopen kun je maximaal kwijt in een binaire zoekboom met hoogte h?
maximaal 2^(h+1) -1 knopen
339
Een boom met hoogte h bevat tenminste ... keys.
h+1
340
Een boom met hoogte h bevat maximaal ... keys
2^(h+1)-1
341
Een boom met n knopen bevat precies ... NIL pointers.
n+1
342
In een niet-lege boom is het aantal knopen met 2 kinderen gelijk aan...
het aantal leaves - 1
343
Stappen bij inductiebewijs dat P(B) geldt voor alle binaire bomen B.
Basis: TB is dat P(B) geldt als B een lege boom is.
Inductie: TB is dat P(T.x) waar is als P(T.x.l) en P(T.x.r) waar zijn.
344
HOe kun je de keys in een binaire zoekboom op volgorde printen?
Roep INORDER-TREE-WALK(T.root) aan
345
Wat is de complexiteit van INORDER-TREE-WALK(B.root)?
THETA(n) als k(TB.root) = n
346
De predecessor subgraaf G.pi is een breadth-first boom als...
V.pi de knopen bevat die in G bereikbaar zijn vanuit s.
G een uniek simpel pad van s naar v bevat voor alle v in V.pi wat ook een kortste pad is van s naar v.
347
tree edges
kant (u,v) als v ontdekt is vanuit u
348
back edges
kant (u,v) als v voorouder van u is, maar niet ontdekt is vanuit u.
349
forward edges
kant (u,v) als v afstammeling van u is maar niet ontdekt via u.
350
Hoe heet een edge als het geen tree, back of forward edge is?
cross edge
351
Op welke 2 standaard manieren kan een graaf gerepresenteerd worden?
1) Als een adjency matrix
2) Als een collectie van adjency lijsten
352
Adjacency list representation of graph G
Consists of an array Adj of |V| lists, one for each vertex.
For each u in V the adjacency list contains all vertices v such that there is an edge (u,v) in E.
353
Adjancy-matrix representation of graph G=(V,E):
consists of a |V| x |V| matrix A = (aij...) such that
aij = { 1 if (i,j) in E
{ 0 else
354
How much time does finding an edge in the Adjacency-matrix representation take?
THETA(v^2)
355
BFS(G,s)
foreach (vertex u in G.V - {s})
{ u.color = WHITE; u.d = infinite; u.pi = null;}
s.color = GRAY;
s.d = 0;
s.pi = null;
Q = empty;
ENQUEUE(Q,s)
while (Q != empty)
{ u = DEQUEUE(Q);
foreach (vertex v in G.Adj[u])
{ if (v.color == WHITE)
{ v.color = GRAY; v.d = u.d+1; v.pi = u; ENQUEUEU(Q,v); }
}
}
u.color = BLACK;
356
Predecessor subgraph of G=(V,E) with source node s:
G.pi = (V.pi, E.pi) where
V.pi = {v in V: v.pi != null} union with {s}
E.pi = {(v.pi, u): v in V.pi -- {s}
357
PRINT-PATH(G,s,v)
if (v==s) {print s;}
elif (v.pi = null) {print"no path exists from s to v"}
else PRINT-PATH(g,s,v.pi) {pint v}
358
DFS(G)
foreach (vertex u in G.v)
{ u.color = WHITE; u.pi = null; }
time = 0;
foreach(vertex u in G.v)
{if (u.color == WHITE)
{DFS-VISIT(G,u)}}
359
DFS-VISIT(G,u)
time ++;
u.d = time;
u.color = GRAY;
foreach (vertex v in G.Adj[u])
{ if (v.color == WHITE)
{ v.pi = u; DFS-VISIT(G,v)} }
time ++;
u.f = time;
u.color = BLACK;
360
What is the running time of DFS?
THETA(V+E)
361
The wiring problem
Given a connected undirected graph G=(V,E) with weights for each edge, find an acyclic subset T of E that connects all vertices.
362
Spanning tree
An acyclic graph that connects all vertices of another graph and forms a tree.
363
Minimum-spanning tree problem
The problem of finding the spanning tree of a graph
364
What are 2 ways to solve the minimum-spanning tree problem?
1) Kruskal's algorithm
2) Prim's algorithm
365
What is the running time of Kruskal's & Prim's algorithm?
O(E lg V)
366
When does Prim's algorithm run in O( E + V lg V)?
(faster than usual)
Whenever E grows asymptotically faster than v.
367
GENERIC-MST(G,w)
A = empty;
while A does not form a spanning tree
{ find an edge (u,v) that is safe for A;
A = union of A and set of (u,v)}
return A
368
Safe edge
Edge that can be safely added to the minimum spanning tree without violating the loop invariant.
369
When does an edge (u,v) cross a cut (S,V-S) of a graph?
When one node of the edge belongs to S and the other belongs to V-S.
370
When does a cut respect a set A of edges?
If no edge in A crosses the cut.
371
When is an edge (u,v) a light edge crossing a cut?
If its weight is the minimum of any edge crossing the cut.
372
How does Kruskal's algorithm work?
Set A is a forest whose vertices are all those of the given graph. Safe edge added to A is always a lowest-weight edge in the graph that connects two distinct nodes.
373
How does Prim's algorithm work?
Set A always forms a single tree, starts from arbitrary root vertex r and grows until it spans all the vertices in V. A safe edge added to A is always a lowest-weight edge connecting the tree to a vertex not in the tree.
374
What do both Kruskal's and Prim's algorithm assume?
That the input graph is connected and represented by adjacency lists.
375
Single-source shortest path problem
Find a shortest path from a given source vertex s in V to every vertex v in V (for a given graph)
376
Shortest path
Cannot contain negative-weight cycle, or positive-weight cycles. Only 0-weight cycles.
377
Relaxing an edge (u,v)
Testing whether going through vertex u improves the shortest path to vertex v found so far. If so: update v.d and v.pi.
378
Critical path
A longest path through the DAG, corresponding to the longest time to perform a sequency of tasks.
379
What does Dijkstra's algorithm do & require?
It solves the single-source shortest path problem on a weighted, directed graph G = (V,E), but requires non-negtative weights on all edges.
380
-
Key Links
-
Subjects
-
Company
-
Find Us
-
