Exercises for the week 3 exercise session¶
Exercise 1¶
In your washing machine, you have just washed a full load containing only black socks. You assume that no piece is lost and every sock has a pair. Now you should find a pair for each sock, since each pair is a little bit different. How would you describe the process of finding a pair for each sock ”algorithmically”? How fast does the pairing go in the best case (and what is the best case like?)
Exercise 2¶
Assume that A is a fixed-sized array. How and what do the following algorithms compute? What things should be taken into account, if the algorithm is implemented in C++?
1 2 3 4 5 6 7 8 9 10 11 | QueuePush(A,x):
IF QueueSize(A) = n THEN
RETURN "queue is full"
END IF
A[QueueEnd(A)] := x
QueueEnd(A) := QueueEnd(A) + 1
IF QueueEnd(A) > n THEN
QueueEnd(A) := 1
END IF
QueueSize(A) := QueueSize(A) + 1
RETURN
|
1 2 3 4 5 6 7 8 9 10 11 | QueuePop(A):
IF QueueSize(A) = 0 THEN
RETURN "queue is empty"
END IF
x := A[QueueBegin(A)]
QueueBegin(A):= QueueBegin(A) + 1
IF QueueBegin(A) > n THEN
QueueBegin(A) := 1
END IF
QueueSize(A) := QueueSize(A) - 1
RETURN x
|