XXXday, May XX, 2006
00.00a.m. - 00.00a.m.
University of Glasgow
DEGREES OF M.Sci., M.Eng., B.Eng., B.Sc., M.A. and M.A. (Social Sciences)
COMPUTING SCIENCE CS-1P
(Answer all 6 questions.)

. 

1.		Consider the following Ada expressions, in which the variables X and Y are of type Integer, Z is of type Float, and B is of type Boolean.
	(a)	X * Y
	(b)	X rem Y
	(c)	10 + X / Y
	(d)	X / 2 = Z and B
		For each expression,
•	state whether it is a legal Ada expression.
•	for each legal expression, 
•	state the type of the expression, and
•	determine its value when the variables have values X=20, Y=3, Z=10.0, B=True.
•	for each illegal expression, explain what is wrong with it.
 [5]

2.	(a)	Explain in a single concise sentence the purpose of the function X given below. 
		[Hint: hand-execute the code using one or more particular arrays as parameters to the function.]

type Int_Array_Type is array(Integer range <>) of Integer;

function X( A : Int_Array_Type ) return Boolean is
   J : Integer := A( A'First );
begin
   for I in A'First + 1 .. A'Last loop
      if A( I ) >= J then
         return False;
      end if;
            
      J := A( I );
   end loop;

   return True;
end X;            
[4]
 	 (b)	An integer array of type Int_Array_Type above holds altitude readings taken during a plane flight.  The flight may consist of many periods of ascent and descent.  Write a subprogram that takes this array as parameter and returns the total height that the plane has climbed during all periods of ascent.
 [7]

3.		The following program reads in a sequence of integers from Standard Input, terminated by a zero.  It then calculates and writes out the average of these integers, as a floating point value.

	with Ada.Text_IO; use Ada.Text_IO;
	with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
	with Ada.Float_Text_IO; use Ada.Float_Text_IO;

	procedure Average
	   Count, Total, Next : Integer;
	begin
	   Get( Next );
	   while Next /= 0 loop;
	      Total := Total + Next;
	      Count := Count + 1;
	   end loop;

	   Put( "The average of the numbers is " );
	   Put( Float( Total ) / Count, 0, 2, 0 );
	   New_Line;
	end Average;

	(a)	Identify two compile-time errors in the code, and how to fix them.
[2]
	(b)	Identify two logic errors in the code, and how to fix them.
[2]
	(c)	Identify two possible exceptions that could be raised by the corrected program, and for each, explain (i) what line would generate it, and (ii) the conditions that would cause it.
[2]
	(d)	Using exception handlers, add code to the program so that it handles these exceptional conditions gracefully.
	[2]
 	(e)	Create two sets of test data that could be used to check how the program handles these exceptions, one set of data per exception.
 [2]

4.		The following procedure uses the insertion sort algorithm to sort the elements of the integer array A into ascending order.

type Int_Array_Type is array(Integer range <>) of Integer;

procedure Sort(A : in out Int_Array_Type ) is
   -- sorts the elements of A into ascending order
   Low  : Integer := A'First;
   High : Integer := A'Last;
   Temp : Integer;
   Insert_Pos : Integer;
begin
   for Next in Low + 1 .. High loop
      Temp := <…1…>;
      Insert_Pos := Next;
      while Insert_Pos > 1 and then <…2…> loop
         <…3…>;
         Insert_Pos := Insert_Pos – 1;
      end loop;
      <…4…>;
   end loop;
end Sort;
  		There are four statements or expressions missing from this procedure, indicated by <...1…>, <…2…>, etc.  Give the four missing code fragments.
[8]

5.	(a)	Write the declaration of an enumeration type Day_Type to represent the seven days of the week.
	[1]
 	(b)	Now define a subtype of this type for just the five working days, called Working_Day_Type.
[1]
	(c)	Assuming the following declarations,
	   	D : Day_Type;
	   	W : Working_Day_Type; 
		for each of the following statements, state whether it would or could generate a compile-time error or run-time error, and explain your answer.
    		(i)	D := W;
    		(ii)	W := D;
    		(iii)	D := Day_Type'Succ( D );
[3]
    	(d)	Why are subtypes a useful typing mechanism?
[1]

6.		In a certain country, trainee teachers are assigned to probationary posts according to the following mechanism. 
1.	Each employing authority indicates the number of posts that are available in that authority. All authorities initially have no trainees assigned.
2.	Each trainee indicates up to three authorities where she wishes to work, in order of preference.
3.	The trainees are randomly ordered.
4.	Each trainee in turn, in the given random order, is assigned to her most preferred authority that is not already full; if all of her chosen authorities are full, she remains unassigned.
		If there are n trainees and m authorities, then the trainees are labelled 1, 2, . . ., n and the authorities are labelled 1, 2, . . ., m.
		As an illustration, suppose that there are 6 authorities, with numbers of posts as in the following table:

Authority	1	2	3	4	5	6	
No. of posts	2	3	2	2	3	2	
		Suppose further that there are 8 trainees and the following table gives the preferences of each trainee.  Note that the trainees appear here in the appropriate random order:

Trainee	1st choice	2nd choice	3rd choice	
4	4	1		
6	2	4	1	
1	4	3	2	
8	4	1	5	
2	1			
7	6	1		
3	4	1	6	
5	1	6	4	
		Then the algorithm executes as follows:
•	trainee 4 is assigned to authority 4
•	trainee 6 is assigned to authority 2
•	trainee 1 is assigned to authority 4
•	trainee 8 is assigned to authority 1 (since authority 4 is full)
•	trainee 2 is assigned to authority 1
•	trainee 7 is assigned to authority 6
•	trainee 3 is assigned to authority 6 (since authorities 4 and 1 are full)
•	trainee 5 is unassigned (since authorities 1, 6 and 4 are all full)
		You are to write a program that implements this scheme. 
		Input to the program consists of two files
•	Authorities.txt – a text file that contains one line for each authority; the ith  line of this file contains an integer representing the number of posts available at authority i;
•	Trainees.txt – a text file that contains one line for each trainee; a line of this file contains a trainee number, followed by a colon, followed by up to three integers, representing the chosen authorities for that trainee, in order of preference; the trainees are already randomly ordered in this file.
		The program sends to standard output:
•	one line of text for each trainee; this line contains a trainee number, followed by a colon, followed by the number of the authority to which the trainee is assigned, with 0 representing the unassigned case, and trainees appearing in the same order as in the input file.
•	one line of text for each authority; this line contains the authority number, the number of posts available, and the number of posts filled
		There are appropriate headings embedded in this output.
		So the input files for the above example would be:
		Authorities.txt:
2
3
2
2
3
2
		Trainees.txt:
4:  4  1
6:  2  4  1
1:  4  3  2
8:  4  1  5
2:  1
7:  6  1
3:  4  1  6
5:  1  6  4
		and the output would be:
Trainees' assignments
4: 4
6: 2
1: 4
8: 1
2: 1
7: 6
3: 6
5: 0

Authorities' allocations
1: 2 2
2: 3 1
3: 2 0
4: 2 2
5: 3 0
6: 2 2

	(a)	Write a plan for this program. 
[8]
   	(b)	What information about each authority, and about each trainee, is relevant to the program? Use your answers to these questions to define appropriate record data types to represent an authority and a trainee. Also define appropriate array data types and variables to represent the set of authorities and the set of trainees. You may assume that there are at most 100 authorities and at most 1000 trainees.
[10]
   	(c)	Specify any subprograms that may be appropriate for the refinement of your program.
[12]
   	(d)	Develop your program into a full Ada implementation.
[30]