A palindrome is a word that reads the same forwards and backwards, such as "MADAM" or "RACECAR". (a) Write pseudocode for a function called IsPalindrome tha...
Question 1 Report
A palindrome is a word that reads the same forwards and backwards, such as "MADAM" or "RACECAR".
(a) Write pseudocode for a function called IsPalindrome that takes a string as a parameter and returns TRUE if it is a palindrome, or FALSE otherwise. [5]
(b) Trace through your function with the input "LEVEL", showing the comparisons made. [3]
(c) Explain why your function only needs to check half the characters in the string. [1]
Answer Details
(a) The function uses two pointers: Left starting at position 1 and Right starting at the last position. It compares characters at these positions and moves both pointers inward. If any mismatch is found, the string is not a palindrome:
FUNCTION IsPalindrome(Word : STRING) RETURNS BOOLEAN
DECLARE Left : INTEGER
DECLARE Right : INTEGER
Left <- 1
Right <- LENGTH(Word)
WHILE Left < Right DO
IF Word[Left] <> Word[Right] THEN
RETURN FALSE
ENDIF
Left <- Left + 1
Right <- Right - 1
ENDWHILE
RETURN TRUE
ENDFUNCTIONThe function header with parameter and return type [1]. Initialising Left and Right pointers [1]. The WHILE loop condition Left < Right [1]. Comparing characters at both ends [1]. Moving pointers inward and returning the correct result [1]. [5]
(b) Tracing with "LEVEL" (length = 5):
| Step | Left | Right | Word[Left] | Word[Right] | Match? |
|---|---|---|---|---|---|
| 1 | 1 | 5 | 'L' | 'L' | Yes |
| 2 | 2 | 4 | 'E' | 'E' | Yes |
| Check | 3 | 3 | Left is not < Right, loop ends | ||
The function returns TRUE. "LEVEL" is a palindrome. [3]
(c) Each comparison checks a character from the front against its mirror character from the back. Checking beyond the midpoint would repeat the same comparisons already made (comparing position i with position n-i+1 is the same pair as comparing position n-i+1 with position i). Stopping at the midpoint avoids this redundancy. [1]
Download The App On Google Playstore
Everything you need to excel in your exams
