[A&C] Oefeningen

[slimmy]

In reeks 2 wordt er gevraagd hoe je een vermenigvuldiging inplementeerd met een DMTT, heeft er iemand dat is helemaal uitgewerkt? En wa is dan de tijd/plaats complexiteit daarvan?

[Shinta]

In reeks 2 wordt er gevraagd hoe je een vermenigvuldiging inplementeerd met een DMTT, heeft er iemand dat is helemaal uitgewerkt? En wa is dan de tijd/plaats complexiteit daarvan?

Euh ik heb da hier erges ligge, ge moest da ni implementeren he, gewoon uitleggen hoe get zou doen.

[Robbe]

Waren er nog reeksen buiten diegenen die op Pieter zijn webspace staan?

[Shinta]

Waren er nog reeksen buiten diegenen die op Pieter zijn webspace staan?

dat zijn ze ongeveer, enkele zijn wel verouderd.. en hij heeft nog enkele dinges in de les op bord geschreve.

[Robbe]

Waren er nog reeksen buiten diegenen die op Pieter zijn webspace staan?

dat zijn ze ongeveer, enkele zijn wel verouderd.. en hij heeft nog enkele dinges in de les op bord geschreve.

Iets da hier het vermelden waard is?

[Robbe]

reeks 7
voor oef2 heb ik:

Code: Select all

begin

    Queue := leeg

    Som := 0

    for j := 1 to n do

        Input[j] vooraan in Queue

        Som += Input[j]

        while Som > 10 do

            Som -= laatste element van Queue

            verwijder laatste element uit Queue

        od

        if Som = 10 then stop fi

    od

end

Volgens mij is dit O(n) omdat die while hoogstens 2 keer uitgevoerd wordt. Ziet iemand hier graten in?


reeks 7b
oef1: wat wordt hier verwacht da ge maakt? zo'n diagrammen gelijk me T&A om een e-NFA te maken uitgaande van een RE?

moet ge trouwens dat dijkstra gedoe kunnen?

[Norfolk]

reeks 7
voor oef2 heb ik:

Code: Select all

begin

    Queue := leeg

    Som := 0

    for j := 1 to n do

        Input[j] vooraan in Queue

        Som += Input[j]

        while Som > 10 do

            Som -= laatste element van Queue

            verwijder laatste element uit Queue

        od

        if Som = 10 then stop fi

    od

end

Volgens mij is dit O(n) omdat die while hoogstens 2 keer uitgevoerd wordt. Ziet iemand hier graten in?

reeks 7b
oef1: wat wordt hier verwacht da ge maakt? zo'n diagrammen gelijk me T&A om een e-NFA te maken uitgaande van een RE?

moet ge trouwens dat dijkstra gedoe kunnen?

dijkstra is dat deel dat we niet moeten kennen
edit: en langs de andere kant moet ge da toch nog kunnen van netwerken vorig jaar dus das toch geen probleem

[Robbe]

edit: en langs de andere kant moet ge da toch nog kunnen van netwerken vorig jaar dus das toch geen probleem

ni da'k da ni kan, maar ik moet het wel nog eens opfrissen dan

[Shinta]

reeks 7
voor oef2 heb ik:

Code: Select all

begin

    Queue := leeg

    Som := 0

    for j := 1 to n do

        Input[j] vooraan in Queue

        Som += Input[j]

        while Som > 10 do

            Som -= laatste element van Queue

            verwijder laatste element uit Queue

        od

        if Som = 10 then stop fi

    od

end

Volgens mij is dit O(n) omdat die while hoogstens 2 keer uitgevoerd wordt. Ziet iemand hier graten in?


reeks 7b
oef1: wat wordt hier verwacht da ge maakt? zo'n diagrammen gelijk me T&A om een e-NFA te maken uitgaande van een RE?

moet ge trouwens dat dijkstra gedoe kunnen?

waarom zou die while lus maar twee keer moeten worden uitgevoerd ? . Neeje, die while lus doet gewoon niets af aan de lineariteit omdat dit niet afhankelijk is van de grootte van de invoer.

[Norfolk]

De body van die while lus wordt hoogstens n -1 keer uitgevoerd. Dit is als er geen substring gevonden wordt. (Wel iets minder dan n -1 keer omdat de laatste 2 getallen ook onder 10 kunnen liggen enzo)
Hiermee bedoel ik ook dat de body van de while lus IN TOTAAL hoogstens n - 1 keer uitgevoerd wordt
De for lus ook n keer. Dus dat wordt 2n keer en dus O(n).


Heeft er iemand een oplossing voor dat algoritme van kortste paden voor een graaf met mogelijk negatieve kosten op zijn kanten?

[Shinta]

De body van die while lus wordt hoogstens n -1 keer uitgevoerd. Dit is als er geen substring gevonden wordt. (Wel iets minder dan n -1 keer omdat de laatste 2 getallen ook onder 10 kunnen liggen enzo)
Hiermee bedoel ik ook dat de body van de while lus IN TOTAAL hoogstens n - 1 keer uitgevoerd wordt
De for lus ook n keer. Dus dat wordt 2n keer en dus O(n).


Heeft er iemand een oplossing voor dat algoritme van kortste paden voor een graaf met mogelijk negatieve kosten op zijn kanten?

ja secondje .

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

[Robbe]

waarom zou die while lus maar twee keer moeten worden uitgevoerd ? . Neeje, die while lus doet gewoon niets af aan de lineariteit omdat dit niet afhankelijk is van de grootte van de invoer.

Die while-lus wordt maar hoogstens 2 keer uitgevoerd omdat het laatst ingelezen getal de som hoogstens op 12 brengt, omdat anders een match werd aangeduid in de vorige iteratie van de for.

[Shinta]

waarom zou die while lus maar twee keer moeten worden uitgevoerd ? . Neeje, die while lus doet gewoon niets af aan de lineariteit omdat dit niet afhankelijk is van de grootte van de invoer.

Die while-lus wordt maar hoogstens 2 keer uitgevoerd omdat het laatst ingelezen getal de som hoogstens op 12 brengt, omdat anders een match werd aangeduid in de vorige iteratie van de for.

wtf :s agij 111119 hebt, dan ebde

1
2
3
4
5
14
WHILELUS:
1: 13
2: 12
3: 11
4: 10

=> 19 is match

[Robbe]

ik denk da gij een andere opgave hebt, want bij mij is het alfabet maar {1,2,3}

[Norfolk]

neen wij hebben zelfde maar ja uw algoritme blijft hetzelfde en dan nog kan de while lus meer dan 2 keer doorlopen worden hoor
vb. 333333333322222
3322 zal de substring zijn dus while wordt 8 keer doorlopen