1. COMP.CS.300 Data Structures and Algorithms 1 »
  2. Decrease- and divide-and-conquer »
  3. Session activity

Session activity

Exercises for the week 3 exercise session

Exercise 1 - Socks

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?) And how quickly does the process of finding pairs proceed in the worst case?

Exercise 2 - Queue

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

A+ presents the exercise submission form here.