Algorithm Design and Problem-Solving

Computational Thinking Skills

Abstraction

• Used to filter out unnecessary information // Meaning only essential information is included
• Simplifies the solution - makes it easier to implement / design
• System is tailored to need of user.

Decomposition

• Breaking down a complex problem into smaller problems / subproblems which are easier to program
• Makes problems easier to solve
• Leads to concept of program modules - subproblems can be assigned to individual teams

Benefits of Decomposition

• Makes task easier to understand and solve — smaller problems are easier to solve
• Smaller problems are easier to program, test and maintain
• Sub-problems can be given different teams // can be solved separately
• Modules can be tested independently making it easier to test

Algorithms

• algorithm — sequence of defined steps that describe how to solve a problem

Stepwise Refinement

• process of developing a modular design by splitting a problem into sub-tasks

• the sub-tasks are repeatedly split into smaller sub-tasks until each is just one statement / element from which the task may be programmed

  this could include statements such as…

  • set total / count to 0
  • input a number
  • check if…
  • repeat from step # a set number of times // repeat for total of # iterations
  • output the total/count/element/string
  • calculate the rounded value of …
  • assign value to an element
  • use function … to return a value
  • open file in read / write mode
  • loop through all lines in a file
  • loop ends when…

  (obviously, be specific to the question, for example,s ay how many times it repeats and from which step)

Data Types and Structures

Defining Record Structures (using arrays of given records and type)

• declaring a record — containing all data items required // containing items of different data types

• declare an array of the given record — each array element represents data for one instance of an objects (e.g. would store one customer order)

Advantages of Records

• a set of data of different data types is stored under a single identifier
• allows multiple instances to be referenced using the single identifier

Uses of BOOLEAN

• to terminate a conditional loop when value has been found
• when the variable can only take one of two possible values

Arrays

• simplify an algorithm, makes it easier to amend or add data
• are easier to understand, test and debug
• it is possible to iterate through the values using a loop - make data organization easier

Files

Advantages of storing data

• Data in file is saved after the computer is switched off ( stored permanently)
• Data does not need to be manually re-entered when program is re-run

WRITE mode overwrites a file completely/ overwrites any existing data in file

How to store a set of data in a file

• Data items are combined to form a single string (set of data is saved as a single line in file)
• Items are separated by a special character- Items are separated by a special character

Abstract Data Types

Linked Lists

• Consists of nodes — each node contains data and a pointer to the next node
• Has a pointer to the start of list (start pointer)
• Last node in list has a null pointer (indicated there are no further nodes in list)
• Data is added by manipulating pointers (Data in nodes does not need to be moved)
• Nodes are traversed in sequence (based on pointers)
• Unused nodes are stored on free list

Adding / inserting a new node

• check for a empty node
• assign data item to first empty node in free list (from now on referred to as
• set the pointer of X to point to the node that will come after it after insertion (Y)
• set pointer of node that previously pointed to Y to point to X
• set pointer of free list to point at next empty node

Advantages of linked lists

• It is easier to add/delete data in a linked list
• Only the pointers need to be changed if data contents are changed (determine ordering of data)

Disadvantages of linked lists

• Pointers need to be stored as well as data
• More complex to implement / setup

Implementing a Linked List

• Declare two 1D arrays — one for data, one for pointers.
• Elements from same index represent one node (data in index position in array 1 maps to pointer in index position in second array)
• Declare variable for start pointer
• Declare variable for next free node pointer
• Define appropriate value for null pointer
• Use routines to add/delete/search within list

Use Record based Implementation

• Define record type with fields for data and pointer
• Declare a 1D array of defined record type

Queues

• Each queue elements contains one data item
• Has a pointer to the start and end of queue
• Works on a FIFO basis
• May be circular
• Front of queue and End of queue pointers are equal when there is only one data item in the queue

Adding / inserting a value from a queue

• check queue is not full
• increment variable / pointer that signifies end of queue
• increment variable storing the number of items in queue
• store data value being added in location pointed to by end of queue pointer
• in arrays - set element of array at end of queue to value / item being added

Removing an item from a queue

• value pointed to by the front of queue pointer is removed first —- can be assigned to a variable
• front of queue pointer is incremented

Required Operations

• adding an item — a check needs to be carried out to ensure queue is not full
• removing an item — a check needs to be carried out to ensure queue is not empty

Implementing a queue

• Declare 1D array of required / specified size
• Declare integer variable for front of queue pinter
• Declare variable for end of queue pinter
• Declare variable for size of queue to limit max number of items allowed
• Initialize variables e.g. the size of the queue

Stack

• Used to store string data which needs to be accessed in several modules within a program ?

Implementing a stack

• Declare a 1D array of type string
• Number of elements in array corresponds to the size of the required stack
• Declare variable for a stack pointer
• Declare variable for size of stack / max value of pointer
• Used stack pointer as index to array
• Initialize pointers and variables to indicate empty stack
• Store each item on stack as one array element
• Push and Pop routines used to operate stack (need to check if stack is full or empty first)

Why files may not appear correctly if using a stack

• if a multiple lines are stored at once, lines transferred to file will appear out of the sequence as stack operate on a FILO basis.
• Stack is full - not all lines can be stored on stack, resulting file will be missing original lines
• Stack is empty - stack is being read faster than being written into, so blank lines may be inserted into file.

Programming

Features that made codes understandable

• Indentation
• White space
• Comments
• Meaningful variable names, use of camelCase (ewww)
• Capitalized keywords (are you serious)
• Standard way to indicate special cases (such as unused array elements) — allows recognition when processing, meaning there is no unexpected data?

Importance of ‘Good Practice’

• makes code easier to understand, describes purpose of sections of code and of identifiers
• makes code easier to debug/test and maintain

Constants

• used for values that are only entered once
• avoid input error or accidental change of value
• easier to maintain program when constant has to change
• make program easier to understand

Library Routines / Program Libraries

• Contains pre written functions / subroutines which may be imported and called in other code
• More complex functions can be used in code through use of program library

Benefits of using Libraries

• Tried and tested, likely to be free from errors
• Perform functions you may not be able to program yourself
• Readily available and speed up development time

Use

• Used for tasks that are performed / repeated in several places within the code
• When part of an algorithm performs a specific task
• Reduces complexity of a program
• Testing / debugging is easier

Constructs

Selection constructs

• IF statement
• CASE statement
  • consists of clauses that are checked in sequence
  • if a value satisfies the first clause, the other clauses will never be tested
  • the OTHERWISE clause may never be performed if all possible values are addressed via the other previous clauses.

Iterative constructs

• WHILE pre condition loop — used when number of iterations is not known
• REPEAT post condition loop — used when number of iterations is not known
• FOR count-controlled — used for known number of iterations

Structured Programming

Functions / Procedures

• a function / procedure interface refers to the parameters and return value — e.g. a function takes two integer parameters and returns a boolean value
  • it provides a mechanism to allow calling a program to pass data
  • defined / provides parameters , giving their data type and order

Benefits

• can be called repeatably when required
• is only designed and tested once (then used repeatedly)
• any changes to function code need to be made once only (easier to maintain)

A function returns a value a procedure can output values

Software Development

Program Development Life Cycle

Benefits

• makes projects / programs easier to plan and manage
• clear deliverables produced at end of each state (can show prototypes to client)

Stages

1. Analysis

• Documents produced include: the problem definition, client requirements, documentation relating to current system, e.g. ER diagrams.
• Developers discusses program requirements with customer / client

2. Design

• An identifier table is produced
• Data structures and choice of programming language are decided
• Includes algorithm, programs and pseudocode
• User interface is designed

3. Coding

• Syntax errors can occur

4. Testing

• A trace table is produced

Waterfall Design

• each state must be completed before new one is begun (linear)
• full documentation, lots of planning involved
• client only involved at start and end of process

Benefits of Waterfall Design

• easy to manage, stages do not overlap and are completed one at a time
• each stage has clear/specific deliverables (detailed documentation of project)
• leave little room for client to change mind and project is planned out thoroughly, meaning a smoother development process (client also has better idea of the finished product when designing it)

Disadvantages of Waterfall Design

• no working program / software until late in life cycle — slower to market than competitors (does not allow early versions)
• more difficult to cope with changes in requirements
• needs high amount of feedback / involvement from client

Iterative Design

• development cycle is run repeatedly until full program has been developed.
• split into stages which are repeated

Benefits of Iterative Design

• working programs developed early on in cycle, produced at each iteration
• easier to test and debug
• more flexible to changes in client requirements
• customer involved during all stages / at each iteration

Drawbacks of Iterative Design

• a lot of planning needs to be done in order to section project into clear stages / iterations (while system needs to be defined at start)
• makes it easy for client to change mind often about end result

Rapid Application Development (RAD)

• modules are developed in parallel as prototypes
• minimal planning is carried out — allow for changes to requirements
• flexible development process
• used for time critical/sensitive development
• client involved during all stages of development

Benefits of RAD

• quicker development possible — multiple areas worked on simultaneously
• prototype produced in early stages
• easier to change requirements
• early review possible

Drawbacks of RAD

• difficult to estimate cost /time needed to complete project
• makes it easy for client to change mind often about end result
• documentation often omitted

Program Design

Purpose of Structure Charts

• To model relationship between modules and see how a problem is broken down
• To determine whether a module is a function or procedure

Symbols

• Curved arrow : iteration / looping
• Downward arrow : result from one state is input / passed to next stage
• Upward arrow : more work required on previous state to complete the current stage

State-Transition Diagrams

• arrows represent transitions between states
• each arrow can have an input or an output — always in the format of i | o
• X signifies start

Program Testing and Maintenance

Types of Maintenance

• Adaptive
  • Accommodates legislative changes or user requirement changes
  • Allows programs / software to be updated if new technology or library routines are made available
• Perfective
  • Changes are made to after it has been made available to public
  • UI changes
  • Performance improvements
• Corrective
  • Used when program does not operate as expected // contains a bug

Types of Testing

• Beta Testing
  • testing carried out by small group of potential users
  • users check that program works as intended and identify any errors present
  • users will provide feedback / suggestions for improvement
  • problems identified are addressed before the program is sold / released
• Integration Testing
  • each module in program is tested individually during devolvement and is debugged as necessary
  • individual modules are combined into single program (or added to existing program) and tested as whole
• Stub Testing
  • used when program contains modules with errors/ incomplete modules
  • dysfunctional modules are replaced with dummy modules
  • dummy modules return known / expected result or output a statement to show they have been called
• Walkthrough Method
  • The structure of the program needs to known
  • Test data and expected results all paths through program can be tested
  • How errors are identified
    • Program is checked by creating a trace table , going through program one line at a time
    • records / check variables as they change
    • errors may be indicated when…
      • variable is given an unexpected value
      • unexpected path through program / faults in logic of program
• White-box Testing
  • detailed testing of how each procedure works
  • tests logical of all possible paths through the program module
• Black-box Testing
  • tests a module’s input and outputs
• Alpha Testing
  • testing carried out by development team
  • check program works as indeed and address/identify any errors within the program before releasing it to the public

Types of Errors

Syntax Errors

• Selection and iteration
• Incorrect block structure — missing keywords like ENDIF, ENDPROCEDURE
• Data type errors
• Incorrect parameter use
• Incorrect brackets or misspell keywords

A program with no syntax errors…

• obeys the rule/grammer of the programming language used
• the program will run without an error being flagged

Run-time Errors

• Program performs an invalid operation
• E.g. division by zero or endless loop

Test Data

• Normal — value within an acceptable range (should be accepted)
• Abnormal — value outside acceptable range (should be rejected)
• Boundary/Extreme — minimum / maximum acceptable value (should be accepted)

Pseudocode Programming

Data Types

Variable Declarations / Constants

DECLARE Counter : INTEGER  

DECLARE TotalToPay : REAL

DECLARE GameOver : BOOLEAN

CONSTANT HourlyRate = 6.50

Assignments

<identifier> ← <value> so for example: Counter ← Counter + 1

Arrays

DECLARE StudentNames : ARRAY[1:30] OF STRING

DECLARE NoughtsAndCrosses : ARRAY[1:3,1:3] OF CHAR

StudentNames[1] ← "Ali"

NoughtsAndCrosses[2,3] ← 'X'

User-defined types

Non-composite data types

A user-defined non-composite data type with a list of possible values is called an enumerated data type.

TYPE Season = (Spring, Summer, Autumn, Winter)

A used-defined non-composite data type referencing a memory location is called a pointer. The pointer should be declared as follows:

TYPE TIntPointer = ^INTEGER

Composite data types

A composite data type is a collection of data that can consist of one or more data types, grouped under one identifier.

TYPE StudentRecord
  DECLARE LastName : STRING
  DECLARE FirstName : STRING
  DECLARE DateOfBirth : DATE
  DECLARE YearGroup : INTEGER
  DECLARE FormGroup : CHAR
ENDTYPE

There is also the set data type which is like set() in python

TYPE LetterSet = SET OF CHAR
DEFINE Vowels ('A', 'E', 'I', 'O', 'U'): Letter Set

Using user-defined data types

DECLARE Pupil1 : StudentRecord  
DECLARE Pupil2 : StudentRecord
DECLARE Form : ARRAY[1:30] OF StudentRecord
DECLARE ThisSeason : Season
DECLARE NextSeason : Season
DECLARE MyPointer : TIntPointer

Pupil1.LastName ← "Johnson"
Pupil1.FirstName ← "Leroy"
Pupil1.DateOfBirth ← 02/01/2005
Pupil1.YearGroup ← 6
Pupil1.FormGroup ← 'A'

Pupil2 ← Pupil1

FOR Index ← 1 TO 30
  Form[Index].YearGroup ← Form[Index].YearGroup + 1
NEXT Index

ThisSeason ← Spring
MyPointer ← ^ThisSeason
NextSeason ← MyPointer^ + 1

Input and output

INPUT Answer

OUTPUT Score

OUTPUT "You have", Lives, " lives left"

Selection

IF <condition> THEN
  <statement(s)>
ENDIF

IF <condition> THEN
  <statement(s)>
ELSE
  <statement(s)>
ENDIF

INPUT Move
CASE OF Move
  'W' : ...
  'S' : ...
  'A' : ...
  'D' : ...
  'OTHERWISE': CALL Beep
ENDCASE

Loops

FOR Index ← 1 TO 100
  OUTPUT Index
NEXT Index

REPEAT
  OUTPUT "Please enter the password"
  INPUT Password
UNTIL Password = "Secret"

WHILE Number > 9
  Number <- Number - 9
ENDWHILE

Procedures and Functions

PROCEDURE <identifier>()
  <statements(s)>
ENDPROCEDURE

CALL <identifier>()

PROCEDURE <identifier>(<param1>: <type>, ...)
  <statements(s)>
ENDPROCEDURE

CALL <identifier>(value1, ...)

By default pass by value is assumed this can be modified by writing BYREF

FUNCTION <identifier(<params>: <types>, ...) RETURNS <type>

  RETURN <vlue>
ENDFUNCTION

File handling

DECLARE LineOfText : STRING
OPENFILE "FileA.txt" FOR READ
OPENFILE "FileB.txt" FOR WRITE

WHILE NOT EOF("FileA.txt")
  READFILE "FileA.txt" LineOfText
  IF LineOfText = "" THEN
    WRITEFILE "FileB.txt", "------------------------"  
  ELSE
    WRITEFILE "FileB.txt", LineOfText
  ENDIF
ENDWHILE

CLOSEFILE "FileA.txt"
CLOSEFILE "FileB.txt"

Handling random files

DECLARE Pupil : Student 
DECLARE NewPupil : Student
DECLARE Position : INTEGER

NewPupil1.LastName ← "Johnson"
NewPupil1.FirstName ← "Leroy"
NewPupil1.DateOfBirth ← 02/01/2005
NewPupil1.YearGroup ← 6
NewPupil1.FormGroup ← 'A'

OPENFILE "StudentFile.Dat" FOR RANDOM
FOR Position ← 20 TO 10 STEP -1
  SEEK "StudentFile.Dat", Position
  GETRECORD, "StudentFile.Dat", Pupil
  SEEK "StudentFile.Dat" Position + 1
  PUTRECORD "StudentFile.Dat", Pupil
NEXT NextPosition

SEEK "StudentFile.Dat", 10
PUTRECORD "StudentFile.Dat", NewPupil

CLOSEFILE "StudentFile.Dat"

Object-oriented Programming

CLASS Pet
  PRIVATE Name : STRING
  PUBLIC PROCEDURE NEW(GivenName: String)
    Name ← GivenName
  ENDPROCEDURE
ENDCLASS

CLASS Cat INHERITS Pet
  PRIVATE Breed: INTEGER
  PUBLIC PROCEDURE NEW(GivenName: STRING, GivenBreed: STRING)
    SUPER.NEW(GivenName)
    Breed ← GivenBreed
  ENDPROCEDURE
ENDCLASS

MyCat ← Cat("Kitty", "Shorthaired")