Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Year 3 of UU > Datastructures > Flashcards

Datastructures Flashcards

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

The instance of a problem consists of…

A

the input needed to compute a solution to the problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

When is an algorithm for a computational problem correct?

A

When it halts for every problem instance and outputs the correct solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

data structure

A

A way to store and organize data in order to facilitate access and modification.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How much time does the algorithm insertion sort take to sort n items?

A

c1 * n^2
with c1 = constant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How much time does the algorithm merge sort take to sort n items?

A

c2 * n * log2(n)
with c2 = constant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

keys

A

the numbers to be sorted in the sorting problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the form of the input in the sorting problem?

A

An array with n elements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

satellite data

A

The data that the input keys are associated with.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

record

A

The key and the satellite data.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What are the 3 things you need to show in a loop invariant?

A

1) initialization
2) maintenance
3) termination

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What are objects composed of?

A

attributes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Analyzing an algorithm

A

Predicting the resources an algorithm requires.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

RAM

A

Random-Access Machine

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What 3 instructions does the RAM model contain?

A

1) arithmetic
2) data movement
3) control

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are arithmetic instructions? (7)

A

add, subtract, multiply, divide,
remainder, floor, ceiling

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What are data movement instructions? (3)

A

load, store, copy

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What are control instructions?

A

conditional and unconditional branch, subroutine call and return.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What are the data types in the RAM model?

A

integer, floating point and character

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Recusive algorithm

A

An algorithm that calls itself repeatedly to solve a related problem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Permutatie

A

Ordening. Aantal is gelijk aan de factorial.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Postconditie

A

Beschrijft wat het betekent voor de output om correct te zijn.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Conditie C

A

De while/if/for opdracht

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Body B

A

Wat er in de loop staat.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

Terminatie T

A

De return opdracht van algoritme.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

Theta-notation means…

A

Roughly proportional

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

When do we consider one algorithm to be more efficient than another?

A

When its worst case running time has a lower order of growhth.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Geef de stappen voor bewijs met inductie voor een statement als
‘Voor alle gehele getallen n>_ b geldt de eigenschap P(n)’.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

Harmonische sommatie

A

Convergeert monotoon naar nul, maar bereikt 0 nooit.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

Inductieve inferentie

A

De redeneermethode waarmee je uit een aantal voorbeelden een algemene regels probeert op te stellen. Niet logisch.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

Deductieve inferentie

A

Een redeneermethode die leidt tot logisch geldende conclusies.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

PROP

A

De verzameling propositielogsiche formules.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

Rekenkundige reeks

A

Een sommatie van opeenvolgende termen met een constant verschil.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Meetkundige reeks

A

Een sommatie van opeenvolgende termen met een constante verhouding.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

Harmonische reeks

A

Voor positieve, gehele n is het nde harmonishe getal de som van 1/1, 1/2, 1/3… tot 1/n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

Lineariteit in sommaties

A

De sommatie van (ca.k + b.k) is gelijk aan
c de sommatie van a.k + de sommatie van b.k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

De sommatie van kwadraten is gelijk aan…

A

(n(n+1)(2n+1) ) / 6

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

De sommatie van n^3 is gelijk aan…

A

(n^2 * (n+1)^2) / 4

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

Geometrische reeks

A

De sommatie 1 + x + x^2 + x^3 + x^… + x^n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

De geometrische sommatie is gelijk aan…

A

(x^(n+1) - 1) / (x-1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

When is a function f(n) monotonically increasing?

A

If m <_ n implies f(m) <_ f(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

When is a function f(n) monotonically decreasing?

A

If m<n implies f(m) > f(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

When is a function f(n) strictly increasing?

A

If m < n implies f(m) < f(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

When is a function f(n) strictly decreasing?

A

If m< n implies f(m) > f(n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

Wat is |x|?

A

The greatest integer less than or equal to x.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

Wat is |- x -|?

A

The least integer greater than or equal to x.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

What property do the floor and ceiling function have?

A

They are monotonically increasing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
52
Q

Floor & ceiling property:
For any integer n, we have

A

|n| = n = |- n -|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

Floor & ceiling property.
For any real number x, we have

A

x-1 < |x| <_ x <_ |-x-| < x+1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
54
Q

|-x| ==

A

minus |-x-|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

minus |x| ==

A

|- -x -|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
56
Q

For any real number x >_ 0 and integers a,b > 0, we have
|- (|- x/a -|) / b -| =…

A

|- x / ab -|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
57
Q

For any real number x>0 and integers a,b >0, we have
| (|_ x/a _|) / b _| ==

A

|_ x / ab _|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
58
Q

For any real number x>0 and integers a,b>0, we have:
|- a/b -| <_ …

A

(a + (b-1)) / b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
59
Q

For any real number x>0 and integers a,b>0, we have:
|_ a/b | > …

A

(a - (b-1)) / b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
60
Q

For any integer n and real number x, we have:
|_ n+x _| ==

A

n + |x|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
61
Q

For any integer n and real number x, we have:
|- n+x -| ==

A

n + |-x-|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
62
Q

For any integer a and any positive integer n, the value a mod n is…

A

the remainder of the quotient a/n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
63
Q

a mod n ==

A

a - n |_ a/n _|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
64
Q

If (a mod n) = (b mod n), we write…
and say…

A

a = b (mod n)
a is equivalent to b, modulo n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
65
Q

Given a nonnegative integer d, a polynomial in n of degree d is a function p(n) of the form…

A

p(n) = SUM(i=0, d) a.i * (n^i)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
66
Q

What are the coefficients of the polynomial
p(n) = SUM(i=0, d) a.i * (n^i)
for a nonnegative integer d?

A

The constants a.0, a…, a.d. With a.d not equal to zero.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
67
Q

A polynomial is asymptotically positive if and only if…

A

a.d > 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
68
Q

For an asymptotically positive polynomial p(n) of degree d, we have p(n) ==

A

THETA (n^d)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
69
Q

For any real constant a>_0, the function n^a is …

A

monotonically increasing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
70
Q

For any real constant a<_0, the function n^a is…

A

Monotonically decreasing.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
71
Q

We say that a function f(n) is polynomially bounded if…

A

f(n) == O (n^k) for some constant k.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
72
Q

For all real a>0, m and n, we have:
a^0 =

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
73
Q

For all real a>0, m and n, we have:
a^1 =

A

a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
74
Q

For all real a>0, m and n, we have:
a^(-1) =

A

1/a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
75
Q

For all real a>0, m and n, we have:
(a^m) ^n =

A

a ^ mn
or
(a^n) ^m

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
76
Q

For all real a>0, m and n, we have:
(a^m)(n^m) =

A

a^(m+n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
77
Q

For all n and a>_1, the function a^n is…

A

monotonically increasing in n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
78
Q

We assume 0^0 =

A

1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
79
Q

For all real constants a>1 and b, we can relate the rates of growth of polynomials and exponentials by…

A

LIM(n to infinity) of (n^b) / (a^n) = 0
and n^b = o(a^n).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
80
Q

Any exponential function with a base strictly greater than 1 grows…

A

faster than a polynomial functino.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
81
Q

For all real x, we have
e^x =

A

1 + x + ((x^2)/2!) + ((x^3)/3!) + …. =
SUM(i=0, infinity) (x^i)/i!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
82
Q

For all real x, we have the inequality x+1 <_ …

A

e^x
Equality , so z+1 = e>x, holds only when x=0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
83
Q

When |x| <_ 1, we have the approximation with e^x:

A

1+x <_ e^x <_ 1 + x + x^2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
84
Q

When x->0, the approximation of e^x by x+1 is…

A

e^x = x + 1 + THETA(x^2)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
85
Q

lg n ==

A

log.2 n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
86
Q

Binary logarithm

A

lg n
log.2 n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
87
Q

Natural logarithm

A

ln n
log.e n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
88
Q

Exponentiation

A

lg^k n
(lg n )^k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
89
Q

lg^k n ==

A

(lg n)^k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
90
Q

lg lg n ==

A

lg(lg n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
91
Q

Composition

A

lg lg n
lg(lg n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
92
Q

For any constant b>1, the function log.b n is undefined if

A

n<_0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
93
Q

For any constant b>1, the function log.b n is strictly increasing if

A

n>0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
94
Q

For any constant b>1, the function log.b n is negative if

A

0 < n < 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
95
Q

For any constant b>1, the function log.b n is positive if…

A

n>1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
96
Q

For any constant b>1, the function log.b n is zero if…

A

n=1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
97
Q

For all real a>0, b>0, c>0 and n, we have…
a =

A

b^(log.b a)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
98
Q

For all real a>0, b>0, c>0 and n, we have..
log.c (ab) ==

A

log.c a + log.c b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
99
Q

For all real a>0, b>0, c>0 and n, we have…
log.b (a^n) =

A

n log.b a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
100
Q

For all real a>0, b>0 and c>0, we have
log.b a =

A

log.c a / log.c b
or
1/ (log.a b)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
101
Q

For all real a>0, b>0, c>0 and n, we have..
log.b (1/a) =

A

-log.b a

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
102
Q

For all real a>0, b>0, c>0 and n, we have..
a^(log.b c) =

A

c^(log.b a)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
103
Q

Changing the base of a logarithm from one constant to another changes the value of the logarithm…

A

by only a constant factor.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
104
Q

For x>-1, the inequalites with logarithms hold…

A

x/(1+x) <_ ln (1+x) <_ x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
105
Q

A function f(n) is polylogarithmically bounded for some constant k if f(n) =…
(running time thing)

A

O(lg^k n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
106
Q

For all real constants a>0 and b, we have…
lg.b n =

A

o(n^a)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
107
Q

The factorial n! is recursively
defined for n>_0 as

A

1 if n=0
n(n-1)! if n>0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
108
Q

Give Stirling’s approximation,
n! =

A

ROOT(2pi*n) * (n/e)^n * (1 + THETA(1/n))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
109
Q

n! = o..

A

o(n^n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
110
Q

n! = omega(…

A

omega(2^n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
111
Q

lg(n!) = theta(..

A

theta(n lg n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
112
Q

For all n>_1 it holds that
n! =

A

ROOT(2pi*n) * (n/e)^n * e^(alpha.n)
with
1/(12n+1) < alpha.n < 1/12n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
113
Q

We define the Fibonacci numbers F.i for i>_0 as …

A

0 if i=0
1 if i=1
F.(i-1) + F.(i-2) if i>-2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
114
Q

golden ratio

A

phi

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
115
Q

conjugate of the golden ratio

A

phi met een dakje erop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
116
Q

Phi (golden ratio) =

A

(1+ROOT(5)) /2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
117
Q

(phi)^ =
(conjugate of golden ratio)

A

(1-ROOT(5))/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
118
Q

In golden ratios,
F.i =

A

(phi.i - phi.i^) / ROOT(5)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
119
Q

Substitution method in 2 steps

A

1) Guess the form of the solution using symbolic constants.
2) Use mathematical induction to show that the solution works and find the constants

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
120
Q

Master recurrence

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
121
Q

How much time does the divide-and-conquer algorithm take to solve each subproblem?

A

T(n/b) time, with n= the size of the original problem and b= the size of the subproblem.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
122
Q

What does the driving function f(n) entail?

A

The cost of dividing a problem into subproblems and the cost of combining the solution to get a final solution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
123
Q

For a>0, b>1 and T(n) = aT(n/b) + f(n), what is the first part of the master theorem?

A

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)).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
124
Q

For a>0, b>1 and T(n) = aT(n/b) + f(n), what is the second part of the master theorem?

A

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)).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
125
Q

For a>0, b>1 and T(n) = aT(n/b) + f(n), what is the third part of the master theorem?

A

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)).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
126
Q

Regularity condition for f(n) in the master theorem.

A

a f(n/b) <_ c f(n)
for some constant c<1 and all sufficiently large n.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
127
Q

Watershed function

A

n^(log.b a)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
128
Q

How do you use the master method?

A

Determine which of the three cases applies and then write down the answer.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
129
Q

Geef drie voorbeelden van het verdeel-en-heers algoritme:

A

binair zoeken
merge sort
quicksort

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
130
Q

What is the worst-case running time of the quicksort algorithm on an input array of n numbers?

A

THETA(n^2).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
131
Q

Why is quicksort often the best algorithm for sorting?

A

The expected running time is THETA(n lg n) when all numbers are distinct, and the constant factors in that notation are small.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
132
Q

comparison sorts

A

Algorithms that determine the sorted order only based on comparing input elements.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
133
Q

Algoritme

A

Een oplossing voor een computationeel probleem, gedefinieerd als een relatie tussen input en output.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
134
Q

Een algoritme is niet hetzelfde als een … in C#.

A

Een methode

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
135
Q

Een datastructuur is niet hetzelfde als een … in C#

A

een object

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
136
Q

Linear zoeken

A

Bij het begin beginnen en doorgaan tot het eind of totdat je x gevonden hebt.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
137
Q

ZOEK-LINEAR (A,x)

A

i=0
while i < A.length
if A[i] == x
return i
i++1
return -1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
138
Q

Hoelang duurt ZOEK-LINEAR (A,x) voor een bepaalde x en A.length = n?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
139
Q

Hoe werkt binair zoeken globaal?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
140
Q

BINAIR-ZOEKEN (A, x)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
141
Q

Correctheid

A

De juiste output bij de juiste input.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
142
Q

Loop invariant

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
143
Q

Hoe gebruik je inductie om een loop invariant te bewijzen?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
144
Q

Hoe toon je terminatie van een loop aan?

A

Beargumenteer dat de variant 0 wordt.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
145
Q

INSERTION-SORT (A)

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
146
Q

Wat is de invariant van insertion sort?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
147
Q

ARRAY-SOM(A)

A

som = 0
teller = 0
while teller < A.length
som = som + A[teller]
teller = teller + 1
return som

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
148
Q

Dingen die je optelt

A

Termen

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
149
Q

Dingen die je vermenigvuldigt

A

factoren

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
150
Q

Als de objecten in een rij getallen zijn, dan is een reeks…

A

de sommatie van de termen van de rij.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
151
Q

Lege sommatie

A

Een sommatie van bijv i=1 tot i=0. Uitkomst is 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
152
Q

truc van Gauss

A

SOM(i=1, n) van i is gelijk aan
(n(n+1)) / 2

153
Q

Asymptotic efficiency

A

How the running time of an algorithm increases with the sice of the input.

154
Q

O-notation

A

Characterizes an upper bound on the asymptotic behavior of a function, based on the highest-order term.

155
Q

Omega-notation

A

Characterizes a lower bound on the asymptotic behavior of function

156
Q

O-notation (formal)

A

O(g(n)) = { f(n): there exists positive consonants c and n0 such that 0<_f(n)<_gc(n) for all n>_n0}

157
Q

Omega-notation (formal)

A

Omega(g(n)) = {f(n): there exist positive consonants c and n0 such that 0<_cg(n)<_f(n) for al n>_n0}

158
Q

Theta-notation (formal)

A

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
Q

kleine o-notatie

A

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
Q

kleine omega-notatie

A

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}

161
Q

f(n) = THETA(g(n)) en g(n) = THETA(h(n)) imply

A

f(n) = THETA(h(n))

162
Q

f(n) = O(g(n)) and g(n) = O(h(n)) imply

A

f(n) = O(h(n))

163
Q

f(n) = OMEGA(g(n)) and g(n) = OMEGA(h(n)) imply

A

f(n) = OMEGA(h(n))

164
Q

f(n) = o(g(n)) and g(n) = o(g(n)) imply

A

f(n) = o(h(n))

165
Q

f(n) = omega(g(n)) and g(n)= omega(h(n)) imply

A

f(n)= omega(h(n))

166
Q

Reflecivity: f(n) =

A

THETA or O or OMEGA (f(n))

167
Q

What is the upper bound on the worst case running time of merge sort & heap sort?

A

O(n lg n)

168
Q

What is the upper bound of the average running time of quicksort?

A

O(n lg n)

169
Q

Any comparison algorithm requires … comparisons in the worst case.

A

OMEGA(n lg n)

170
Q

Counting sort assumes that each of the n input elements is…

A

an integer in the range 0 to k for some positive integer k.

171
Q

Counting sort runs in … time.

A

THETA (n+k)

172
Q

When k=O(n), counting sort runs in … time.

A

THETA(n)

173
Q

What is the average-case running time of bucket sort?

A

O(n)

174
Q

Eenpuntsregel

A

SOM(i=p, p) van a.i = a.p

175
Q

Hoe bereken je makkelijk het resultaat van een sommatie als f(i) linear is?

A

(aantal elementen * (eerste + laatste)) / 2

176
Q

b^a * b^c ==

A

b^(a+c)

177
Q

b^ (a*c) ==

A

(b^a)^c of
(b^c)^a

178
Q

(b^a) / (b^c) ==

A

b ^(a-c) of
b^a * b^-c

179
Q

b^(log.b c * log.c b) ==

A

b^1

180
Q

log.b c * log.c b =

A

1

181
Q

a^(log.b c) ==

A

c^(log.b a)

182
Q

Termenverdeling: exponentieel

A

n in de exponent

183
Q

Termverdeling: logaritmisch

A

een macht van lg n

184
Q

Termverdeling: polynomiaal

A

een macht van n

185
Q

Termverdeling relatie:

A

logaritmisch < polynomiaal < exponentieel

186
Q

Wat is de formule voor de telescoopsom?
SOM (k=1, n) van a.k - a.(k-1)

A

a.n - a.0
(want elke term wordt precies 1x toegevoegd en weggehaald)

187
Q

Wat is een recurrente betrekking?

A

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.

188
Q

in place sorteren

A

Gebruik niet meer dan een constante hoeveelheid geheugen buiten de array.

189
Q

Wat zijn 6 comparison sort algoritmes?

A

1) Insertion sort
2) Selection sort
3) Bubble sort
4) Merge sort
5) Heapsort
6) Quicksort

190
Q

Noem de 3 lineare sorteeralgoritmen

A

1) Counting sort
2) Radix sort
3) Bucket sort

191
Q

Het Master theorem is alleen toepasbaar als geldt…

A

T(n) = a* T(n/b) + f(n)

192
Q

Welke aannname doet Counting Sort?

A

Alle n keys komen uit een (kleine) verzameling

193
Q

Welke aanname doet Bucket sort over de input?

A

De n input-keys zijn uniform verdeeld over [0, 1)

194
Q

What is the worst-case running time of Quicksort on an input array of n numbers?

A

THETA(n^2)

195
Q

How is an array stored?

A

As a contiguous sequence of bytes in memory.

196
Q

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 …

A

Bytes a+b(i-s) through a+b(i-s+1)-1

197
Q

Pointer

A

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
Q

Block representation

A

The matrix is divided into blocks and each block is stored contiguously.

199
Q

In a stack, the element deleted from the set is…

A

the one most recently inserted.

200
Q

In a queue, the element deleted is…

A

the one that has been in the set for the longest time.

201
Q

Where is a new element enqueued in a queue?

A

At the tail.

202
Q

What is at the head of a queue?

A

The element that has been there the longest and that will be dequeued next.

203
Q

How much time do the enqueue and dequeue operations take?

A

O(1)

204
Q

ENQUEUE(Q,x)

A

Q[Q.tail] = x;
if Q.tail == Q.size
… Q.tail =1
else
… Q.tail ++

205
Q

DEQUEUE(Q,x)

A

x = Q[Q.head]
if Q.head == Q.size
… Q.head = 1
else
… Q.head ++
return x

206
Q

Linked list

A

A data structure in which the objects are arranged in linear order. Order is determined by pointers in each object.

207
Q

Search lists

A

Another name for linked lists.

208
Q

Each element of a doubly linked list is…

A

an object with an attribute key and two pointer attributes: next and prev.

209
Q

(linked lists) if x.prev = NIL, then…

A

the element x has no predeccesor and is therefore the head.

210
Q

(linked lists) if x.nect = NIL, then,..

A

the element x has no successor and is therefore the tail, the last element.

211
Q

Singly linked list

A

Each element has a next pointer but no prev pointer.

212
Q

Sorted list

A

The linear order of the list corresponds to the linear order of keys stored in elements of the list.

213
Q

Unsorted list

A

The elements can appear in any order.

214
Q

Circular list

A

The prev pointer of the head of the list points to the tail.

215
Q

What does the List-prepend procedure do?

A

When the key attirbute of an element x is already set, this procedure adds x to the front of the list.

216
Q

What is the running time of Heapsort?

A

O(nlgn)

217
Q

Does heapsort sort in place?

A

Yes.

218
Q

ADS

A

Abstracte datastructuur

219
Q

Abstracte datastructuur

A

Geeft aan wat het kan en niet hoe. Gebruik is gescheiden van implementatie.

220
Q

Hoe bekijk je het bovenste element zonder die te verwijderen in een stack?

A

PEEK()

221
Q

Hoe check je of een stack leeg is?

A

STACK_EMPTY()

222
Q

Hoe krijg je de index van het bovenste element in een stack?

A

S.top

223
Q

IN wat voor tijd gebeuren de operaties op een stack?

A

Constante tijd

224
Q

Op welke twee manieren kun je een stack implementeren?

A

Als array of als list.

225
Q

Wanneer is er stack overflow?

A

Als top = s-1 met s=size.

226
Q

HOeveel kost een verdubbelinng van de array bij stackoverflow?

A

Bij een size=c kost dat O(c)

227
Q

Hoeveel tijd kost een push operatie in een stack van een array gemiddeld?

A

O(1)

228
Q

Geamortiseerde tijd

A

Gemiddeld O(1)

229
Q

Hoeveel tijd kosten de operaties op een queue?

A

Constante tijd

230
Q

OP welke manieren kun je een queue implementeren?

A

Als array of als linked list.

231
Q

Hoe implementeer je een queue als array?

A

Gebruik tellers head en tail

232
Q

Wat is ENQUEUE() bij queau implementatie als array?

A

Q[tail++] = x

233
Q

Wat is DEQUEUE() bij queue implementatie als array?

A

return Q[head++]

234
Q

Wat is COUNT() bij queue implementatie als array

A

return (tail-head)

235
Q

Wat doe je bij stackoverflow bij een queue die geïmplementeerd is als array?

A

Verdubbel de grootte van de array en stapel alle elementen over van de eerste naar de tweede array. Gemiddeld O(1) tijd.

236
Q

Wat is de dictionary in CLRS?

A

Een dynamische verzameling objecten met de operaties INSERT(S, x), DELETE(S, x) en SEARCH(S, k).

237
Q

INSERT(S, x) bij dictionary

A

voeg element x toe aan dictionary S

238
Q

DELETE(S, x)

A

verwijder element x uit dictionary S

239
Q

SEARCH(S, k) dictionary

A

return element x met key k uit dictionary S (of NIL)

240
Q

element x in dictionary volgens CLRS

A

een pointer naar een object. Als er naar een element geen pointer meer bestaat, dan is het element weg!

241
Q

MINIMUM(S) en MAXIMUM(S) bij dynamische verzameling S

A

returnt het element met de kleinste of grootste key.

242
Q

SUCCESSOR(S,x) of PREDECESSOR(S, x) in dynamische verzameling

A

returnt element met kleinste key >_ x.key of grootste key <_ x.key.

243
Q

Statische datastructuur

A

Data zit in een array, met vaste en gereserveerde omvang en directe toegang.

244
Q

Dynamische datastructuur

A

Er is structuur aangebracht met pointers, flexibele omvang, maar indirecte toegang

245
Q

Directe toegang

A

A[i] opvragen kost O(1) tijd. Elementen zijn aaneengesloten opgeslagen met bekende grootte.

246
Q

Indirecte toegang

A

Maak objecten (=nodes) met een key en koppel ze aan elkaar met verwijzingen (prev en next)

247
Q

(binary) heap datastructure

A

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
Q

Max-heap property

A

In a max-heap: the property that for every node i other than the root,
A[PARENT(i)] => A[i]

249
Q

Min-heap

A

Organized such that for every node i other than the root,
A[PARENT(i)] <= A[i]

250
Q

What kind of heaps does the heapsort algorithm use?

A

Max-heaps.

251
Q

In what time does the MAX-HEAPIFY procedure run?

A

O(lg n)

252
Q

In how much time does the BUILD-MAX-HEAP procedure run?

A

linear time, so O(n)

253
Q

What does MAX-HEAPIFY assume?

A

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
Q

What does MAX-HEAPIFY do?

A

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
Q

Can you build a max-heap from an unordered array in linear time?

A

Yes

256
Q

HEAPSORT(A,n)

A

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
Q

Priority queue

A

A data structure for maintaining a set S of elements, each with an associated value called a key.

258
Q

What operations does the MAX-PRIORITY QUEUE support?

A

INSERT(S, x, k)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S,x,k)

259
Q

handles

A

additional information stored in the objects and heap elements that give enough information to perform the mapping.

260
Q

PARENT(i) of heap node i

A

return FLOOR(i/2)

261
Q

LEFT(i) of node i in heap

A

return 2i

262
Q

RIGHT(i) of node i in heap

A

return 2i+1

263
Q

Hoe hangt de heap-hoogte af van het aantal keys n?

A

h = FLOOR(lg n)

264
Q

idee van MAX-HEAP-INSERT

A

een key toevoegen aan een heap

265
Q

A.length bij heap implementatie als array

A

De lengte van de array A.

266
Q

A.heap-size bij de heap implementatie als array

A

Het aantal elementen van de heap in A

267
Q

Waarvoor gebruik je MAX-HEAP-INSERT?

A

Om een key toe te voegen aan een heap.

268
Q

Wanneer gebruik je MAX-HEAPIFY?

A

Om de max-heap eigenschap te herstellen.

269
Q

Wanneer gebruik je BUILD-MAX-HEAP?

A

Als je een max-heap van een array wil maken.

270
Q

Wat doet HEAPSORT?

A

Sorteert een gegeven array met behulp van een heap.

271
Q

MAX-HEAPIFY(A, i)

A

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
Q

Hoeveel van de n elementen in een heap zijn leaves?

A

De laatste CEILING(n/2) elementen.

273
Q

BUILD-MAX-HEAP(A)

A

A.heap-size = A.length
for i = FLOOR(A.length/2) down to 1
{MAX-HEAPIFY(A, i) }

274
Q

Hoe sorteer je een array A met het heap-idee?

A

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
Q

HEAPSORT(A)

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
Q

What is the average time to search for an element in a hash table?

A

O(1)

277
Q

When do hash tables become an effective alternative to directly adressing an array?

A

When the number of keys actually stored is small relative to the total number of possible keys.

278
Q

Collision

A

An event in which more than one key map to the same array index.

279
Q

Direct adressing

A

A technique that works well when the universe U of keys is reasonably small.

280
Q

Direct-adress table

A

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
Q

Slot k in direct-adress table

A

Points to an element in the set with key k. T[k] = NIL if the set contains no element with key k.

282
Q

Independent uniform hash function

A

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
Q

Random oracle

A

Another term for the independent uniform hash function.

284
Q

Chaining

A

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
Q

CHAINED-HASH-INSERT(T,x)

A

LIST-PREPEND(T[h(x.key)], x)

286
Q

CHAINED-HASH-SEARCH(T,k)

A

return LIST-SEARCH(T[h(k)], k)

287
Q

CHAINED-HASH-DELETE(T,x)

A

LIST-DELETE(T[h(x.key)],x)

288
Q

Given a hash table T with m slots that stores n elements, the load factor alpha for T is…

A

n/m
the average number of lements stored in a chain.

289
Q

Random variable Z

A

How many elements appear in the list prior to the element being searched for.

290
Q

Static hashing

A

Trying to provide a single hash function that works well on any data.

291
Q

Division method (for creating hash functions)

A

Maps a key k into one of m slots by taking the remainder of k/m.
h(k) = k mod m

292
Q

Multiplication method for creating hash functions

A

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))

293
Q

Wat bepaalt vooral de average-case tijd bij hashen?

A

Of de hash-functie de keys uniform verdeelt

294
Q

Hoe kan je een search tree gebruiken?

A

Als een dictionary of een priority queue.

295
Q

Hoe snel zijn de worst-case operaties op een searchtree?

A

THETA (lg n)

296
Q

Als een zoekboom een lineare ketting van n nodes is, dan lopen de operaties in … tijd.

A

THETA(n)

297
Q

Wat heeft elke node in een binaire zoekboom?

A

Een key, satellite data, left right and p (pointer to parent).

298
Q

For een node x in een binaire zoekboom, de keys in de linker subtree zijn

A

<= x.key

299
Q

In een binaire zoekboom zijn de keys van de rechter-subboom van key x..

A

=> xkey.

300
Q

Telt de wortel van een binare zoekboom mee in de hoogte?

A

Nee.

301
Q

Wat doet INORDER-TREE-WALK(x)?

A

Print de key van de wortel van een subboom na zn linker subboom en zonder zn rechtersubboom. Is recursief.

302
Q

INORDER-TREE-WALK(x)

A

if x!= NIL
… INORDER-TREE-WALK(x.keft)
print(x.key)
INORDER-TREE-WALK(x.right)

303
Q

HOeveel tijd kost INORDER-TREE-WALK(x) ?

A

Lineare tijd.

304
Q

TREE-SEARCH(x,k)

A

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)}

305
Q

Wat doet de TREE-SEARCH(x,k) procedure?

A

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
Q

ITERATIVE-TREE-SEARCH(x,k)

A

while x != NIL and k != x.key
{ if k<x.key
{ x=x.left}
else {x=x.right}
}
return x

307
Q

TREE-MINIMUM(x)

A

while x.left != NIL
{ x = x.left}
return x

308
Q

TREE-MAXIMUM(x)

A

while x.right != NIL
{ x = x.right}
return x

309
Q

Hoe snel zijn TREE-MINIMUM(x) en TREE-MAXIMUM(x)?

A

O(h) voor hoogte h

310
Q

Successor of a node (in a binary (sub)tree)

A

The next node visited in an inorder tree walk.

311
Q

TREE-SUCCESSOR(x)

A

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
Q

TREE-INSERT(T,z)

A

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}

313
Q

Wat zijn de 3 case bij het verwijderen van een node z uit een binaire zoekboom T?

A

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
Q

TRANSPLANT(T, u , v)

A

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
Q

Wat doet TRANSPLANT(T, u, v)

A

Vervangt een subboom geworteld in node u met de subboom geworteld in node v.

316
Q

TREE-DELETE(T,z)

A

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
Q

simple path

A

all vertices are distinct

318
Q

cycle in directed graph

A

A path where v.0 = v.k (with k nodes) that contains at least one edge

319
Q

acyclic graph

A

graph without simple cycles

320
Q

connected graph

A

if every vertex is reachable from all other vertices

321
Q

strongly connected graph

A

every two vertices are reachable from another (directed)

322
Q

forest

A

acyclic undirected graph

323
Q

(free) tree

A

connected acyclic undirected graph

324
Q

dag

A

directed acyclic graph

325
Q

rooted tree

A

a free tree in which one of the vertices is distinguished from the others, namely the root.

326
Q

Hoeveel kost retrieval in de SortedDictionary<TKey, TValue> klasse?

A

O(log n)

327
Q

Welke twee klassen hebben vergelijkbare object modellen en O(log n) retrieval tijd?

A

SortedDictionary<TKey, TValue> en
SortedList<TKey, TValue>

328
Q

In welke twee aspecten verschillen de SortedDictionary<TKey, TValue> en de
SortedList<TKey, TValue> klasse?

A

Het geheugengebruik en de snelheid van invoegen en verwijderen.

329
Q

Wat is het verschil in geheugengebruik tussen SortedDictionary<TKey, TValue> en
SortedList<TKey, TValue> ?

A

SortedList gebruikt minder geheugen dan SortedDictionary.

330
Q

Wat is het verschil in snelheid van invoegen en verwijderen voor ongesorteerde data tussen de SortedDictionary<TKey, TValue> en de
SortedList<TKey, TValue> ?

A

SortedDictionary is met O(log n) sneller dan SortedList met O(n).

331
Q

Welke van SortedDictionary<TKey, TValue> en SortedList<TKey, TValue> is sneller als het gaat om gesorteerde data invoegen en verwijderen?

A

SortedLIst

332
Q

Boom

A

Een verbonden, a-cyclische, ongerichte graaf.

333
Q

Graaf

A

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
Q

Binaire zoekboom

A

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
Q

Diepte van knoop x in binaire zoekboom

A

De aftsnad vanaf de root met root=0.

336
Q

Hoogte van knoop x in een binaire zoekboom

A

De lengte van het langste pad van x naar een leaf.

337
Q

Wat is de hoogte van een lege boom?

A

-1

338
Q

Hoeveel knopen kun je maximaal kwijt in een binaire zoekboom met hoogte h?

A

maximaal 2^(h+1) -1 knopen

339
Q

Een boom met hoogte h bevat tenminste … keys.

A

h+1

340
Q

Een boom met hoogte h bevat maximaal … keys

A

2^(h+1)-1

341
Q

Een boom met n knopen bevat precies … NIL pointers.

A

n+1

342
Q

In een niet-lege boom is het aantal knopen met 2 kinderen gelijk aan…

A

het aantal leaves - 1

343
Q

Stappen bij inductiebewijs dat P(B) geldt voor alle binaire bomen B.

A

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
Q

HOe kun je de keys in een binaire zoekboom op volgorde printen?

A

Roep INORDER-TREE-WALK(T.root) aan

345
Q

Wat is de complexiteit van INORDER-TREE-WALK(B.root)?

A

THETA(n) als k(TB.root) = n

346
Q

De predecessor subgraaf G.pi is een breadth-first boom als…

A

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
Q

tree edges

A

kant (u,v) als v ontdekt is vanuit u

348
Q

back edges

A

kant (u,v) als v voorouder van u is, maar niet ontdekt is vanuit u.

349
Q

forward edges

A

kant (u,v) als v afstammeling van u is maar niet ontdekt via u.

350
Q

Hoe heet een edge als het geen tree, back of forward edge is?

A

cross edge

351
Q

Op welke 2 standaard manieren kan een graaf gerepresenteerd worden?

A

1) Als een adjency matrix
2) Als een collectie van adjency lijsten

352
Q

Adjacency list representation of graph G

A

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
Q

Adjancy-matrix representation of graph G=(V,E):

A

consists of a |V| x |V| matrix A = (aij…) such that
aij = { 1 if (i,j) in E
{ 0 else

354
Q

How much time does finding an edge in the Adjacency-matrix representation take?

A

THETA(v^2)

355
Q

BFS(G,s)

A

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
Q

Predecessor subgraph of G=(V,E) with source node s:

A

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
Q

PRINT-PATH(G,s,v)

A

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
Q

DFS(G)

A

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
Q

DFS-VISIT(G,u)

A

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
Q

What is the running time of DFS?

A

THETA(V+E)

361
Q

The wiring problem

A

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
Q

Spanning tree

A

An acyclic graph that connects all vertices of another graph and forms a tree.

363
Q

Minimum-spanning tree problem

A

The problem of finding the spanning tree of a graph

364
Q

What are 2 ways to solve the minimum-spanning tree problem?

A

1) Kruskal’s algorithm
2) Prim’s algorithm

365
Q

What is the running time of Kruskal’s & Prim’s algorithm?

A

O(E lg V)

366
Q

When does Prim’s algorithm run in O( E + V lg V)?
(faster than usual)

A

Whenever E grows asymptotically faster than v.

367
Q

GENERIC-MST(G,w)

A

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
Q

Safe edge

A

Edge that can be safely added to the minimum spanning tree without violating the loop invariant.

369
Q

When does an edge (u,v) cross a cut (S,V-S) of a graph?

A

When one node of the edge belongs to S and the other belongs to V-S.

370
Q

When does a cut respect a set A of edges?

A

If no edge in A crosses the cut.

371
Q

When is an edge (u,v) a light edge crossing a cut?

A

If its weight is the minimum of any edge crossing the cut.

372
Q

How does Kruskal’s algorithm work?

A

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
Q

How does Prim’s algorithm work?

A

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
Q

What do both Kruskal’s and Prim’s algorithm assume?

A

That the input graph is connected and represented by adjacency lists.

375
Q

Single-source shortest path problem

A

Find a shortest path from a given source vertex s in V to every vertex v in V (for a given graph)

376
Q

Shortest path

A

Cannot contain negative-weight cycle, or positive-weight cycles. Only 0-weight cycles.

377
Q

Relaxing an edge (u,v)

A

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
Q

Critical path

A

A longest path through the DAG, corresponding to the longest time to perform a sequency of tasks.

379
Q

What does Dijkstra’s algorithm do & require?

A

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
Q
A

Year 3 of UU (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions