UNIVERSITY OF MAURITIUS FACULTY OF ENGINEERING

SECOND SEMESTER EXAMINATIONS

MAY 2010
PROGRAMME BSc (Hons) Computer Science & Engineering BSc (Hons) Electronics and Computer Science BSc (Hons) Information and Communication Technologies Programming Languages and Algorithms Monday 10 May 2010 TIME NO. OF QUESTIONS SET 09.30 12.30 Hrs 6 DURATION NO. OF QUESTIONS TO BE ATTEMPTED 3 Hours 5 MODULE CODE CSE 2004Y(3)

MODULE NAME DATE

INSTRUCTIONS TO CANDIDATES

There are 2 sections in this paper: Section A and Section B. Each section consists of 3 questions. Answer any five (5) questions. All questions carry equal marks.

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

SECTION A
Question 1 (20 marks) (a) (b) Give the BNF rule for an identifier in C++. [2 marks]

Given the following BNF rules that form part of the grammar of the C++ language and the rule from Question 1(a) above, write the BNF rule for a condition in C++: Digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Letter a | b | | z | A | B | | Z Underscore _ RelationalOperator > | < | >= | <= | == | != BooleanOperator and | or UnaryOperator not Literal Integer | Boolean Integer Digit | Integer Digit Boolean True | False [3 marks] A class Calculator is used to represent a simple calculator. It has a single attribute value, of type double, that refers to the current value being displayed on the calculator. In addition, it has the following methods: Constructor that initialises the value being displayed to zero. Accessor and mutator methods. Method clear to set the value being displayed to zero. Method add that takes as parameter a double value and adds it to the current value being displayed. Method subtract that takes as parameter a double value and subtracts it from the current value being displayed. Method multiply that takes as parameter a double value and multiplies it with the current value being displayed. Method divide that takes as parameter a double value and divides the current value being displayed by the specified value if the latter is not equal to zero. Note: The methods add, subtract, multiply and divide leave their result on the display for further manipulation. You are required to: (i) Write an interface for the class Calculator. (ii) Implement the class Calculator in C++. [4 + 8 marks] /Contd next page Page 1 of 7

(c)

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

Question 1 (Contd) (d) Name the type of relationship between the objects in each of the following cases: (i) The telephone directory stores the contact details of many people. (ii) The Ministry of Finance is part of the Mauritian Government. (iii) A Manager is also an employee. [3 marks]

Question 2 (20 marks) (a) Refer to the following grammar G for mathematical operators +, -, *, /, % (modulo) and ** (exponentiation): Expr Expr + Term | Expr - Term | Term Term Term*Factor | Term/Factor| Term%Factor | Factor Factor Primary**Factor | Primary Primary 0|..|9| ( Expr ) (i) What can you say about the associativity of the operators * and **? [1 mark] Draw the parse tree for the mathematical expression 11 % 2 ** 2 + 4 * 3 - 5. [3 marks] Evaluate the expression given in Question 2(a)(ii). [1 mark]

(ii)

(iii)

(b)

(i)

What is the main difference between an imperative programming language and a functional programming language? [1 mark]

(ii)

In lambda Calculus, given that:

V1 V2 Vn . E means ( V1 ( V2 .... ( Vn. E))) What is the meaning of the lambda expression x y z. add x y z? [1 mark]

(c)

(i)

Write a function, length, in Scheme that takes as input a list L and returns the number of elements in L. [4 marks] Write a function, merge, in Scheme that takes as input two lists, L1 and L2, and appends the contents of L2 to L1. [5 marks] /Contd next page Page 2 of 7

(ii)

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

Question 2 (Contd) (iii) Using the functions in Question 2(c)(i) and Question 2(c)(ii), write a function, merge_longer, in Scheme that takes as input two lists, L1 and L2. If L1 is longer than L2 the function appends L2 to L1. Otherwise, it appends L1 to L2. Outputs of sample calls to merge_longer are as given below: > (merge_longer '(1 2 3 4) '(5 6)) (1 2 3 4 5 6) > (merge_longer '(1 2) '(3 4 5 6)) (3 4 5 6 1 2) [4 marks] Question 3 (20 marks) (a) (i) Differentiate between a statically-typed and a dynamically-typed language. Give one (1) example of each. [2 marks] Refer to the following code that represents part of a C++ program:

(ii)

void main() { 1. int num1, num2, sum; 2. float percent; 3. cout << Input num1: ; 4. cin>>num1; // Assume the user inputs 3 5. cout << Input num2: ; 6. cin>>num2; // Assume the user inputs 5 7. sum = num1 + num2; 8. percent = ((float) num1/num2) * 100; 9. cout<<Percentage representation of num1 over num2 is <<percent; // More code } Give the typeMap, tm, of the above program and the state, , of the above program after execution of line 8. [2 marks]

(b)

Write the corresponding predicates to represent each of the following statements: (i) Every student is enrolled in at least one module. (ii) If it is cloudy and humidity is high then it will rain. [2 marks] /Contd next page Page 3 of 7

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

Question 3 (Contd) (c) Write a Prolog program to represent the directed graph G1 given in figure 1. You are required to define the edges representing the graph, and a predicate for the relation path between two nodes.

Figure 1: Directed Graph G1

[5 marks] (d) (i) Write a Prolog definition for a predicate app that appends the contents of a list L2 to a list L1. Example: Query:?- app([1, 2, 3], [4, 5],Result). Result = [1, 2, 3, 4, 5]. [4 marks] Using the predicate app in Question 3(d)(i), write a Prolog program, double_list, that takes as input a list and returns another list whereby the contents of the given list are doubled. Example: Query: ?- double_list([2, 3, 5, 7], Result). Result = [4, 6, 10, 14] [5 marks]

(ii)

Page 4 of 7

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

SECTION B
Question 4 (20 marks) (a) A sorting algorithm is in O(n2) in the worst case. It takes 5 seconds to sort 10,000 records, i.e. n = 10,000. (i) What is the predicted time for the algorithm to sort 20,000 records? (ii) Suppose that you are presented with a machine that is 49 times as fast. How many records will you be able to process on the new machine in 5 seconds? [2 + 2 marks]

(b)

Given the growth rate for an algorithm, in the worst case, is expressed as follows, determine the upper bound of the algorithm: T(n) = 2n3 + 18n2 + 7 [3 marks] Solve the following recurrence relation using the substitution method: T(n) = 2T(n/2) + n, for n 2 and T(1) = 0 [4 marks]

(c)

(d)

Sort the following array of integers: 34 12 64 7 43 21 using: (i) (ii) Selection sort Insertion sort [3 + 3 marks]

Note: You are required to clearly illustrate each step.

(e)

Determine the worst case time complexity of the insertion sort algorithm, in terms of the number of comparisons. Note: You are required to show all your workings. [3 marks]

Question 5 (20 marks) (a) Given the following array of characters:

sort it using: (i) Quicksort, using the rightmost element as the pivot element (ii) Mergesort (iii) Straight radix sort, given the integer value of A is 1, that of B is 2,... Note: You are required to clearly illustrate each step. [4 + 4 + 4 marks] /Contd next page Page 5 of 7

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

Question 5 (Contd) (b) Determine the worst case time complexity, in terms of the number of comparisons, of each of the following algorithms: (i) Quicksort algorithm (ii) Straight radix sort algorithm Note: You are required to show all your workings. [3 + 3 marks] Name one (1) method that can be used to improve the running time of the quicksort algorithm. [1 mark] Briefly explain what is meant by a stable sort. [1 mark]

(c)

(d)

Question 6 (20 marks) (a) Draw the Red-Black tree that results from inserting the alphabetic keys Q U E S T I O N I S E A S Y in that order into an initially empty Red-Black tree. [7 marks] Using the alphabetic keys K E Y S, explain the concept of hashing as a searching method. [3 marks] Refer to the directed graph G2 below:

(b)

(c)

Figure 2: Directed Graph G2

(i) (ii)

Draw the adjacency list of G2. Draw the Depth-First-Search tree of G2, starting from node A. [3 + 3.5 marks]
/Contd next page

Page 6 of 7

PROGRAMMING LANGUAGES & ALGORITHMS CSE 2004Y(3)

Question 6 (Contd) (d) Consider the following undirected weighted graph G3:

Figure 3: Undirected Weighted Graph G3

Draw the minimum spanning tree (MST) of G3, using the Kruskals algorithm and find its cost. [3.5 marks]

END OF QUESTION PAPER

/ph

Page 7 of 7