VERY USEFUL FOR THE FINAL EXAMINATION – “A” LEVELS –
Prepared by Kaleem, Computer Science Teacher, NIS
NOTES ON DIFFERENT TYPES OF TOPICS – RELATED TO PSEUDOCODES:
SEARCHING – ALGORITHMS:
LINEAR SEARCH:
PROCEDURE LINEAR_SEARCH (ARRAY, VALUE):
FOR I -> 0 TO LENGTH OF ARRAY - 1
IF (ARRAY [I] == VALUE)
OUTPUT (ARRAY [I])
END IF
END FOR
OUTPUT (“VALUE IS NOT FOUND”)
END PROCEDURE
BINARY SEARCH:
PROCEDURE BINARY_SEARCH (ARRAY, VALUE):
LEFT = 0
RIGHT = LENGTH (ARRAY) - 1
WHILE LEFT <= RIGHT
MID = (LEFT + RIGHT) / 2
IF ARRAY [MID] == VALUE:
OUTPUT (MID)
ELSE IF (ARRAY [MID] < VALUE)
LEFT = MID + 1
END IF
ELSE
RIGHT = MID – 1
END IF
END WHILE
OUTPUT (“VALUE NOT FOUND”)
END PROCEDURE
SORTING – ALGORITHMS:
BUBBLE SORT (OPTIMIZED ALGORITHM):
PROCEDURE BUBBLE_SORT (A: LIST OF SORTABLE ITEMS)
N = LENGTH (A)
REPEAT
SWAPPED = FALSE
FOR I -> 1 TO N-1
IF A [I] > A [I+1] THEN
SWAP (A [I], A [I+1])
SWAPPED = TRUE
END IF
END FOR
N=N-1
UNTIL NOT SWAPPED
END PROCEDURE
INSERTION SORT:
PROCEDURE INSERTION_SORT (A: LIST OF SORTABLE ITEMS)
FOR I -> 1 TO LENGTH (A) - 1
KEY = A [I]
J=I-1
WHILE J >= 0 AND A [J] > KEY
A [J + 1] = A [J]
J=J-1
END WHILE
A [J + 1] = KEY
END FOR
END PROCEDURE
DATA STRUCTURES – STACKS, QUEUES:
STACKS – LAST IN FIRST OUT (LIFO):
STACK:
ITEMS = []
PROCEDURE PUSH(ITEM)
ITEMS.APPEND (ITEM)
PROCEDURE POP()
IF IS_EMPTY():
OUTPUT "STACK IS EMPTY"
RETURN ITEMS.POP()
PROCEDURE IS_EMPTY()
RETURN LENGTH(ITEMS) == 0
PROCEDURE PEEK()
IF IS_EMPTY():
OUTPUT "STACK IS EMPTY"
RETURN ITEMS [LENGTH (ITEMS) - 1]
PROCEDURE SIZE ()
RETURN LENGTH(ITEMS)
ALGORITHM:
STACK -> NEW STACK () // CREATE A NEW STACK
STACK.PUSH (1) // PUSH 1 ONTO THE STACK
STACK.PUSH (2) // PUSH 2 ONTO THE STACK
STACK.PUSH (3) // PUSH 3 ONTO THE STACK
OUTPUT (STACK.PEEK ()) // PRINTS 3
OUTPUT (STACK.POP ()) // PRINTS 3
OUTPUT (STACK.PEEK ()) // PRINTS 2
STACK.PUSH (4) // PUSH 4 ONTO THE STACK
OUTPUT (STACK.SIZE ()) // PRINTS 3 (THE STACK CONTAINS 2, 1, AND 4)
WHILE NOT STACK.IS_EMPTY ()
OUTPUT (STACK.POP ()) // PRINTS 4, 1, 2 (IN THAT ORDER)
END WHILE
QUEUES – FIRST IN FIRST OUT (FIFO):
ENQUEUE – ADDING ITEMS TO THE QUEUE:
PROCEDURE ENQUEUE (ITEM, N)
IF (REAR = N – 1)
OUTPUT “OVERFLOW! QUEUE IS ALREADY FULL”
IF FRONT = -1 AND REAR = -1
SET FRONT, REAR TO 0
ELSE
SET REAR = REAR + 1
END IF
SET QUEUE [REAR] = ITEM
END PROCEDURE
DEQUEUE – REMOVING ITEMS FROM THE QUEUE:
PROCEDURE DEQUEUE ()
IF (FRONT = -1 OR FRONT > REAR)
OUTPUT “UNDERFLOW! QUEUE IS EMPTY”
ELSE
SET VAL = QUEUE [FRONT]
END IF
IF (FRONT=REAR)
SET FRONT=REAR=-1
ELSE
FRONT = FRONT + 1
END IF
END PROCEDURE
FRONT – TO PRINT THE VALUE IN THE FRONT:
PROCEDURE FRONT ()
IF (FRONT = -1)
OUTPUT “QUEUE IS EMPTY!”
ELSE
SET VAL = QUEUE [FRONT]
OUTPUT VAL
END IF
END PROCEDURE
ARRAYS – 1 DIMENSIONAL & 2 DIMENSIONAL:
1-Dimensional Array – example:
1. Design a pseudocode that reverses a string and print it.
SET WORD TO “INTELLECT”
FOR LOOPCOUNTER -> (LENGTH OF THE WORD) – 1 TO 0
LOOPCOUNTER = LOOPCOUNTER – 1
OUTPUT ARRAYWORD [LOOPCOUNTER]
END FOR
2-Dimensional Array – example:
1. Given a table of integers, the pseudocode will ask user for a row number
and return the total of that row, e.g.
If the user inputs "0", they will see 33 (which is 4+7+12+10)
N=ARRAY[[4,7,12,10],[2,1,8,9],[14,9,3,7] ]
INPUT ROW
TOTAL=0
FOR I -> 0 TO 3
TOTAL=TOTAL + N [ROW, I]
END FOR
OUTPUT TOTAL
2. Write pseudo code to input and output number in two-dimensional array of
3 rows and four column.
BEGIN
DECLARE ARRNUM [3][4]
FOR I -> 0 TO 3
FOR K IS 0 TO 4
READ ARRNUM [I][K] FROM KEYBOARD
END FOR
END FOR
FOR I -> 0 TO 3
FOR K IS 0 TO 4
OUTPUT (ARRNUM[I][K])
END FOR
END FOR
END
