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.

 Programming – Pascal: Essential skills 2

 

Learning Outcomes:

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

Searching a list

 

Sequential search: check one by one.

Binary search:

 

Principles:

A sorted list in ascending or descending order. (otherwise cannot use binary search)

i	1	2	3	4	5	6
A[i]	50	95	105	205	400	450

Question 1: Where is 205 located?

Sequential search: check one by one from i = 1 to 6.

Binary search: check middle one to see. (1+6)/2 = 3. A[3] = 105.

105 < 205 i.e. ignore the left side and check the right side only à i from 4 to 6 (lower bound changed) Senario 1

i	1	2	3	4	5	6
A[i]	50	95	105	205	400	450

Check the middle one again. (4+6)/2 = 5. A[5] = 400.

400>205 i.e. ignore the right side and check the left side only à i from 4 to 4 (upper bound changed) Senario 2

i	1	2	3	4	5	6
A[i]	50	95	105	205	400	450

Check the middle one again. (4+4)/2 = 4. A[4] = 205. à found!

 

Question 2: What would happen if we instead look for 200 in the list?

After 2nd round, we check the middle one again. (4+4)/2 = 4. A[4] = 205.

205 > 200 i.e. Ignore the right side and check the left side only à i from 4 to 3 (upper bound changed) à implies 200 not in the list. Senario 3

 

Techniques:

Suppose you have an array A[i] with i = 1 to n. You want to find location of x in A[i].

var                 min, max, mid : integer;                 found : boolean; begin                 min := 1;                 max := n;                 found := false;                                                   (* to stop the loop once the target found*)                 repeat                                 mid := (min + max) div 2;                               (* calculate the middle of the list *)                                 if A[mid] = x then found := true                                                 else if A[mid] > x then max := mid -1        (* Senario 2 *)                                                 else min := mid + 1;                         (* Senario 1 *)                 until found or (min > max);                                          (* Senario 3 min > max *)                 If found then writeln (mid) end.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2015 3d*.

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

 Programming – Pascal: Essential skills 1
 

Learning Outcomes:

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

 

Character handling

 

ASCII Character list (extract):

Character	ASCII
‘0’	48
‘1’	49
‘A’	65
‘a’	97

 

Functions:

ord(‘A’) à 65

chr(65) à ‘A’

 

Essential skills:

Convert uppercase to lowercase: chr(ord(‘A’)+32) or lowercase(‘A’)

Convert lowercase to uppercase: chr(ord(‘a’)-32) or upcase(‘a’)

Covert ‘1’ to 1: ord(‘1’)-48

Covert ‘A’ to 1: ord(‘A’)-64

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  SP 2bc.

CE CIT Elect A(2005-2011): 2007 1a, 4bc. 2008 4ab.

 

Counting/Accumulating

 

var counter, i:integer; begin    counter:=0;                                        (* initiation *)    for i:= 1 to 5 do                 counter := counter +1      (* count the number of loops *) end.

 

Relevant past paper:

CE CIT Elect A(2005-2011): 2008 4d. 2010 3a.

 

Swapping

 

Suppose A[1] = 5, A[2] = 10.

var temp:integer;                            (* a temporary variable is usually needed *) begin    temp := A[1];    A[1] := A[2];    A[2] := temp end.

begin                                                  (* a temporary variable is not necessary for numbers *)    A[1] := A[1] + A[2];                            (* A[1] = 15 *)    A[2] := A[1] – A[2];                            (* A[2] = 15 – 10 = 5 *)    A[1] := A[1] – A[2]                             (* A[1] = 15 – 5 = 10 *) end.

Now A[1] = 10, A[2] = 5.

 

Relevant past paper:

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

CE CIT Elect A(2005-2011): 2010 2b. 2011 2a.

 Programming Languages

 

Learning Outcomes:

Programming paradigms

• Be aware of the evolution of programming languages.
• Recognise the programming paradigms involved in procedural, logic, object-oriented and query languages.
• One programming language for each paradigm is selected for illustration.
• Describe the criteria for selecting a programming language for a specific problem.

Language translators and compilers

• Define code generation, linkers and loaders.

 

Programming paradigms

 

Procedural languages

• Examples: Pascal, C, Fortran
• Features/Advantages: top-down approach àeasy to trace program flow and logic.

Object-oriented languages

• Examples: Visual Basic, Java, C++, Python
• Features/Advantages: 
• Entities represented by classes. An object belongs to a class. Each class has its own set of attributes and methods. E.g. CAR as an example of a class. My car (object) belongs to the class CAR. My car is white in color (attribute) and uses electricity to run e.g. move forward (method).
• Hide unnecessary information (encapsulation): you can use the class without showing the details of the class.
• Reuse of class/function (inheritance): derive a class from another class and reuses its attributes/methods.
• Utility libraries: pre-written code for specific tasks, helps to shorten software development time.

Logic languages

• Examples: Prolog
• Features/Advantages: Instead instructing the computer how to solve a problem, logic programming languages focus on what problem to solve by using the facts and rules given.

 

Criteria for selecting a programming language

• Examples:
• Cost
• Organisation policy
• Scalability
• Modularity
• Portability
• Availability of utility libraries

Relevant past paper:

DSE ICT Elect B(SP-2017):  PP 3f. 2012 1ci, 4c. 2013 4d. 2014 2d. 2015 2c. 2017 3d.

CE CIT 2005 3e.

 

Language translators and compilers

 

Code generation related: Translator – assembler, compiler, interpreter

• Source code: low level or high level program code that is written by programmer.
• Translator: Translation of source code into format that is understandable by computer. i.e. object code, machine code.
• Machine code: machine code is generated by assembler from source code (low level program code).  In general, execution of machine code is efficient.
• Object code: object code is generated by compiler from source code (high level program code). Further process is needed to convert the object code into executable file.
• Interpreter: Instead of generating an object code, interpreter translate the source code one statement at a time.
• Compiler vs interpreter: Compiler is more efficient as there is optimization of code during code generation.

Linker: A linker combines object code and the required external libraries files into a single executable file (.exe).

Loader: A loader loads the executable file to the main memory for execution.

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  PP 1c. 2012 1cii. 2013 2a. 2015 1ciii, 2d. 2016 1b. 2017 2e.

Learn more:

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

AL CS2(2003-2012): 2007 8cde. 2009 6. 2011 5.

 

References:

https://www.geeksforgeeks.org/introduction-of-programming-paradigms/

https://hackr.io/blog/programming-paradigms

https://divisionartistcom.wordpress.com/factors-influencing-the-choice-of-programming-languages/#:~:text=There%20are%20many%20factors%20that,when%20choosing%20a%20programming%20language.

https://medium.com/@rahul77349/machine-code-vs-byte-code-vs-object-code-vs-source-code-vs-assembly-code-812c9780f24c

https://semesters.in/concept-of-assembler-compiler-loader-and-linker/