WINAK

joew, hier zijn de examenvragen voor Datastructuren en Algoritmen van 2e zit. Ze leken mij vrij gemakkelijk.

1. Toon aan dat bij een topological sort van een graph met gesloten paden, het aantal foute edges niet altijd minimaal is.
(Hint: een graph met 4 nodes was voldoende)

2. Toon aan dat c(u,v) + c(v,u) = fc(u,v) + fc(v,u) met c de capacity en fc de flow van een flow-netwerk.
(Antwoord in 2 lijntjes).

3. Schrijf een algortime met complixiteit O(E* log E) , dat in een flownetwork het augmenting path vind met de grootste capaciteit. (Hint: Sorteer edges op capacity en zoek met DFS ofdat {E1,...,EK} een path vormt met E1 tot EK edges).

4. Gegeven een bipartite graph. Doe het Ford-Fulkerson algoritme en bepaal de kleinste bovengrens van het langste augmenting path dat je kan hebben.

5. Je hebt een niet geconnecteerde graph G, met k delen. Zoek een algoritme dat deze delen vindt en ze kan voorstellen
(Hint : Disjoint Sets.)

6. Gegeven een spannings tree T van graph G. Amax(T) = de maximum weight van een edge.
Bewijs dat als Amax(T) miminaal beschouwt wordt T ook een minimal spannings tree is of geef een tegenvoorbeeld.

7. Gegeven een Fibonacci heap met 30 nodes. Wat is het maximale aantal root nodes die je kan overhouden nadat je een Delete-Min hebt uitgevoerd.

hey hier is ook Programmeer paradigma's : - P
Theorie:
1. Welke van volgende vergelijkingen is/zijn correct? Verklaar je antwoord:

(L = lambda)

- ((Lu.Lv.(v u) Lx.(x x)) Ly.(y (y y))) = (Lv.(Lu.(v u) Lx.(x x)) Ly.(y (y y)))
- ((Lu.Lv.(v u) Lx.(x x)) Ly.(y (y y))) = ((Lu.(Lu.u v) Lx.(x x)) Ly.(y (y y)))

2. (zie "Toekenning van typedescriptoren" in lambda calculus). Leg in je eigen woorden uit waarom het nodig is een generiek lijsttype gl in te voeren.

3. Geef enkele redenen waarom de volgorde van de clauses in een prolog programma belangrijk kan zijn, en illustreer dat telkens met een voorbeeld.

Oefeningen:
Schrijf een programma dat kan bepalen of een binairy tree symmetrisch is. Dit betekent dat de subtrees van de root elkaars spiegelbeeld zijn. Hierbij houden we geen rekening met de inhoud van de nodes, maar enkel met de structuur van de boom.

(a) Prolog : Verwachte werking

?- symmetric(t(a,t(b,nil,nil),t(c,nil,nil))).
true

(b) In haskell:
*main> symmetric(Tree 'a' Empty (Tree 'b' Empty Empty))
False

Schrijf een programma dat alle integers binnen een bepaalde interval berekent.

(a) Prolog

?- range(4,9,L).
L = [4,5,6,7,8,9]

(b) In Haskell zonder gebruik te maken van .. of enumfromto
main> range 4 9
[4,5,6,7,8,9]

Dan hier ook de examenvragen van Elementaire statistiek. Eindelijk het laatste : - P.

1. Formuleer de Centrale Limiet Stelling. Leg beknopt uit waarom deze stelling belangrijk is in de statistiek.

2. Geef in het kader van een algemene hypothesetest de definitie van
a. Type-II fout
b. p-waarde
c. Teststatistiek
d. Nullhypothese

3. Een continue stochastische veranderlijke X heet exponentieel verdeeld met parameter Lambda > 0 indien de dichtsheidsfunctie gelijk is aan

f(x) = e^(-x/Lambda) / (Lambda) met x >= 0

Bovendien is dan EX = Lambda.
Men weet nu dat de lengte van de telefoongesprekken een exponentiële verdeling volgt, met een verwachtingswaarde van 3 minuten.
a. Bereken de kans dat 1 telefoongesprek minder dan 4 minuten duurt.
b. Bereken de kans dat je in een bepaalde week met 30 telefoongesprekken te voeren, langer dan 2uur getelefoneerd hebt.

4. Wat is de kans dat niemand in een groep van 25 personen dezelfde verjaardag heeft.

5. Stel dat 8 kinderen leren lezen aan de hand van Methode A en dat 10 andere kinderen leren lezen met methode B. Na verloop van tijd gaat men beide groepen een leesvaardigheidstest afnemen. Bij de A-group registreert men volgende uitslagen: 12,18,16,16,15,17,14,18
De gemiddelde score bij de B-groep is 16.8 met een variantie van 6.62.
Mag men besluiten dat de score op de leesvaardigheidstest significant hoger is bij methode B (a = 5%)?