Datastructures Flashcards
Randomized algorithm
An algorithm whose behavior is not only determined by the input, but also by the values by a random number generator.
Give the formal definition of the sorting problem
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.
The instance of a problem consists of…
the input needed to compute a solution to the problem.
When is an algorithm for a computational problem correct?
When it halts for every problem instance and outputs the correct solution.
What does n! denote?
The factorial function.
For n=6, n! = 6 x 5 x 4 x 3 x 2 x 1
data structure
A way to store and organize data in order to facilitate access and modification.
How much time does the algorithm insertion sort take to sort n items?
c1 * n^2
with c1 = constant
How much time does the algorithm merge sort take to sort n items?
c2 * n * log2(n)
with c2 = constant
keys
the numbers to be sorted in the sorting problem
What is the form of the input in the sorting problem?
An array with n elements.
satellite data
The data that the input keys are associated with.
record
The key and the satellite data.
insertion sort
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.
What are the 3 things you need to show in a loop invariant?
1) initialization
2) maintenance
3) termination
What are objects composed of?
attributes
Analyzing an algorithm
Predicting the resources an algorithm requires.
RAM
Random-Access Machine
What 3 instructions does the RAM model contain?
1) arithmetic
2) data movement
3) control
What are arithmetic instructions? (7)
add, subtract, multiply, divide,
remainder, floor, ceiling
What are data movement instructions? (3)
load, store, copy
What are control instructions?
conditional and unconditional branch, subroutine call and return.
What are the data types in the RAM model?
integer, floating point and character
How do we assume integers are represented as data?
As c * log2 (n) bits
with c = a constant bigger than or equal to 1.
DIvide-and-conquer method
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.
Recusive algorithm
An algorithm that calls itself repeatedly to solve a related problem.
Permutatie
Ordening. Aantal is gelijk aan de factorial.
Postconditie
Beschrijft wat het betekent voor de output om correct te zijn.
Conditie C
De while/if/for opdracht
Body B
Wat er in de loop staat.
Terminatie T
De return opdracht van algoritme.
Theta-notation means…
Roughly proportional
When do we consider one algorithm to be more efficient than another?
When its worst case running time has a lower order of growhth.
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.
Harmonische sommatie
Convergeert monotoon naar nul, maar bereikt 0 nooit.
Inductieve inferentie
De redeneermethode waarmee je uit een aantal voorbeelden een algemene regels probeert op te stellen. Niet logisch.
Deductieve inferentie
Een redeneermethode die leidt tot logisch geldende conclusies.
PROP
De verzameling propositielogsiche formules.
Rekenkundige reeks
Een sommatie van opeenvolgende termen met een constant verschil.
Meetkundige reeks
Een sommatie van opeenvolgende termen met een constante verhouding.
Harmonische reeks
Voor positieve, gehele n is het nde harmonishe getal de som van 1/1, 1/2, 1/3… tot 1/n.
Lineariteit in sommaties
De sommatie van (ca.k + b.k) is gelijk aan
c de sommatie van a.k + de sommatie van b.k
De sommatie van kwadraten is gelijk aan…
(n(n+1)(2n+1) ) / 6
De sommatie van n^3 is gelijk aan…
(n^2 * (n+1)^2) / 4
Geometrische reeks
De sommatie 1 + x + x^2 + x^3 + x^… + x^n
De geometrische sommatie is gelijk aan…
(x^(n+1) - 1) / (x-1)
When is a function f(n) monotonically increasing?
If m <_ n implies f(m) <_ f(n).
When is a function f(n) monotonically decreasing?
If m<n implies f(m) > f(n).
When is a function f(n) strictly increasing?
If m < n implies f(m) < f(n).
When is a function f(n) strictly decreasing?
If m< n implies f(m) > f(n).
Wat is |x|?
The greatest integer less than or equal to x.
Wat is |- x -|?
The least integer greater than or equal to x.
What property do the floor and ceiling function have?
They are monotonically increasing.
Floor & ceiling property:
For any integer n, we have
|n| = n = |- n -|
Floor & ceiling property.
For any real number x, we have
x-1 < |x| <_ x <_ |-x-| < x+1
|-x| ==
minus |-x-|
minus |x| ==
|- -x -|
For any real number x >_ 0 and integers a,b > 0, we have
|- (|- x/a -|) / b -| =…
|- x / ab -|
For any real number x>0 and integers a,b >0, we have
| (|_ x/a _|) / b _| ==
|_ x / ab _|
For any real number x>0 and integers a,b>0, we have:
|- a/b -| <_ …
(a + (b-1)) / b
For any real number x>0 and integers a,b>0, we have:
|_ a/b | > …
(a - (b-1)) / b
For any integer n and real number x, we have:
|_ n+x _| ==
n + |x|
For any integer n and real number x, we have:
|- n+x -| ==
n + |-x-|
For any integer a and any positive integer n, the value a mod n is…
the remainder of the quotient a/n.
a mod n ==
a - n |_ a/n _|
If (a mod n) = (b mod n), we write…
and say…
a = b (mod n)
a is equivalent to b, modulo n.
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)
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.
A polynomial is asymptotically positive if and only if…
a.d > 0
For an asymptotically positive polynomial p(n) of degree d, we have p(n) ==
THETA (n^d)
For any real constant a>_0, the function n^a is …
monotonically increasing.
For any real constant a<_0, the function n^a is…
Monotonically decreasing.
We say that a function f(n) is polynomially bounded if…
f(n) == O (n^k) for some constant k.
For all real a>0, m and n, we have:
a^0 =
1
For all real a>0, m and n, we have:
a^1 =
a
For all real a>0, m and n, we have:
a^(-1) =
1/a
For all real a>0, m and n, we have:
(a^m) ^n =
a ^ mn
or
(a^n) ^m
For all real a>0, m and n, we have:
(a^m)(n^m) =
a^(m+n)
For all n and a>_1, the function a^n is…
monotonically increasing in n
We assume 0^0 =
1
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).
Any exponential function with a base strictly greater than 1 grows…
faster than a polynomial functino.
For all real x, we have
e^x =
1 + x + ((x^2)/2!) + ((x^3)/3!) + …. =
SUM(i=0, infinity) (x^i)/i!
For all real x, we have the inequality x+1 <_ …
e^x
Equality , so z+1 = e>x, holds only when x=0.
When |x| <_ 1, we have the approximation with e^x:
1+x <_ e^x <_ 1 + x + x^2
When x->0, the approximation of e^x by x+1 is…
e^x = x + 1 + THETA(x^2)
lg n ==
log.2 n
Binary logarithm
lg n
log.2 n
Natural logarithm
ln n
log.e n
Exponentiation
lg^k n
(lg n )^k
lg^k n ==
(lg n)^k
lg lg n ==
lg(lg n)
Composition
lg lg n
lg(lg n)
For any constant b>1, the function log.b n is undefined if
n<_0
For any constant b>1, the function log.b n is strictly increasing if
n>0
For any constant b>1, the function log.b n is negative if
0 < n < 1
For any constant b>1, the function log.b n is positive if…
n>1
For any constant b>1, the function log.b n is zero if…
n=1.
For all real a>0, b>0, c>0 and n, we have…
a =
b^(log.b a)
For all real a>0, b>0, c>0 and n, we have..
log.c (ab) ==
log.c a + log.c b
For all real a>0, b>0, c>0 and n, we have…
log.b (a^n) =
n log.b a
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)
For all real a>0, b>0, c>0 and n, we have..
log.b (1/a) =
-log.b a
For all real a>0, b>0, c>0 and n, we have..
a^(log.b c) =
c^(log.b a)
Changing the base of a logarithm from one constant to another changes the value of the logarithm…
by only a constant factor.
For x>-1, the inequalites with logarithms hold…
x/(1+x) <_ ln (1+x) <_ x
A function f(n) is polylogarithmically bounded for some constant k if f(n) =…
(running time thing)
O(lg^k n)
For all real constants a>0 and b, we have…
lg.b n =
o(n^a)
The factorial n! is recursively
defined for n>_0 as
1 if n=0
n(n-1)! if n>0
Give Stirling’s approximation,
n! =
ROOT(2pi*n) * (n/e)^n * (1 + THETA(1/n))
n! = o..
o(n^n)
n! = omega(…
omega(2^n)
lg(n!) = theta(..
theta(n lg n)
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
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
golden ratio
phi
conjugate of the golden ratio
phi met een dakje erop
Phi (golden ratio) =
(1+ROOT(5)) /2
(phi)^ =
(conjugate of golden ratio)
(1-ROOT(5))/2
In golden ratios,
F.i =
(phi.i - phi.i^) / ROOT(5)
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
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.
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.
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.
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)).
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)).
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)).
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.
Watershed function
n^(log.b a)
How do you use the master method?
Determine which of the three cases applies and then write down the answer.
Geef drie voorbeelden van het verdeel-en-heers algoritme:
binair zoeken
merge sort
quicksort
What is the worst-case running time of the quicksort algorithm on an input array of n numbers?
THETA(n^2).
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.
comparison sorts
Algorithms that determine the sorted order only based on comparing input elements.
Algoritme
Een oplossing voor een computationeel probleem, gedefinieerd als een relatie tussen input en output.
Een algoritme is niet hetzelfde als een … in C#.
Een methode
Een datastructuur is niet hetzelfde als een … in C#
een object
Linear zoeken
Bij het begin beginnen en doorgaan tot het eind of totdat je x gevonden hebt.
ZOEK-LINEAR (A,x)
i=0
while i < A.length
if A[i] == x
return i
i++1
return -1
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).
Hoe werkt binair zoeken globaal?
Zet index i helemaal links en index j helemaal rechts. Zoek het midden (m). Als x<m, gooi rechterhelft weg en als x>m, gooi linkerhelft weg. Herhaal totdat i==j-1.
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
Correctheid
De juiste output bij de juiste input.
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.
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).
Hoe toon je terminatie van een loop aan?
Beargumenteer dat de variant 0 wordt.
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
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.
ARRAY-SOM(A)
som = 0
teller = 0
while teller < A.length
som = som + A[teller]
teller = teller + 1
return som
Dingen die je optelt
Termen
Dingen die je vermenigvuldigt
factoren
Als de objecten in een rij getallen zijn, dan is een reeks…
de sommatie van de termen van de rij.
Lege sommatie
Een sommatie van bijv i=1 tot i=0. Uitkomst is 0.
truc van Gauss
SOM(i=1, n) van i is gelijk aan
(n(n+1)) / 2
Asymptotic efficiency
How the running time of an algorithm increases with the sice of the input.
O-notation
Characterizes an upper bound on the asymptotic behavior of a function, based on the highest-order term.
Omega-notation
Characterizes a lower bound on the asymptotic behavior of function
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}
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}
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}
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}
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)<f(n) for all n>_n0}
f(n) = THETA(g(n)) en g(n) = THETA(h(n)) imply
f(n) = THETA(h(n))
f(n) = O(g(n)) and g(n) = O(h(n)) imply
f(n) = O(h(n))
f(n) = OMEGA(g(n)) and g(n) = OMEGA(h(n)) imply
f(n) = OMEGA(h(n))
f(n) = o(g(n)) and g(n) = o(g(n)) imply
f(n) = o(h(n))
f(n) = omega(g(n)) and g(n)= omega(h(n)) imply
f(n)= omega(h(n))
Reflecivity: f(n) =
THETA or O or OMEGA (f(n))
What is the upper bound on the worst case running time of merge sort & heap sort?
O(n lg n)
What is the upper bound of the average running time of quicksort?
O(n lg n)
Any comparison algorithm requires … comparisons in the worst case.
OMEGA(n lg n)
Counting sort assumes that each of the n input elements is…
an integer in the range 0 to k for some positive integer k.
Counting sort runs in … time.
THETA (n+k)
When k=O(n), counting sort runs in … time.
THETA(n)
What is the average-case running time of bucket sort?
O(n)
Eenpuntsregel
SOM(i=p, p) van a.i = a.p
Hoe bereken je makkelijk het resultaat van een sommatie als f(i) linear is?
(aantal elementen * (eerste + laatste)) / 2
b^a * b^c ==
b^(a+c)
b^ (a*c) ==
(b^a)^c of
(b^c)^a
(b^a) / (b^c) ==
b ^(a-c) of
b^a * b^-c
b^(log.b c * log.c b) ==
b^1
log.b c * log.c b =
1
a^(log.b c) ==
c^(log.b a)
Termenverdeling: exponentieel
n in de exponent
Termverdeling: logaritmisch
een macht van lg n
Termverdeling: polynomiaal
een macht van n
Termverdeling relatie:
logaritmisch < polynomiaal < exponentieel
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)
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<n definieert.
in place sorteren
Gebruik niet meer dan een constante hoeveelheid geheugen buiten de array.
Wat zijn 6 comparison sort algoritmes?
1) Insertion sort
2) Selection sort
3) Bubble sort
4) Merge sort
5) Heapsort
6) Quicksort
Noem de 3 lineare sorteeralgoritmen
1) Counting sort
2) Radix sort
3) Bucket sort
Het Master theorem is alleen toepasbaar als geldt…
T(n) = a* T(n/b) + f(n)
Welke aannname doet Counting Sort?
Alle n keys komen uit een (kleine) verzameling
Welke aanname doet Bucket sort over de input?
De n input-keys zijn uniform verdeeld over [0, 1)
What is the worst-case running time of Quicksort on an input array of n numbers?
THETA(n^2)
How is an array stored?
As a contiguous sequence of bytes in memory.
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
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
Block representation
The matrix is divided into blocks and each block is stored contiguously.
In a stack, the element deleted from the set is…
the one most recently inserted.
In a queue, the element deleted is…
the one that has been in the set for the longest time.
Where is a new element enqueued in a queue?
At the tail.
What is at the head of a queue?
The element that has been there the longest and that will be dequeued next.
How much time do the enqueue and dequeue operations take?
O(1)
ENQUEUE(Q,x)
Q[Q.tail] = x;
if Q.tail == Q.size
… Q.tail =1
else
… Q.tail ++
DEQUEUE(Q,x)
x = Q[Q.head]
if Q.head == Q.size
… Q.head = 1
else
… Q.head ++
return x
Linked list
A data structure in which the objects are arranged in linear order. Order is determined by pointers in each object.
Search lists
Another name for linked lists.
Each element of a doubly linked list is…
an object with an attribute key and two pointer attributes: next and prev.
(linked lists) if x.prev = NIL, then…
the element x has no predeccesor and is therefore the head.
(linked lists) if x.nect = NIL, then,..
the element x has no successor and is therefore the tail, the last element.
Singly linked list
Each element has a next pointer but no prev pointer.
Sorted list
The linear order of the list corresponds to the linear order of keys stored in elements of the list.
Unsorted list
The elements can appear in any order.
Circular list
The prev pointer of the head of the list points to the tail.
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.
What is the running time of Heapsort?
O(nlgn)
Does heapsort sort in place?
Yes.
ADS
Abstracte datastructuur
Abstracte datastructuur
Geeft aan wat het kan en niet hoe. Gebruik is gescheiden van implementatie.
Hoe bekijk je het bovenste element zonder die te verwijderen in een stack?
PEEK()
Hoe check je of een stack leeg is?
STACK_EMPTY()
Hoe krijg je de index van het bovenste element in een stack?
S.top
IN wat voor tijd gebeuren de operaties op een stack?
Constante tijd
Op welke twee manieren kun je een stack implementeren?
Als array of als list.
Wanneer is er stack overflow?
Als top = s-1 met s=size.
HOeveel kost een verdubbelinng van de array bij stackoverflow?
Bij een size=c kost dat O(c)
Hoeveel tijd kost een push operatie in een stack van een array gemiddeld?
O(1)
Geamortiseerde tijd
Gemiddeld O(1)
Hoeveel tijd kosten de operaties op een queue?
Constante tijd
OP welke manieren kun je een queue implementeren?
Als array of als linked list.
Hoe implementeer je een queue als array?
Gebruik tellers head en tail
Wat is ENQUEUE() bij queau implementatie als array?
Q[tail++] = x
Wat is DEQUEUE() bij queue implementatie als array?
return Q[head++]
Wat is COUNT() bij queue implementatie als array
return (tail-head)
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.
Wat is de dictionary in CLRS?
Een dynamische verzameling objecten met de operaties INSERT(S, x), DELETE(S, x) en SEARCH(S, k).
INSERT(S, x) bij dictionary
voeg element x toe aan dictionary S
DELETE(S, x)
verwijder element x uit dictionary S
SEARCH(S, k) dictionary
return element x met key k uit dictionary S (of NIL)
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!
MINIMUM(S) en MAXIMUM(S) bij dynamische verzameling S
returnt het element met de kleinste of grootste key.
SUCCESSOR(S,x) of PREDECESSOR(S, x) in dynamische verzameling
returnt element met kleinste key >_ x.key of grootste key <_ x.key.
Statische datastructuur
Data zit in een array, met vaste en gereserveerde omvang en directe toegang.
Dynamische datastructuur
Er is structuur aangebracht met pointers, flexibele omvang, maar indirecte toegang
Directe toegang
A[i] opvragen kost O(1) tijd. Elementen zijn aaneengesloten opgeslagen met bekende grootte.
Indirecte toegang
Maak objecten (=nodes) met een key en koppel ze aan elkaar met verwijzingen (prev en next)
(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,
Max-heap property
In a max-heap: the property that for every node i other than the root,
A[PARENT(i)] => A[i]
Min-heap
Organized such that for every node i other than the root,
A[PARENT(i)] <= A[i]
What kind of heaps does the heapsort algorithm use?
Max-heaps.
In what time does the MAX-HEAPIFY procedure run?
O(lg n)
In how much time does the BUILD-MAX-HEAP procedure run?
linear time, so O(n)
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)
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.
Can you build a max-heap from an unordered array in linear time?
Yes
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)
Priority queue
A data structure for maintaining a set S of elements, each with an associated value called a key.
What operations does the MAX-PRIORITY QUEUE support?
INSERT(S, x, k)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S,x,k)
handles
additional information stored in the objects and heap elements that give enough information to perform the mapping.
PARENT(i) of heap node i
return FLOOR(i/2)
LEFT(i) of node i in heap
return 2i
RIGHT(i) of node i in heap
return 2i+1
Hoe hangt de heap-hoogte af van het aantal keys n?
h = FLOOR(lg n)
idee van MAX-HEAP-INSERT
een key toevoegen aan een heap
A.length bij heap implementatie als array
De lengte van de array A.
A.heap-size bij de heap implementatie als array
Het aantal elementen van de heap in A
Waarvoor gebruik je MAX-HEAP-INSERT?
Om een key toe te voegen aan een heap.
Wanneer gebruik je MAX-HEAPIFY?
Om de max-heap eigenschap te herstellen.
Wanneer gebruik je BUILD-MAX-HEAP?
Als je een max-heap van een array wil maken.
Wat doet HEAPSORT?
Sorteert een gegeven array met behulp van een heap.
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) }
Hoeveel van de n elementen in een heap zijn leaves?
De laatste CEILING(n/2) elementen.
BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = FLOOR(A.length/2) down to 1
{MAX-HEAPIFY(A, i) }
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).
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) }
What is the average time to search for an element in a hash table?
O(1)
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.
Collision
An event in which more than one key map to the same array index.
Direct adressing
A technique that works well when the universe U of keys is reasonably small.
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.
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.
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.
Random oracle
Another term for the independent uniform hash function.
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.
CHAINED-HASH-INSERT(T,x)
LIST-PREPEND(T[h(x.key)], x)
CHAINED-HASH-SEARCH(T,k)
return LIST-SEARCH(T[h(k)], k)
CHAINED-HASH-DELETE(T,x)
LIST-DELETE(T[h(x.key)],x)
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.
Random variable Z
How many elements appear in the list prior to the element being searched for.
Static hashing
Trying to provide a single hash function that works well on any data.
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
Multiplication method for creating hash functions
Multiply the key k by a constant A in range 0<A<1 and extract the fractional part of kA.
Then multiply this value by m and take the floor of result.
h(k) = FLOOR(m*(kA mod 1))
Wat bepaalt vooral de average-case tijd bij hashen?
Of de hash-functie de keys uniform verdeelt
Hoe kan je een search tree gebruiken?
Als een dictionary of een priority queue.
Hoe snel zijn de worst-case operaties op een searchtree?
THETA (lg n)
Als een zoekboom een lineare ketting van n nodes is, dan lopen de operaties in … tijd.
THETA(n)
Wat heeft elke node in een binaire zoekboom?
Een key, satellite data, left right and p (pointer to parent).
For een node x in een binaire zoekboom, de keys in de linker subtree zijn
<= x.key
In een binaire zoekboom zijn de keys van de rechter-subboom van key x..
=> xkey.
Telt de wortel van een binare zoekboom mee in de hoogte?
Nee.
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.
INORDER-TREE-WALK(x)
if x!= NIL
… INORDER-TREE-WALK(x.keft)
print(x.key)
INORDER-TREE-WALK(x.right)
HOeveel tijd kost INORDER-TREE-WALK(x) ?
Lineare tijd.
TREE-SEARCH(x,k)
if x==NIL or k == x.key
{ return x}
if k<x.key
{return TREE-SEARCH(x.left, k)}
else{return TREE-SEARCH(x.right,k)}
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.
ITERATIVE-TREE-SEARCH(x,k)
while x != NIL and k != x.key
{ if k<x.key
{ x=x.left}
else {x=x.right}
}
return x
TREE-MINIMUM(x)
while x.left != NIL
{ x = x.left}
return x
TREE-MAXIMUM(x)
while x.right != NIL
{ x = x.right}
return x
Hoe snel zijn TREE-MINIMUM(x) en TREE-MAXIMUM(x)?
O(h) voor hoogte h
Successor of a node (in a binary (sub)tree)
The next node visited in an inorder tree walk.
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
TREE-INSERT(T,z)
x = T.root
y = NIL
while (x!=NIL)
{ y = x
if z.key <x.key
{x = x.left}
else{ x = x.right}
}
z.p = y
if y == NIL {T.root = z}
elif z.key<y.key {y.left = z}
else {y.right = z}
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.
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}
Wat doet TRANSPLANT(T, u, v)
Vervangt een subboom geworteld in node u met de subboom geworteld in node v.
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
}
simple path
all vertices are distinct
cycle in directed graph
A path where v.0 = v.k (with k nodes) that contains at least one edge
acyclic graph
graph without simple cycles
connected graph
if every vertex is reachable from all other vertices
strongly connected graph
every two vertices are reachable from another (directed)
forest
acyclic undirected graph
(free) tree
connected acyclic undirected graph
dag
directed acyclic graph
rooted tree
a free tree in which one of the vertices is distinguished from the others, namely the root.
Hoeveel kost retrieval in de SortedDictionary<TKey, TValue> klasse?
O(log n)
Welke twee klassen hebben vergelijkbare object modellen en O(log n) retrieval tijd?
SortedDictionary<TKey, TValue> en
SortedList<TKey, TValue>
In welke twee aspecten verschillen de SortedDictionary<TKey, TValue> en de
SortedList<TKey, TValue> klasse?
Het geheugengebruik en de snelheid van invoegen en verwijderen.
Wat is het verschil in geheugengebruik tussen SortedDictionary<TKey, TValue> en
SortedList<TKey, TValue> ?
SortedList gebruikt minder geheugen dan SortedDictionary.
Wat is het verschil in snelheid van invoegen en verwijderen voor ongesorteerde data tussen de SortedDictionary<TKey, TValue> en de
SortedList<TKey, TValue> ?
SortedDictionary is met O(log n) sneller dan SortedList met O(n).
Welke van SortedDictionary<TKey, TValue> en SortedList<TKey, TValue> is sneller als het gaat om gesorteerde data invoegen en verwijderen?
SortedLIst
Boom
Een verbonden, a-cyclische, ongerichte graaf.
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}
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.
Diepte van knoop x in binaire zoekboom
De aftsnad vanaf de root met root=0.
Hoogte van knoop x in een binaire zoekboom
De lengte van het langste pad van x naar een leaf.
Wat is de hoogte van een lege boom?
-1
Hoeveel knopen kun je maximaal kwijt in een binaire zoekboom met hoogte h?
maximaal 2^(h+1) -1 knopen
Een boom met hoogte h bevat tenminste … keys.
h+1
Een boom met hoogte h bevat maximaal … keys
2^(h+1)-1
Een boom met n knopen bevat precies … NIL pointers.
n+1
In een niet-lege boom is het aantal knopen met 2 kinderen gelijk aan…
het aantal leaves - 1
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.
HOe kun je de keys in een binaire zoekboom op volgorde printen?
Roep INORDER-TREE-WALK(T.root) aan
Wat is de complexiteit van INORDER-TREE-WALK(B.root)?
THETA(n) als k(TB.root) = n
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.
tree edges
kant (u,v) als v ontdekt is vanuit u
back edges
kant (u,v) als v voorouder van u is, maar niet ontdekt is vanuit u.
forward edges
kant (u,v) als v afstammeling van u is maar niet ontdekt via u.
Hoe heet een edge als het geen tree, back of forward edge is?
cross edge
Op welke 2 standaard manieren kan een graaf gerepresenteerd worden?
1) Als een adjency matrix
2) Als een collectie van adjency lijsten
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.
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
How much time does finding an edge in the Adjacency-matrix representation take?
THETA(v^2)
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;
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}
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}
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)}}
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;
What is the running time of DFS?
THETA(V+E)
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.
Spanning tree
An acyclic graph that connects all vertices of another graph and forms a tree.
Minimum-spanning tree problem
The problem of finding the spanning tree of a graph
What are 2 ways to solve the minimum-spanning tree problem?
1) Kruskal’s algorithm
2) Prim’s algorithm
What is the running time of Kruskal’s & Prim’s algorithm?
O(E lg V)
When does Prim’s algorithm run in O( E + V lg V)?
(faster than usual)
Whenever E grows asymptotically faster than v.
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
Safe edge
Edge that can be safely added to the minimum spanning tree without violating the loop invariant.
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.
When does a cut respect a set A of edges?
If no edge in A crosses the cut.
When is an edge (u,v) a light edge crossing a cut?
If its weight is the minimum of any edge crossing the cut.
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.
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.
What do both Kruskal’s and Prim’s algorithm assume?
That the input graph is connected and represented by adjacency lists.
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)
Shortest path
Cannot contain negative-weight cycle, or positive-weight cycles. Only 0-weight cycles.
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.
Critical path
A longest path through the DAG, corresponding to the longest time to perform a sequency of tasks.
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.
