2.2 Problem Solving and Programming Flashcards
What is iteration?
Repeating code a set number of times or until a condition is met
What is selection/branching?
Taking different paths through the code based on a condition
What is sequence?
The order the instructions are in
What is a variable?
A space in memory allocated to store a value that can change and be recalled in the program
What is a constant?
Fixed values that do not change during run time
What are naming conventions?
Important when programming that you agree within a project team on suitable naming conventions
Variable and constant can’t start with a number or symbol and cannot contain spaces
What is recursion?
Where a subroutine calls itself
Method of solving a problem where the solution depends on solving increasingly smaller instances of the same problem
What are the characteristics of recursive algorithms?
Base case (stopping condition)
For any input values other than the one that meets the base case, subroutine should call itself
General case
Must have finite number of iterations or a memory error will occur (stack overflow)
What is a base case?
Condition to determine when the algorithm should stop calling itself
Point when you know the answer to that part of the problem
Where the problem has got as small as it can get and therefore starts to unwind
What is the stopping condition used to halt a recursive algorithm called?
Sentinel or rogue value
What is a general case?
Way of defining the problem which references a decreasing in size version of the problem
Statement that expresses the solution to a problem in terms of a reference to a smaller version of that same problem
What are the benefits of a recursive approach opposed to an iterative approach?
Can be CLOSER TO NATURAL LANGUAGE AND EASY TO UNDERSTAND
Can be SHORTER AND EFFICIENT
Can be good to iterate through a tree structure (good when algorithm needs to branch off e.g. a flood fill or tree)
Can provide a solution when iterative code is very long and complex
What are the drawbacks of a recursive approach opposed to an iterative approach?
NOT MEMORY EFFICIENT - lot of local variables
Uses stacks to store all the data and therefore if a recursive algorithm calls itself too many times then it may run out of memory on the stack
Some data will need to be stored for a long time until algorithm unravels
Can be slower to execute because of maintenance of stack that needs to go on during the execution
Can be DIFFICULT TO CODE AND DIFFICULT TO TRACE
How can a recursive algorithm be used in binary search trees?
On each comparison, sent left or right so values in other subtree don’t need to be searched
Tree must be balanced to be as efficient as binary search
What is a balanced tree?
Every leaf is around the same distance away from the root as any other leaf
Doesn’t need same number of nodes on each side but should be same length
What is an unbalanced tree?
One or more leaves are much further away from the root than other leaf
How can recursion be used for a binary search?
Algorithm returns True if value found and False if not
Takes two arguments: node (current node being examined) and search_item (item being searched for)
As data stored in tree, refer to each element as node rather than item
Node is structure containing data (simple value attached to node); right (reference to node to right); left (reference to node to left)
If no node to right, right value = Null
If no node to left, left value = Null
Where local variables declared?
Inside the subroutine
What is the scope of a local variable?
Cannot be accessed outside the subroutine
What happens to a local variable when the subroutine has finished executing?
Value in local variable deleted and cannot be recalled - meaning memory used only during subroutine then deleted
How do subroutines access local variables?
Variables have to be passed/returned between subroutines
Can local variables be named the same?
Yes, if they are in different subroutines
Where are global variables declared?
Outside of the subroutine
What is the scope of global variables?
Can be access from inside any subroutine
What happens to a local variable when the subroutine has finished executing?
Value remains in the variable - stored in memory throughout the entire program
When do global variables require memory?
Memory allocated at the beginning of the program and throughout the program
What is a problem with using global variables?
Makes integrating modules tricking as the other module may have a global variable of the same name
If there are two variables with the same name (one local and one global), which one will data be written to unless specified?
Local
What are the different ways that data can be passed into a subroutine?
Passing by value
Passing by reference
What is passing by value?
A copy of the value is sent as a parameter and when changes are made inside the subroutine, they don’t change the original value
Creates increased demand on RAM
Parameter has local scope
What is passing by reference?
A pointer to the memory location holding the value is passed as a parameter and when changes are made inside the subroutine, they also change the original value
What are subroutines?
Named section of code that can be called by writing the subroutines name in a program statement
Makes the code more readable and usable as the code is broken into smaller sections
What are the types of subroutine?
Procedure
Function
What is a procedure?
Set of instructions that will be executed when the procedure is called
DOESN’T return a value when called
What is a function?
Set of instructions that will be executed when the function is called
DOES return a value when called
What is modularity?
Technique for breaking down a complex system into smaller components called modules, which can each be developed independently and contain everything required to execute one part of the overall application
What does IDE stand for?
Integrated Development Environment
What is an IDE?
Specialist piece of software that can help you code, interpret your code and show you how it would run
What are the IDE tools?
Editor
Error diagnostics
Run-time environment
Translators
What is an editor?
Lets you write and edit code
When is an editor used?
When writing code
What are the functions of an editor?
Highlighting key words (colour)
Autocompletion (keywords/brackets)
Auto indentation (to keep code organised and help identify program flow)
Line numbering (to help when debugging code)
What does error diagnostics do?
Enables you to DEBUG code
When is error diagnostics used?
When writing code
What are the features of error diagnostics?
Error description
What line error is on
Breakpoint
What is a breakpoint?
Added to code to pause the execution of code at a certain point
What does a breakpoint enable the developer to do?
Examine/trace/watch values stored in variables at that point in code
Step through the code line by line to identify the exact place where the error occurs
Step though the code line by line to watch the values in the variables to identify when and how they change
What does step into mean?
Steps into execution of a subroutine when called - allows developed to trace the variables and identify the exact actions within the subroutine call
What does step out mean?
Steps out of a subroutine execution and back to the main code
What does step over mean?
Steps to the next line of code
What is tracing?
Traces/watches the values of variables at any certain point within code to see what values are stored within those variables or how values in those variables change as the program executes
When is a run-time environment used?
When testing code
What is a run time environment?
Allows the coder to test their code by entering inputs and seeing what the outputs will be
Allows the developer to test their code WITHOUT NEEDING TO OPEN AN ADDITIONAL PIECE OF SOFTWARE OR COMPILER
When coder is happy with code, can be exported
What is a translator in an IDE?
IDE needs to be able to translate your code into machine code to enable the code to run in the run-time environment
Converts source code to machine code that a computer can process
What are other features of an IDE?
Enables TEAM OF DEVELOPERS TO WORK TOGETHER as they may be able to check in and out files as they are working on them
Supports VERSION CONTROL so previous code can be relocated if needed
Often generates DOCUMENTATION (e.g. data dictionary)
What are the characteristics of a problem solvable by computational methods?
Clear definition of problem
- end goal?
- successful solution?
- current situation/problem?
- likely problems whilst solving?
Able to identify calculations
- perform processing/calculations?
- in required amount of time?
Data requirements
- enough storage?
- storing data?
Use of abstraction and decomposition
- remove unnecessary data?
- break problem down?
What does it mean a computer can be solved by computational methods?
If an algorithm can be developed that SOLVES ALL INSTANCES of the problem in a FINITE number of steps/REASONABLE amount of time
What is an intractable problem?
A problem that can’t be solved by a computer in a reasonable amount of time
What are the different ways we can solve problems?
Enumeration
Simulation
Theoretical approach
What is enumeration?
Where problems are solved using brute force and exhaustive search
Checking through all possibilities until you find the correct one
How can a simulation be used to solve a problem?
A computer could be used to create a simulation
Used to model a system, predict behaviour and outputs
How can a theoretical approach be used to solve a problem?
If a problem can be solved by a mathematical formula or theory then it will be solved by computational methods
What is problem recognition?
Identifying what the problem is that we need to solve
What are things to think about in problem recognition?
What the problem is
How it can be solved using computational methods
What other techniques can help problem recognition?
Visualisation
Abstraction
Decomposition
What is decomposition?
Breaking a problem down into smaller sub-tasks which are easier to solve
What is a divide conquer algorithm?
Reduces the size of the problem with each iteration
What are examples of divide and conquer algorithms?
Binary search
Quick sort algorithm
What is backtracking?
Incrementally building up towards a solution, abandoning partial success when the solution cannot be completed and then going back to a previous successful point
What are the uses of backtracking?
Good for route finding problems
Finding an alternative route in a network if part broken
What is big data?
The collection of large amount of data on a particular topic
Humans cannot search through all this data and make connections
What is data mining?
Allows a computer to analyse big data
Spot patterns and trends, make connections and use those connections to enable businesses etc to make decisions
What is heuristics?
Makes use of previous knowledge/experience to find a solution that is not always optimum but is good enough
What are the uses of heuristic algorithms?
AI
Language recognition
Big data analysis
Shortest path algorithms
Machine learning
When is performance modelling completed?
Before the application is released
What is performance modelling?
Predicting how our computer system will perform as the level of usage increases using mathematical formulas
What are the questions asked during performance modelling?
Will it be able to cope with the number of users?
Will it run at an acceptable speed?
Will it scale well as more people start to use it?
Where is the breaking point? (STRESS TESTING)
Will it crash when the user enters erroneous data?
What is pipelining?
Splitting a task up into smaller tasks so the output of one task is the input of the next
Allows multiple tasks to be executed simultaneously and therefore speeds up performance
What is software pipelining?
Same concept as instruction pipelining
Task must be able to be split up into a series of sub tasks
Each sub task must lead to the next
What is visualisation?
The ability to picture a problem and its solution in a visual way, making it easier to spot patterns, make connections, solve the problem or analyse data
What are data visualisation algorithms?
Used in most software (or video games) which are based on GUI
Provide more intuitive, user-friendly visual representation of data
Wide range of techniques and algorithms used to represent data in a visual way often using maths concepts (2D/3D coordination, trigonometry, proportionality)
