AEC
1) Geef de tijdscomplexiteit van volgende 2 functies
Code: Select all
a: functie f(m, n) {
int i = 0;
int total = 0;
while (i < m) {
int j = 0;
while (j < n) {
total += 5; // Ik weet ni meer exact wa het dee, mr da doe er ni echt toe voor de tijdscomplexiteit
j++;
}
i++;
}
}
O(m*n) dus
b: functie f(m, n) {
int i = 0;
int j = 0;
int total = 0;
while (i < m) {
while (j < n) {
total += 5; // Ik weet ni meer exact wa het dee, mr da doe er ni echt toe voor de tijdscomplexiteit
j++;
}
i++;
}
}
O(m+n) dus
/* Kben wel ni meer 100% zeker, kheb deze vraag ni opgeschreven,
maar voor zover dak mij herinner moet het toch zoiets zijn */
2) p21 en p22
a: Geef de vertaling van STORE*i (2pt)
b: Geef de tijdskost volgens het logaritmisch criterium voor de individuele RASP instructies uit (a), zoals dit gedaan wordt bovenaan p21 (2pt)
3) a: p66 Leg uit waarom een knoop geen hoofdknoop kan zijn van 2 verschillende indices i, in de veronderstelling dat S = {a1, ..., an} bestaat uit n verschillende elementen (4pt)
b: Toon aan dat stelling p65 hieruit volgt, ook zonder veronderstelling dat alle elementen verschillend zijn (2pt)
4) p99 SAT
a: Schets een niet-deterministisch algoritme voor SAT dat een polynomiaal tijdscomplexiteit heeft. De beschrijving moet voldoende gedetailleerd zijn om duidelijk te maken dat de tijdscomplexiteit wel degelijk polynomiaal is (3pt)
b: Volstaat dit om aan te tonen dat SAT element is van NP-TIME? (2pt)
5) p114 VC is NP-compleet
Leg uit waarom deze reductie van CLIQUE naar VC een polynomiaal reductie is (3pt)