Programming#

Stepwise Refinement#

This is the process of developing a modular design by splitting a problem into smaller sub-tasks, which themselves are repeatedly split into even smaller sub-tasks until each is just one element of the final program.

1. Break down the complex problem into smaller and more manageable parts.
2. These steps parts then need to be written as a series of steps.
3. Each step can be written as a statement in a high-level programming language.

Waterfall Model#

Each stage is completed and signed off before the next stage is begun

• suitable for small projects with a short timescale

Principles

• linear, as each stage is completed before the next is begun
• well documented as full documentation is completed at every stage
• low customer involvement; only involved at the start and end of the process

Benefits

• easy to manage, understand and use
• stages do not overlap and are completed one at a time
• each stage has specific deliverables
• works well for smaller programs where requirements are known and understood

Drawbacks

• difficult to change the requirements at a later stage
• not suitable for programs where the requirements could be subject to change
• working program is produced late in the lifecycle
• not suitable for long, complex projects

Iterative Model#

These program development cycles are repeated until the full system has been developed

• suitable for projects for which the major requirements are known but some details are likely to change or evolve with time

Principles

• incremental development as the program development lifecycle is repeated
• working programs are produced for part of the system at every iteration
• high customer involvement, as part of the system can be shown to the
• customer after every iteration

Benefits

• some working programs developed quickly at an early stage in the lifecycle
• easier to test and debug smaller programs
• more flexible as easier to alter requirements
• customers involved at each iteration therefore no surprises when final system delivered

Drawbacks

1. whole system needs to be defined at start, so it can be broken down into pieces to be developed at each iteration
2. needs good planning overall and for every stage
3. not suitable for short simple projects

Rapid Application Development#

Develops different parts of the requirements in parallel

• suitable for complicated projects that need developing in a short timeframe to meet the evolving needs of a business

Principles

• minimal planning
• reuses previously written code where possible, makes use of automated code generation where possible
• high customer involvement, as customers can use the prototypes during development

Benefits

• reduced overall development time
• rapid frequent customer feedback informs the development
• very flexible as requirements evolve from feedback during development as parts of the system are developed side by side, modification is
• easier because each part must work independently

Drawbacks

• system under development needs to be modular
• needs strong teams of skilled developers
• not suitable for short simple projects

Structure Diagram#

Structure chart is a modelling tool used to decompose a problem into a set of sub-tasks.

It shows the hierarchy or structure of the different modules and how they connect and interact with each other.

• Shows the sequence of module execution.
• Represents Module Hierarchy (top-down approach with major modules on top)
• Shows selections.
• Shows repetitions.
• Depicts the interface/connection between modules using parameters.

3 programming actions / features that can be depicted in a structure chart:

1. Procedures and functions - each module is represented by a box and the parameters passed to and from the modules are shown by arrows pointing towards the module receiving the parameter.

   

2. Selection - the diamond shaped box shows a condition that can be true or false.

   

3. Repetition - the repetition is shown by adding a label and semi-circular arrow above the module to be completed.

   

Symbol	Name	Meaning
	Process	Each box represents a programming module = a calculation, output etc.
	Data Couple	Data being passed from module to module that needs to be processed.
	Flag	The check data sent to process to stop or start process. (only represent Boolean value)

详细的实例参考教材288页即可

State Transition Diagram#

State transition diagrams are suitable for systems with a fixed number of states that may change on input or when an event occurs (Final state machine).

It visually represents a system’s states, the events that causes transitions (Inputs or times), and the transitions between states.

They may also show the condition needed for an event to cause a transition (the guard condition) and the outputs or actions carried out resulting from a transition.

• States are represented as nodes (circles).
• Transitions are represented as interconnecting arrows.
• Events are represented as labels on the arrows.
• Conditions can be specified in square brackets after the event label.
• The initial state is indicated by an arrow with a black dot.
• A stopped state is indicated by a double circle.

$\uparrow$ finite state machine - a machine that consists of a fixed set of possible states with a set of inputs that change the state and a set of possible outputs.

Errors#

Syntax - An error in the grammar that breaks the rules of the Programming Language.

Run-time - Can be compiled to machine code but fails upon execution. eg. divide by 0, infinite loop.

Logic - The program runs but gives incorrect output.

Testing Methods#

对于功能的测试：

• Dry run / Walkthrough: The developer works through a program or module from a program manually and document the results using a trace table. A walkthrough is a formalised version of a dry run using pre-defined test case.
• White-box testing: the detailed testing of how each procedure works, this involves testing the structure and logic of every part through a program module.
• Black-box testing: tests a module’s input and output.
• Integration testing: The testing of any separately written modules to ensure that they work together.

Stub Testing

Stubs are the modules that act as temporary replacement for a called module and give the same output as the actual product.

Test stubs are programs that mimic (copy) the behaviors of software components (or modules) that a module undergoing tests depends on.

Stubs are used during Top-down integration testing.

对于消费者的测试：

• Alpha testing: used first - The completed or nearly completed program is tested in-house by development team.
• Beta testing: used second, the completed program is tested by a small group of users before it is formally released.
• Acceptance testing: Used third. The completed program to prove to the customer that it works as required in the environment in which it will be used.

Test Data#

• Normal data: the data will be accepted by the program.
• Extreme data: the largest and lowest value that are normal data.
• Abnormal data: the data will be rejected by the program.

Types of Maintenance#

• Corrective: used to correct any errors that appear during use.
• Protective: to improve the performance of a program during its use.
• Adaptive: Used to alter a program so it can perform any new tasks required by the customer. Can function in different environments.

Abstract Data Type#

ADT is the collection of data, and the set of operations on those data

关于这部分内容，建议参考Hello 算法中的介绍。(大力推荐这本书)

考试会涉及的三种抽象数据类型：

• Stack - 5.1 栈 - Hello 算法

  last in, first out

  • PUSH
  • POP

  1
  // To set up a stack
  2
  DECLARE stack ARRAY[1:10] OF INTEGER
  3
  DECLARE topPointer : INTEGER
  4
  DECLARE basePointer : INTEGER
  5
  DECLARE stackful : INTEGER
  6
  basePointer <- 1
  7
  topPointer <- 0
  8
  stackful <- 10
  9
  
  10
  // To push an item, stored in item, onto a stack
  11
  IF topPointer < stackful
  12
  THEN
  13
      topPointer <- topPointer + 1
  14
      stack[topPointer] <- item
  15
  ELSE
  16
      OUTPUT "Stack is full, cannot push"
  17
  ENDIF
  18
  
  19
  // To pop an item, stored in item, from the stack
  20
  IF topPointer = basePointer - 1
  21
  THEN
  22
      OUTPUT "Stack is empty, cannot pop"
  23
  ELSE
  24
      Item <- stack[topPointer]
  25
      topPointer <- topPointer - 1
  26
  ENDIF
  

• Queue - 5.2 队列 - Hello 算法

  first in, first out

  • ENQUEUE
  • DEQUEUE

  1
  // To set up a queue
  2
  DECLARE queue ARRAY[1:10] OF INTEGER
  3
  DECLARE rearPointer : INTEGER
  4
  DECLARE frontPointer : INTEGER
  5
  DECLARE queueful : INTEGER
  6
  DECLARE queueLength : INTEGER
  7
  frontPointer <- 1
  8
  endPointer <- 0
  9
  upperBound <- 10
  10
  queueful <- 10
  11
  queueLength <- 0
  12
  
  13
  // To add an item, stored in item, onto a queue
  14
  IF queueLength < queueful
  15
  THEN
  16
      IF rearPointer < upperBound
  17
      THEN
  18
          rearPointer <- rearPointer + 1
  19
      ELSE
  20
          rearPointer <- 1
  21
      ENDIF
  22
      queueLength <- queueLength + 1
  23
      queue[rearPointer] <- item
  24
  ELSE
  25
      OUTPUT "Queue is full, cannot enqueue"
  26
  ENDIF
  27
  
  28
  // To remove an item from the queue and store in item
  29
  IF queueLength = 0
  30
  THEN
  31
      OUTPUT "Queue is empty, cannot dequeue"
  32
  ELSE
  33
      Item <- queue[frontPointer]
  34
      IF frontPointer = upperBound
  35
      THEN
  36
          frontPointer <- 1
  37
      ELSE
  38
          frontPointer <- frontPointer + 1
  39
      ENDIF
  40
      queueLength <- queueLength - 1
  41
  ENDIF
  

• Linked list - 4.2 链表 - Hello 算法

  each item in the list points to the next item in the list

  1
  To set up a linked list
  2
  DECLARE myLinkedList ARRAY[0:11] OF INTEGER
  3
  DECLARE myLinkedListPointers ARRAY[0:11] OF INTEGER
  4
  DECLARE startPointer : INTEGER
  5
  DECLARE heapStartPointer : INTEGER
  6
  DECLARE index : INTEGER
  7
  heapStartPointer <- 0
  8
  startPointer <- -1 // list empty
  9
  
  10
  FOR index <- 0 TO 11
  11
      myLinkedListPointers[index] <- index + 1
  12
  NEXT index
  13
  // the linked list heap is a linked list of all the
  14
  // spaces in the linked list, this is set up when the
  15
  // linked list is initialised
  16
  
  17
  myLinkedListPointers[11] <- -1
  18
  // the final heap pointer is set to -1 to show no
  19
  // further links
  

Bubble Sort#

对bubble sort完全不理解的话建议先看一遍这个视频：数据结构合集 - 冒泡排序(算法过程, 算法改进, 效率分析, 稳定性分析)_哔哩哔哩_bilibili

1
// The content of the array is pre-defined
2
DECLARE myList : ARRAY[0:8] OF INTEGER
3

4
DECLARE upperBound : INTEGER
5
DECLARE lowerBound : INTEGER
6
DECLARE index : INTEGER
7
DECLARE swap : BOOLEAN
8
DECLARE temp : INTEGER
9
DECLARE top : INTEGER
10

11
upperBound <- 8
12
lowerBound <- 0
13
top <- upperBound
14

15
REPEAT
16
    FOR index = lowerBound TO top - 1
17
        Swap <- FALSE
18
        IF myList[index] > myList[index + 1]
19
        THEN
20
            temp <- myList[index]
21
            myList[index] <- myList[index + 1]
22
            myList[index + 1] <- temp
23
            swap <- TRUE
24
        ENDIF
25
    NEXT
26
    top <- top -1
27
UNTIL (NOT swap) OR (top = 0)

Linear Search#

1
// The content of the array is pre-defined
2
DECLARE myList : ARRAY[0:8] OF INTEGER
3

4
DECLARE index : INTEGER
5
DECLARE target : INTEGER
6
DECLARE position : INTEGER
7

8
target <- "4"
9
position <- -1
10
FOR index <- 0 TO 8
11
  IF myList[index] = target
12
  THEN
13
    position <- index
14
  ENDIF
15
NEXT index
16

17
IF position = -1
18
THEN
19
  OUTPUT "Not Found"
20
ELSE
21
  OUTPUT position
22
ENDIF