Comprehesion-type questions

 

Learning Outcomes:

• Represent algorithms with flowcharts or block diagrams.
• Apply algorithms of counting, accumulating, swapping, searching, sorting and merging in writing programs.
• The search algorithms included are linear search and binary search.
• Construct lists, stacks and queues in terms of arrays.
• Students should be able to create and manipulate linear linked lists, stacks and queues in terms of arrays.
• Realise the importance of good programming styles.
• Students should develop the habit of using meaningful variable names, comments, annotations, space and indentation.
• Design sets of test data for program testing.
• Test data for boundary cases has been discussed in the Compulsory Part.

 

Follow a flowchart

Relevant past paper:

DSE ICT Elect B(SP-2017):  2014 1b.

 

Searching

Linear/sequential search: check the items one by one. E.g. for data structure such as queue and linked list.

Binary search:  for data sorted in an array.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2017 4dii,e.

 

Linked lists, stacks, queues

• Linked lists: need to find an item by linear search. More flexible to add or remove an item.
• Queues: first-in-first-out. Need to use head and tail indicator.
• Stacks: last-in-first-out.

All data structure can have underflow errors/overflow errors if attempts to add items to a full list or to remove items from empty list.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  SP 2de. PP 2ab. 2012 2a. 2014 1ci,3. 2016 2ac. 2017 3ab.

CE CIT Elect A(2005-2011): 2005 4. 2006 4. 2008 2ab. 2009 3abce. 2010 1a. 2011 3a-d.

 

Good programming styles

• Use of meaningful variable names, comments, annotations, space and indentation.
• Use of constant: easy to change the value for use in other programs.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2012 3b.

 

Test data

Useful set of test data should include:

• Valid data: normal data and extreme case
• Invalid data

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  PP 3e. 2013 2e.

CE CIT Elect A(2005-2011): 2006 1c.

 

Manipulate arrays

Relevant past paper:

DSE ICT Elect B(SP-2017):  2014 2abci. 2015 3abii,iii.

 

Other questions

Relevant past paper:

DSE ICT Elect B(SP-2017):  SP 2a. 2013 4ab. 2015 4bc. 2016 3avd. 2017 4aci,di.

Pseudocode

 

You may be required to write an algorithm using pseudocode or to interpret an algorithm written in pseudocode.

 

In general, a pseudocode is similar to program written in Pascal. So there is no need to ‘learn’ how to write if you know how to write in Pascal.

Some tips:

	Pascal	Pseudocode
Loop	For i := 1 to n do	For i from 1 to n do
Assign	n := 1	n ß 1
Return a result from a function Sample	sample := true	Return true
Display on the screen	Writeln (a)	Display a

 

Relevant past paper:

Write pseudocode

DSE ICT Elect B(SP-2017):  PP 1ai. 2013 1biii. 2014 2cii. 2015 3bi,c,4d. 2016 2b,d,3b,4b. 2017 1bii, 4b,cii.

CE CIT Elect A(2005-2011): 2008 2c. 2009 3d. 2010 1bii,c. 2011 1bc,3eii.

 

Comprehension

DSE ICT Elect B(SP-2017):  SP 1. PP 1ab. 2012 1ab, 4b. 2013 1,2,3dii,iii. 2014 4ab. 2015 1abci,ii. 2016 1c,4a. 2017 2a-d.

CE CIT Elect A(2005-2011): 2007 1. 2010 1bi. 2011 1ad, 3ei.

Programming – Pascal: Essential skills 8

Other commands

 

Random()

 

To generate different random numbers when the same program is run, use the command randomize.

Random(100) generates a number with a possible range of 0 – 99.

var                 a : integer; begin randomize;                         (* when the same program is run again, a different set of random number is generated *) a := Random(100) + 1      (* possible values of a = 1-100 *) end;

 

Trunc()

 

The function trunc() changes a real number into an integer by simply removing the decimal part.

e.g. trunc(2.99) becomes 2

 

Multiple select: case … of

 

Instead of using multiple if… statements, we can better organize the program by using case … of.

var                 a : integer; being                 case a of                                 1..3 : writeln (‘less than 4’);                                 4..6 : writeln (‘between 4 and 6’);                                 7..9 : writeln (‘between 7 and 9’)                 else                                 Writeln (‘out of range’)                 end end;

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2013 3di.

CE CIT Elect A(2005-2011): 2007 3ab. 2009 1ad, 4bi. 2010 3bcd.

 Programming – Pascal: Essential skills 7

Learning Outcomes:

• Construct lists, stacks and queues in terms of arrays.
• Students should be able to create and manipulate linear linked lists, stacks and queues in terms of arrays.

 

Data structure - Queue

 

Features of a queue:

• First-in-first-out i.e. moving an item can only be from the front(head) and adding an item can only be to the end(tail).

A queue represented by an array:

• Inconvenient to move every items forward when first item is removed. Pointers are used to represent the head and tail positions. I.e. head pointer moves to next location when first item is removed.
• When more and more items are added and removed from the queue, the tail pointer reaches the end of the array. In order to fully utilize the array, the tail pointer move to the first position of the array for the queue to continue. In this way, the array is analogous to a circular array.
• The queue size is limited by the size of the array.

 

One of the way to implement a queue:

var                 queue : array[0..2] of string;       (* array with 3 slots *)                 head, tail : integer; begin head := 0; tail := 0;                (* when head = tail, queue is empty *)                 …

 

	head = 0		head = 1		head = 2
Size of of the queue	head	tail	head	tail	head	tail
0	0	0	1	1	2	2
1	0	1	1	2	2	0
2	0	2	1	0	2	1
3	0	0 (3 mod 3)	1	1	2	2

 

Two ways to handle a ‘full’ array

1. Use a counter to count the number of items in the queue. So even head = tail, we know the queue is not empty as counted by counter. (max number in the queue is 3)
2. Avoid filling up the array. I.e. avoid the situation of head = tail when the queue is not empty. (max number in the queue is 2)

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2014 1cii,iii,d.

Programming – Pascal: Essential skills 6

 Programming – Pascal: Essential skills 6

 

Learning Outcomes:

• Implement parameters passing in manipulating sub-programs.
• The sub-programs are called by two parameters passing methods: call by value and call by reference.

  

Call-by-value/Call-by-reference

 

When using procedure or function, parameters may be passed into the called procedure / function. The original parameters may or may not be affected depending on call-by-value or call-by-reference.

 

Call-by-value:

var                 x, y : integer;      (* global variables *)                 procedure add (a, b : integer);    (* a and b have their own memory address *) begin                 a := a + 1;                 b := b + 1;                 write (a+b) end;   begin                 x := 1;                 y := 2;                 add (x, y);            (* the use of this procedure does NOT affect the  value of x and y *)                 write (x + y) end.

Output: 53

 

Call-by-reference:

(the only difference from the program above is the var in the procedure heading)

var                 x, y : integer;      (* global variables *)                 procedure add (var a, b : integer);             (* a and b uses the memory address of x and y *) begin                 a := a + 1;             (* x is now 2 *)                 b := b + 1;            (* y is now 3 *)                 write (a+b) end;   begin                 x := 1;                 y := 2;                 add (x, y);            (* the use of this procedure AFFECTS the values of x and y *)                 write (x + y) end.

Output: 55

 

Procedure and function

While a procedure is a subprogram which is quite similar to a usual program (see above), a function always returns a single result.

 

Procedure:

procedure add (a, b : integer); …

 

Function:

function add (a, b : integer) : integer; …

Having the extra part (: integer), it means this function is going to return an integer when called.

 

var                 x, y, sum : integer;   function add (a, b : integer) : integer; begin                 add := a + b end;   begin                 x := 1;                 y := 2;                 sum := add (x, y);              (* similar to using a built-in function *)                 write (sum) end.

Output: 3

 

You can use call-by value or call-by-reference when using functions depending on the purposes of the function / program.

 

Relevant past paper:

DSE ICT Elect B(SP-2017): SP 3d. PP 3a-d. 2012 3ac, 4ai.

CE CIT Elect A(2005-2011): 2009 4bii,iii.

 Programming – Pascal: Essential skills 5

 

Learning Outcomes:

• Manipulate text files through filehandling statements.
• The manipulation involves file updating statements to delete, insert, append and amend records.
  
   

Text file handling

Read from file

var                 infile : text;         (* text file variable *)                 a : integer; begin                 assign (infile, ‘yourfile.txt’);         (* step 1: associate the file with the variable *)                 reset (infile);                                      (* step 2: read from beginning *)                 while not eof (infile) do                 begin                                 readln (infile, a);                (* step 3: read the integer and put into a *)                                 writeln (a)                           (* write the content on the screen *)                 end;                 close (infile)                                         (* step 4: close the file properly *) end;

 

Write into file

var                 infile : text;         (* text file variable *)                 a : integer; begin                 assign (infile, ‘yourfile.txt’);         (* step 1: associate the file with the variable *)                 rewrite (infile);                                 (* step 2: create or erase the file for writing*)                 a := 1;                 writeln (infile, a);                               (* step 3: put the integer into the file *)                 close (infile)                                         (* step 4: close the file properly *) end;

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  PP 4cd. 2012 4aii.

CE CIT Elect A(2005-2011): 2005 2a. 2009 2abi. 2010 4a. 2011 4cd.

 Programming – Pascal: Essential skills 4

 

Learning Outcomes:

• Apply control structures in a solution.
• Sequence, selection and iteration have been introduced in the Compulsory Part.
  
  

Iteration

 

Methods of iteration:

• for … to … do … / for … downto … do …
• repeat … until …
• while … do …

Advanced technique:

• Nested loop

 

for … to … do … / for … downto … do …

Important point: use for loop when the number of loops is known.

for i := 1 to n do                 write (i);

Output: 1234….n              

 

repeat … until …

Important points:

• use repeat loop or while loop when the number of loops cannot be determined before running the program.
• Location of the counter is important.
• The program will run through the content first before checking the condition. i.e. even condition is not met, the content is run at least once.

i := 0; Repeat                 i := i + 3;                 write (i) until i > 10;

i := 0; Repeat                 write (i);                 i := i + 3 until i > 10;

Output: 36912                                                         Output: 0369

 

while … do …

Important points:

• use repeat loop or while loop when the number of loops cannot be determined before running the program.
• Location of the counter is important.
• The program will check the condition first before running through the content i.e. When condition is not met, the content is skipped.

i := 0; while i <10 do begin i := i + 3; write (i) end;

i := 0; while i <10 do begin write (i); i := i + 3 end;

Output: 36912                                                                   Output: 0369

 

Nested loop

Suppose you have an array A[x,y], you want to sum up the elements.

var                 i, j : integer; begin                 for i := 1 to 3 do                 (* Outer loop *)                                 for j := 1 to 2 do                 (* Inner loop *)                                                 sum := sum + A[i,j] end;

Use a table to trace the program.

Outer loop	i	j	Inner loop
	1	1
	1	2
	2	1
	2	2
	3	1
	3	2

The same applies to nested while loop and nested repeat loop.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2014 4c*.

CE CIT Elect A(2005-2011): 2005 3a-d. 2006 3cd. 2007 2abc. 2009 1bc, 2bii, 4a. 2010 2a.

Programming – Pascal: Essential skills 3

 Programming – Pascal: Essential skills 3

 

Learning Outcomes:

Apply algorithms of counting, accumulating, swapping, searching, sorting and merging in writing programs.

Sorting

• Bubble sort
• Insertion sort
• Merge sort

Bubble sort principles:

Question: to sort the array in ascending order.

i	1	2	3	4	5
A[i]	12	14	5	7	8

For bubble sort, 2 elements are inspected each time, and the larger one is swapped to right if it’s not on the right.

 

i	1	2	3	4	5
A[i]	12	14	5	7	8

Then we move on to position 2 and 3.

i	1	2	3	4	5
A[i]	12	5	14	7	8

Since 14 is larger, it is swapped to the right

 

… the process goes on until…

i	1	2	3	4	5
A[i]	12	5	7	14	8

14 is larger than 7.

i	1	2	3	4	5
A[i]	12	5	7	8	14

After the first round, we are sure the largest number is on the right.

 

So we will work on the remaining 4 elements at second round.

i	1	2	3	4	5
A[i]	12	5	7	8	14

After completing second round, we are sure 12 is the second largest number in the array.

i	1	2	3	4	5
A[i]	5	7	8	12	14

 

After completing third round:

i	1	2	3	4	5
A[i]	5	7	8	12	14

We noticed no swapping happened in the third round since the 3 numbers are in order already.

So there is no need for forth round.

 

Techniques:

Suppose you have an array A[i] with n elements.

var                 i, j, temp : integer;                 swapped : Boolean; begin                 i := 0;                 repeat                                                            (* Outer loop for each round *)                                 i := i + 1;                                       (* count the number of round *)                                 swapped := false;                           (* initiate for each round *)   for j := 1 to n – i do                     (* Inner loop for swapping, 1st round 1 to n-1, 2nd round 1 to n-2, etc. *)                 if A[j] > A[j+1] then                 begin                                 temp := A[j];                (* swapping *)                                 A[j] := A[j+1];                                 A[j+1] = A[j];                                 Swapped := true                               (* if no swapping after 1 round, outer loop stops *)                 end                   until ( i = n – 1 ) or not swapped;            (* maximum number of round is n – 1 *) end;

 

Relevant past paper:

CE CIT Elect A(2005-2011): 2005 1.