19.1 Algorithms

Question 1

Write an algorithm to implement a linear search (player name).

Answer 1

//search for a player's name
DECLARE  Found : BOOLEAN
DECLARE i : INTEGER
Found ← FALSE
i ← 1

REPEAT
   IF ThisPlayerName = PlayerName[i]
      THEN
          Found ← TRUE
          PlayerNumber ← i
      ELSE
         i ← i + 1
   ENDIF

UNTIL (Found = TRUE)

Question 2

Write an algorithm to implement a binary search.

Answer 2

//search for value in array
DECLARE ValueFound : BOOLEAN
DECLARE UpperBound : INTEGER
DECLARE LowerBound : INTEGER
DECLARE NotInList : BOOLEAN
ValueFound ← FALSE
UpperBound ← LengthOfList - 1
LowerBound ← 0
NotInList ← FALSE

WHILE ValueFound = FLASE AND NotInList = FALSE
MidPoint ← ROUND( (LowerBound + UpperBound) / 2)

   IF List[MidBound] = SearchValue
      THEN
         ValueFound ← TRUE
      ELSE
         IF List[MidPoint] < SearchValue
            THEN
               LowerBound ← MidPoint + 1
            ELSE
               UpperBound ← MidPoint - 1
         ENDIF
   ENDIF
ENDWHILE

IF ValueFound = TRUE
   THEN
      OUTPUT "Value Found"
   ELSE
      OUTPUT "Not on List"
ENDIF

Question 3

Why does a Binary Search Algorithm need to be sorted?

Answer 3

1) Does not check every value
2) MidPoint is assigned to middle element, not the middle numerical value.
3) Has to assume that numbers to the right of the MidPoint will be greater and numbers to the left will be smaller.

Question 4

Binary Search complexities.

Answer 4

Time Complexity : O(log n)

Space Complexity : O(1)

Question 5

Write an algorithm to implement an insertion sort.

Answer 5

//array Numbers[0 : Max]
Declare Variables
FOR Pointer ← 1 TO (Max - 1)
   ItemToInsert ← Numbers[Pointer]
   CurrentItem ← Pointer
   WHILE (CurrentItem > 0) AND (Numbers[CurrentItem - 
   1] > ItemToInsert)
      CurrentItem ← CurrentItem - 1
   ENDWHILE
   Numbers[CurrentItem] ← ItemToInsert
ENDFOR

Question 6

Write an algorithm to implement bubble sort.

Answer 6

//array ItemList[1:20]
MaxIndex ← 20
NumberItems ← MaxIndex - 1
FOR Outer ← 1 TO MaxIndex - 1
   FOR InnerList ← 1 TO NumberItems