25-Comp-A4 Program Design and Data Structures · December 2017
Question 9 of 9: Algorithm Design — Recursive Palindrome Test
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
Paper format. 98-Comp-A4 Program Design and Data
Structures, December 2017 — 3 hours, closed book, no calculator
permitted. Nine questions of equal weight (20 marks each: 1 and 7 split as
(a) 10 + (b) 10, 8 split as (a) 15 + (b) 5); candidates answer any six, so a
complete paper is 120 marks. Pseudocode or any high-level language is
accepted, and the examiner's note states explicitly that marking emphasises
the operation of the program, not syntactic details.
All nine questions are answered below, because the whole set
is the more useful revision resource. Answers are given in C or C++ as the
question dictates; each is compilable as written (or corrected where the printed paper itself has a slip), but a clear, correctly reasoned
pseudocode answer would earn the same marks.
Reference texts for this subject.
Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms,
4th ed. — tree traversals and BSTs (ch. 12), recursion and
divide-and-conquer (ch. 2, 4), asymptotic analysis (ch. 3).
Weiss, Data Structures and Algorithm Analysis in C, 2nd ed. —
linked lists and stacks (ch. 3), binary trees (ch. 4).
Deitel & Deitel, C++ How to Program, 10th ed. — class
design and operator overloading (ch. 9–11), file streams (ch. 14).
Kernighan & Ritchie, The C Programming Language, 2nd ed. —
arrays and file I/O (ch. 1, 7), pointers, structures and linked
lists (ch. 5–6).
Stroustrup, The C++ Programming Language, 4th ed. — class
templates and value semantics (ch. 3, 25–27).
The Computer Engineering citation list is built around architecture and
networking texts (Patterson & Hennessy, Tanenbaum, Mano); this subject is
programming and data structures, so the works above are cited instead.
Question 9: Algorithm Design — Recursive Palindrome Test (20 marks)
Given. A character sequence seq of length
n; worked examples "bob", "deed", "level" (palindromes) and
"test", "Hello" (not).
Find. A short recursive function
int palindrome(char *seq, int n).
Approach. Compare the first and last characters; if they
differ, it is not a palindrome; if they match, the answer reduces to
whether the interior (length $n-2$, starting one character in) is itself a
palindrome. Base cases: length 0 or 1 is trivially a palindrome.
State the recursion. $palindrome(seq,n)=1$ if $n\le1$;
$0$ if $seq[0]\ne seq[n-1]$; otherwise
$palindrome(seq+1,\,n-2)$.
Write the function.
int palindrome(char *seq, int n)
{
if (n <= 1) return 1;
if (seq[0] != seq[n - 1]) return 0;
return palindrome(seq + 1, n - 2);
}
Confirm against the worked examples. "bob" ($n=3$):
$b==b$, recurse on "o" ($n=1$) → 1. "deed" ($n=4$): $d==d$, recurse on
"ee" ($n=2$): $e==e$, recurse on "" ($n=0$) → 1. "level" ($n=5$):
$l==l\to$ "eve" $\to e==e\to$ "v" ($n=1$) → 1. "test" ($n=4$): $t==t$,
recurse on "es" ($n=2$): $e\ne s$ → 0. "Hello" ($n=5$): $H\ne o$
→ 0 immediately.
$$\boxed{\text{bob, deed, level}\to1;\ \ \text{test, Hello}\to0}$$
