2D1455 OO-Teori


Take Home Exam

NOTES: (Please read these carefully!)

(i) Clearly mark at the top of each sheet you use: (a) your name (b) your e-mail address (in case I need to contact you) (c) the page number.

(ii) On the front page indicate how many pages are contained in your work in total.

(iii) Before handing in your work, tie the pages together with a paperclip, staple, or put them in a folder.

(iv) Your work must be handed in to NADAs studentexpedition no later than Thursday 26th May 2005 at 11.00 am. After this time it will be marked as late, and marks will be subtracted.

(v) If you have any questions about the exam (for example, if you do not understand a question) you may call my mobile number 076 223 86 79. Please do not call before 9.00 am or after 9.30pm! During the work day you may also e-mail me.

(vi) You may use your kursbunt, and any course books. You are allowed to use the internet, including search engines. However, you may not download any material from the internet and present it as your own without giving credit to your source. You are not allowed to discuss or develop your answer with anyone else until after all manuscripts have been handed in. You are not allowed to copy anyone else's work. By handing in your manuscript you are declaring that you have abided by these rules. In the case that cheating is suspected, actions will be taken against any students involved.

(ii) Write clearly. No marks will be awarded for work that I cannot read. You can write your answers in swedish or english.

Answer all questions. Maximum marks are 50 points. A grade 3 will be awarded for 25 points or more, grades 4 and 5 are returned for better performances.

Question 1. Consider a simple CD player. We will assume the player interface includes an automated sliding tray that can be opened and closed. We can select a track number by skipping forwards or backwards. We can play/stop/pause.

(i) (2 points) Draw a simple diagram for a graphical user interface (GUI) of such a device, and give names for the main GUI components (buttons etc) that could be used in LSCs.

(ii) (3 points) Draw a UML class diagram for an object model of the CD player. Your diagram should include all events generated by interface components as methods belonging to the target class of each event. (If you are not familiar with UML class diagrams, then simply list the classes of you object model, and for each class list its attributes and/or methods.) Include parameter and return types.

(iii) (5 points) By means of 1 or more text use cases, describe the user interaction that takes place starting from power-on, followed by loading a CD, followed by playing a selected track. Include any exceptional/error scenarios.

(iv) (10 points) Formalise your text use cases for part (iii) as live sequence charts. You may use the play-engine if you wish, but you may also draw diagrams by hand. (If you use the play-engine at home, you will also need access to a printer.)

Question 2. Recall the sequential object-oriented language Seqool and its operational semantics. The semantics of this language assumes an unlimited memory supply. Therefore objects need never be deleted! This assumption is of course unrealistic.

(i). (2 points) Redefine the syntax of seqool by adding an operation that allows the programmer to delete an object. Note: you do not need to redefine the whole language. Just show where and how you add the extension to the language. Use BNF notation following the course notes.

(ii) (12 points) Modify the semantics of seqool by restricting the memory size to some finite number n say. You may assume that the memory size is the same as the maximum number of objects (of any type) that may exist. (a) By using semantic rules, define the behaviour of your delete operation. Also, (b) Redefine the existing semantics of the new operator, so that if new is invoked after n objects have been created then an exception is raised (memory overflow).

(iii) (6 points) Explain how new and delete work together, by showing how a very simple Seqool program that contains them executes from start to termination. You should define the sequence of states and transitions that the abstract virtual machine goes through, in particular showing how your semantic rules in (ii) are applied. Note: your program should be very short (2-3 lines?) to simplify your explanation.

Question 3. Horner's scheme is an efficient algorithm for evaluating a polynomial

f(x) = a[0] + a[1] x + a[2] x^2 + + a[n] x^n

using as few multiplications as possible. The coefficients a[i] can be stored in a floating point array. Consider the following implementation of Horner's scheme as a while program.

Horner(float[] a, float x, int n)

{ i := n;

y := 0;

while ( i > 0 ) do

y := y + a[i];

y := y * x;

i := i - 1 od;

y := y + a[i]


(i) (1 point) Draw a flowchart for this while program.

(ii) (9 points) Using Floyd's method of inductive assertions prove the correctness assertion { n >=0 } Horner { y = a[0] + a[1] * x + a[2] * x^2 + + a[n] * x ^n } under its partial correctness interpretation. Take care to show how you derive each labelling formula using the branching and assignment rules.