Course week 2 exercises¶

Pseudocode¶

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

 Mystery1(Array[a1, a2, ... , aN]):
   B := []
   FOR elem IN Array LOOP
     IF first THEN
       B[0] := elem
     ELSEIF elem > LAST(B)
       APPEND(B, elem)
     END IF
   END LOOP
   RETURN  B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

 Mystery2(Int A, Int B):
   res := 0
   WHILE B > 0 LOOP
     IF B % 2 = 1 THEN
       res := res + A
     ENDIF
     A := A * 2
     B := B / 2
   END LOOP
   IF res = 0 THEN
     RETURN A
   ELSE
     RETURN res
   ENDIF

Decrease and conquer¶

There are two young boys on one side of the river and N adults on the other side. The boys have a small boat that they both fit into at the same time. However, the boat can only fit one adult and no boys at a time. How can all adults cross the river? Describe your solution in enough detail or write pseudocode. How is the decrease and conquer principle used in this problem?

Insertion sort¶

Binary search¶