(COMP3031)[2011](f)final~kmlaiab^_10765.pdf

Back to COMP3031 Login to download

======================================================

HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY

COMP3031 (Principles of Programming Languages)

Fall 2011

FINAL EXAMINATION

Dec 21, 2011 (Wed) 8:30am-11:30am, LG1 Table Tennis Room

Name ITSC Account

SOLUTION

Student ID Lecture Section L1

1.

About the exam:

2.

How to answer:

a.

You can ONLY use ball pen with black or blue ink to write your answers. Your answer should be in the designated space following each question.

b.

Rough work can be done in the provided additional blank paper for draft work. However, do not write answers there as they will NOT be graded.

3.

About this paper:

a.

There are a total of 11 pages, including this page.

b.

There are a total of 8 questions counting for 100 points in total.

c.

Attempt all questions. Partial credit will be given as applicable.

a. This is a closed-book, closed-notes examination.

b. You CANNOT use any electronic device (e.g. calculator) during the examination.

Please TURN OFF all of your electronic devices (e.g. mobile phone) and put them in

your bag.

c. You cannot leave during the last 15 minutes of the examination.

Problem 1 2 3 4 5 6 7 8 Total

Points

Problem 1 (10 points) SML Programming

A point is represented as a 2-integer tuple (X,Y) of X and Y coordinates. A point cloud is represented as a list of points. A point cloud is clear if there are no identical points in the list. A point cloud is sorted if all points in the list are first sorted on X and then on Y, both in ascending order. By definition, an empty cloud is both clear and sorted.

(a) Write a function clear: (int * int) list -> bool to determine whether a point cloud is clear.

fun in_cloud((x:int,y:int), []) = true | in_cloud((x,y), (x1,y1)::tail) = if x=x1 andalso y=y1 then true else in_cloud((x,y), tail);

fun clear([]) = true | clear(head::tail) = if in_cloud(head,tail) then false else clear(tail);

Grading criteria

1.

Compare two 2-integer tuple [X,Y] (1 point)

2.

Determine whether a 2-integer tuple [X,Y] appeared in a point list L (2 points)

3.

Determine whether a point cloud is clear. (2 points)

(b) Write a function sort: (int * int) list -> (int * int) list such that the output point cloud is sorted from the input point cloud.

Grading criteria:

1.

Compare relative value of two 2-intger tuple [X1,Y1] and [X2, Y2]. (1 point)

2.

Bubble sort.

a.

Sort the smallest point to the front, as insert function (2 points).

b.

Do insert to every element of the list. (2 points)

3.

Insert sort

a.

Find smallest (largest) value in list (2 points)

b.

Add smallest value in front of list (2 points)

4.

Quick sort

a.

Find pivot , put small value to the left and larger value to right of pivot (2 points)

b.

Recursively call sub-sort function (2 points)

Problem 2 (10 points) Prolog Programming

A p