COMP3021 (Spring 2021) Programming Language Paradigms
Take-home exam 4:00pm-9:30pm, 7th May, 2021
Question Paper
Instructions:
• You must type your answers into the provided answer book.
DON’T type your answers into this question paper!
• Please check the detailed instructions in the provided answer book.
• You must answer questions by yourself only.
You are not allowed to discuss with other people about questions and answers.
Question 1. [25 marks]
You are given the following C++ program.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include
#include
bool isPalindrome( char* s, int n ) {
if (n<2)
return true;
else
return (isPalindrome(&s[1],n-2)&&(s[0]==s[n-1]));
}
void main() {
char* t="abcdcda";
int m=strlen(t);
bool result = isPalindrome(t,m);
}
1(a) [13 marks]
Run the given program until the condition at line 5 (len<2) becomes true.
Assume that the address of t is 0x70001000.
Draw the runtime stack at that time moment.
• Show clearly both the name and the value / pointer of each item.
• Mark unknown values (in activation records) by ?.
1(b) [6 marks]
Let m be the length of the string used in the main function.
Calculate the maximum (possible) number of activation records in the runtime stack,
in terms of m, during the execution of the given problem.
1(c) [6 marks]
Rewrite the isPalindrome function by using tail recursion.
Question 2. [25 marks]
Suppose that the Java language no longer supports 2-dimensional array.
We will write the following Java class in order to simulate 2-dimensional array.
In this question, you are not allowed to use any existing class (e.g., ArrayList, Vector) in existing Java packages
public class TwoDimArray {
private int[] A;
private int lenX,lenY;
public TwoDimArray( int _lenX, int _lenY ) ...
public int getValue(int X, int Y) ...
public void setValue(int X, int Y, int value) ...
}
2(a) [9 marks]
Write codes for all the methods (including the constructor) in TwoDimArray.
2(b) [8 marks]
The above TwoDimArray class can only be used to store integers. In other applications, we need to use two-dimensional arrays for other data types, e.g., floating-point numbers, strings, …, etc. Discuss how to modify the TwoDimArray class in order to support code reuse and extensibility.
2(c) [8 marks]
Discuss about the advantages and the disadvantages of using C++ and Java.
Suggest an application so that C++ is preferred over Java. Explain why.
Suggest an application so that Java is preferred over C++. Explain why.
Question 3. [25 marks]
In an arithmetic puzzle, different letters are assigned different digits (e.g., 0, 1, 2, …, 9) in order to make the arithmetic expression becomes correct. For example, in the following two arithmetic puzzles, their answers are:
Puzzle #1: C=4, R=2, A=6, C=4, K=1, H=9, E=5, O=8
Puzzle #2: G=1, I=0, V=7, E=2, M=9, O=8, N=6, Y=4
Puzzle #1
Puzzle #2
CRACK
+ HACK
ERROR
GIVE
* ME
MONEY
In this question, we use the following Prolog program to solve a puzzle. Z denotes a list of variables. It applies the generate-and-test paradigm: (i) first assign digits to variables in Z, then (ii) check whether the puzzle becomes correct.
assign( Z, L ) :- ???.
check( Z ) :- ???.
solve( Z ) :- assign( Z, [0,1,2,3,4,5,6,7,8,9] ), check( Z ).
In the following, we only consider the puzzle #1: CRACK + HACK = ERROR
To solve this puzzle, we enter the following goal in the Prolog interpreter: solve([C,R,A,K,H,E,O]).
3(a) [5 marks]
Write a rule for find(VAL,H,A,C,K) so that it instantiates the variable VAL to the arithmetic value of “HACK”. E.g., find(VAL,9,6,4,1) binds VAL to 9641.
3(b) [10 marks]
Write a rule for check(Z) so that it binds Z to a list of variables (C,R,A,...) and then checks whether the condition in the puzzle #1 becomes true.
You may write additional rule(s) if you need to use them in check(Z).
Note that, in the puzzle #1, C and H are the first digits so they cannot take the value 0.
Hint: use
3(c) [10 marks]
The rule for assign(Z,L) is used to assign the digits from the list L to the list Z,
so that different items in Z are assigned different digits.
Write rule(s) for assign(Z,L) so that it considers all possible assignments of digits to Z.
Question 4. [25 marks]
4(a) [5 marks]
Define the list of all positive odd integers by using set-builder notation in the Haskell language.
4(b) [10 marks]
Consider a function Factorize that takes a positive integer X as input,
then returns the list of prime factors of X.
Example input: X=20
Example output: [2,2,5]
(because 20 = 2*2*5)
Express the function Factorize by using mathematical equations.
Hints: Consider the base case and the recursive case. If you wish to use some helper functions in your solution, please write their equations first.
4(c) [10 marks]
Discuss and compare about the readability of Scheme and Haskell.
Provide sample codes to support your arguments.