Övning 2

Detta händer på dagens övning:

  • Frågor om labb 2?
  • Rekursion
  • Tidskomplexitet
  • Frågestund inför KS0

 

Frågor om Labb2?

 


Rekursion

Mål: Träna på rekursiva algoritmer.


Rekursiv listfunktion

Skriv en rekursiv funktion som lägger till ett element sist i en länkad lista

Rita först:

  • Hur det blir när listan är tom.
  • Hur det blir när listan redan innehåller tre element.

Och planera:

  • Vad ska funktionen ha för parametrar?
  • Vad ska funktionen returnera?
  • Vad är basfallet?
  • Vad är den rekursiva tanken?

Ladda ner recursiveAppend.py

recursiveAppend.py i Python Tutor Links to an external site.

GCD

För att beräkna största faktorn som två tal m och n har gemensamt kan vi använda Euklides algoritm:
Om m är jämnt delbar med n så är n den största gemensamma faktorn. Annars är GCD(m, n) = GCD(n, m%n). Skriv en rekursiv funktion!

lösning

Fibonaccital

Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta talföljd:
Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder och varje månad därefter producerar varje kaninpar ett nytt kaninpar. Vi kan skriva en rekursiv formel för antal kaninpar:

  • f(0)=0
  • f(1)=1
  • f(n)=f(n-1)+f(n-2) 


Skriv en rekursiv funktion för att beräkna Fibonaccital. Visa vilka rekursiva anrop den ger upphov till vid beräkningen av f(5). Är det här det effektivaste sättet att beräkna Fibonaccitalen?

lösning


Tidskomplexitet (inför KS1)

Mål: Öva på att räkna på tidskomplexitet. 


Körtider

En viss algoritm tar 0.5 ms när antal indata är 100. Hur många ms kommer det att ta när antal indata är 500 om man vet att körtiden är:

    1. linjär
    2. O(NlogN)
    3. kvadratisk
    4. kubisk   

lösning

Ordoklasser

Ange ordoklassen för funktionen T(n) =  log(n) + n*log(n) + 18*log(n²) + 0.7*n + 5*n²  + 325*n³ + 1600

lösning

Hur snabbt växer funktionerna?

Rangordna funktionerna efter hur snabbt dom växer, från långsammast till snabbast.

  • log(n)
  • 2n
  • n*log(n)
  • n
  • n

Tips: Rita upp funktionerna, t ex i https://www.desmos.com/calculator och jämför för stora n.

Tidskomplexitet för funktioner

Vilken tidskomplexitet har de två funktionerna nedan?

Vilken variabel beror tidskomplexiteten på?

Vilken av funktionerna är snabbast (för samma indata)?

def exists(the_list, key):
n = len(the_list) for x in the_list: if x == key: return True return False











exists i Python Tutor Links to an external site.
def binary_search(the_list, key):
low = 0
n = len(the_list)
high = n-1

while low <= high:
middle = (low + high)//2
if the_list[middle] == key:
return True
else:
if key < the_list[middle]:
high = middle - 1
else:
low = middle + 1
return False


binary_search i Python Tutor Links to an external site.

lösning: se föreläsning 3


Gamla tentauppgifter för eget arbete


Tidstentan 2014-01-08, uppgift 4

  • Betyg E
    Antalet binära strängar av längd n är 2n. Antalet alfanumeriska (ca 32 olika tecken) strängar av längd m är 32m.

    Vad blir uttrycken ovan om n=10 och m=3?

    Hur mycket större än m måste n vara för att det första uttrycket ska bli större än det andra?

  • Betyg C
    Körtider Linda berättar för Alexander att hon bytt till ett lösenord med 45 binära siffror. ''Men herregud!'', säger Alexander, ''Det blir ju alldeles för lätt att knäcka. Själv har jag 9 alfanumeriska tecken i mitt.''

    Vems lösenord är svårast att knäcka med totalsökning?

    Ungefär hur många sekunder tar knäckningen om datorn prövar en miljard lösenord i sekunden?

    Visa dina beräkningar!

    lösning till liknande, s 3

Aliententan 2015-03-20, uppgift 9

  • betyg A Samtliga solförmörkelsedatum på jorden under perioden 4000 f.kr. - 4000 e.kr. är insorterade i ett binärt sökträd. Givet en historisk persons födelse och död, beskriv en algoritm som hittar antal solförmörkelser personen potentiellt skulle kunna ha upplevt under sin livstid. 

Algoritmbeskrivningen måste vara välstrukturerad och begriplig. 

lösning