ovn4.md

Övning 4 grudat21

Torsdag 29/4 kl 13.00

Vid övningen ska du vara beredd att muntligt presentera och diskutera dina lösningar och din programkod.

• Gör (minst) en fil per uppgift och lägg filerna i katalogen username-ovn4 i organisationen grudat21 på KTH GitHub.
• Utgå från mallarna i /grudat21/ovn0/.
• Lösningar ska vara inlämnade före deadline.

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.

Betyg G

1 Tidskomplexitet för rekursiva funktioner

Teori

Beräkna tidskomplexiteten för funktionerna pow, sum1 och sum2.

def pow(n):
	"""Return 2**n, where n is a nonnegative integer."""
	if n == 0:
		return 1
	x = pow(n//2)
	if n%2 == 0:
		return x*x
	return 2*x*x

def sum1(a):
	"""Return the sum of the elements in the list a."""
	n = len(a)
	if n == 0:
		return 0
	if n == 1:
		return a[0]
	return sum1(a[:n//2]) + sum1(a[n//2:])

def sum2(a):
	"""Return the sum of the elements in the list a."""
	return _sum(a, 0, len(a)-1)

def _sum(a, i, j):
	"""Return the sum of the elements from a[i] to a[j]."""
	if i > j:
		return 0
	if i == j:
		return a[i]
	mid = (i+j)//2
	return _sum(a, i, mid) + _sum(a, mid+1, j)

Tips och råd om att räkna ut tidskomplexitet för rekursiva funktioner (video)

Praktik

Gör en benchmark där du mäter tiden för att exekvera de här funktionerna. Uppgiften ska göras i Python och du ska mäta tiden, till exempel med funktionen time.time:

start = time.time()
pow(n)
print(n, time.time() - start) # elapsed time

Testa för n = 10, 100, 1,000, 10,000, 100,000 och 1,000,000. Vid behov kan du också testa större tal, eller kanske fler datapunkter. Presentera resultaten av tidmätningarna i en tabell eller i en graf.

Diskussion

Skriv en diskussionsdel där du försöker förstå och förklara eventuella skillnader mellan teori och praktik.

2 Linjärtidssortering av små tal

Implementera, dokumentera och testa en algoritm som sorterar heltalen x₁, x₂, ..., x_n. För samtliga tal x_i gäller att 0 ≤ x_i ≤ k.

Din algoritm ska ha värstafallstidskomplexitet O(n+k). För vilka värden på k blir algoritmen linjär?

Tips: räkna hur många element det finns av varje sort.

Betyg VG

3 Linjärtidssortering när det finns många dubbletter

Designa en algoritm som som sorterar n stycken heltal där det förekommer upprepningar. Det totala antalet olika tal är k. Beskriv algoritmen i pseudokod.

Din algoritm ska ha tidskomplexitet O(n + klog(k)). Förväntad tid räcker. För vilka värden på k blir algoritmen linjär?