- Gör (minst) en fil per uppgift och lägg filerna i katalogen
username-ovn3i organisationen grudat19 på KTH GitHub. - Utgå från mallarna i /grudat19/ovn0/.
- Lösningar ska vara inlämnade innan övningen börjar.
Du väljer själv vilket av programspråken Python, Go eller Java du vill använda. Observera att all kod på den här kursen ska dokumenteras och testas. Vid övningen ska du vara beredd att muntligt presentera och diskutera dina lösningar och din programkod.
Skriv en rekursiv fakultetsfunktion och bevisa att den är korrekt med hjälp av induktion.
Utöver beviset ska du som vanligt skriva testkod.
Beware of bugs in the above code; I have only proved it correct, not tried it.
– Donald Knuth
Typvärdet (mode) i ett statistiskt datamaterial är det värde som förekommer flest gånger.
- Skriv en funktion som beräknar typvärdet för en vektor med heltal. Om flera värden är lika vanliga skall funktionen ge det minsta av dem.
- Tidskomplexiteten för din algoritm ska vara O(n log n).
Det är fritt fram att använda de datastrukturer och algoritmer som finns i standardbiblioteken för Python, Java eller Go.
- Skriv en funktion som ändrar ordningen på en vektor med tal så att de negativa talen kommer först. Vektorn ska inte sorteras, du behöver endast samla alla negativa tal för sig.
- Skriv en loopinvariant som förklarar hur koden fungerar.
- Räkna också ut tidskomplexiteten för din algoritm.
Algoritmen ska vara in-place (Wikipedia: In-place algorithm), dvs använda högst O(1) extra utrymme. Du får inte använda någon sorteringsalgoritm.
För betyg VG ska du göra samma uppgifter som för betyg G, men med det extra kravet att algoritmerna i uppgift 3.2 och 3.3 ska ha O(n) tidskomplexitet. Det räcker med förväntad tid, men värstafall går förstås också bra.