Programming Techniques Flashcards
Stepwise Refinement
Breaks problem into progressively smaller sections until each section can be written in single procedure/function.
Top-down design
Produced through the process of stepwise refinement.
Function
Block of code which performs a single task. Returns a single value. Uses local variables.
Procedure
Block of code which performs a task. Receives parameter values. Uses local variables. It may or may not produce a single value
Benefits of using proc/func Features of struct progs
Can be tested separately. Easier to maintain the program. Main program is simpler and code clearly structured. Use of library routines saves time. Code is reusable. Produced faster and to higher standard as proc/func may be shared between coders.
Variable
An identifier / memory location representing a value needed by the program. Value may change while the program is running.
Parameter
Is an item of data supplied to a procedure or function. Data can be passed by reference or by value. Used as local variables.
Pass by value
Only actual value passed. Procedure/function can only modify a copy of original variable (and not the original variable itself).
Pass by reference
Provides procedure/function with actual address to original variable therefore allowing it to permanently alter its contents.
Local Variables
A variable defined within one part of the program (procedure/function) & is only accessible in that part. Data contained is lost when execution of that part of program is completed. The same variable names can be used in different procedures and functions. An example of a local variable could be a loop counter.
Global Variables
A variable defined at the start of the program which exists throughout the program (including within functions and procedures). Global variables allow data to be shared by modules. They are overridden by local variables with the same name
An example of a global variable could be VAT rate.
Use of stack
To help control the flow of instructions. When a subroutine is called the return address is placed on the stack followed by the parameters of the subroutine (if there are any). When the subroutine executes it first pops the parameters off the stack. When it finishes it pops the return address off the stack so control can pass back to the instruction at the calling address.
Backus-Naur Form
(BNF) is a notation technique used to unambiguously describe the syntax of programming languages.
Why is BNF needed
To unambiguously define the syntax of a computer language.
Recursion in BNF
::= 0|1|2|3|4|5|6|7|8|9
::= |
Syntax Diagrams – Purpose
To define terms unambiguously (for a computer language).
Infix Notation
The way we normally work e.g. 5 + 6
Reverse Polish Notation
Also known as postfix notation e.g. 5 6 +
RPN →infix conversion
- Completely parenthesize the infix expression according to order of priority you want. 2. Move each operator to its corresponding right parenthesis. 3. Remove all parentheses.
RPN Advantages
Simpler to evaluate by a machine (no need for brackets). Can be evaluated as they are entered, they are not limited to a certain number of operators in an expression.
RPN↔infix - stacks
Stacks are used in the evaluation of RPN expressions.
RPN↔infix - trees
Trees can be traversed in-order to obtain the infix and post-order to obtain the RPN (postfix).
In-order traversal
Place a dot under each node. Trace around tree starting to left of root. As you pass underneath a node output its data.
Post-order traversal
Place a dot on the right of each node. Trace around tree starting to left of root. As you pass to right of node output its data.
Post-order Algorithm
- Traverse the left sub tree until there isn’t one. 2. Traverse the right sub tree (if there is one). 3. Re-visit the root of the current branch. 4. Repeat 1, 2, 3 until every node has been visited.
In-order Algorithm
- Traverse the left branch until there is no left branch. 2. Visit the root of the current branch. 3. Traverse the right sub tree if there is one. 4. Repeat steps 1, 2 and 3 until every node has been visited.
