Unit 2 - Problem Solving Flashcards
What is computational thinking?
The ability to think logically about a problem and apply techniques for solving it
What are the 5 main ways to solve a problem?
- Enumeration (list all cases)
- Simulation
- Theoretical approach
- Creative approach
- Trial and error
What does simulation involve?
Designing a model for a system in order to understand its behaviour and then testing it to observe how the system responds to different situation
What does enumeration involve?
Running every possible solution until there is one that works
What does the decrease and conquer approach to algorithm design involve?
Breaking down a problem into smaller sub-problems which can be tackled individually and then applied to the greater problem
What is an algorithm?
A sequence of steps that can be followed to complete a task and always terminates
What does a good algorithm need to do?
- Have a clear set of steps which produces a successful outcome for any set of inputs
- Allows for invalid inputs
- Terminate
- Efficiently achieve the outcome in as few steps as possible
- Be designed in a way that it can be understood and edited by others
What do hierarchy charts do?
Break down a bigger problem into smaller subtasks, a visual representation of decomposition
What does an insertion sort entail?
Removing an item and replacing it in the correct position within the set
What type of sets is an insertion sort suited to?
Small sets
When is bubble sort used?
When there is a small set of values
What does a bubble sort entail?
Iterating through the set n-1 times and comparing a value to the ones which are next to it, if they need to switch a switch is carried out
What does a linear search entail?
Iterating through the items in the list and comparing them to the desired item, if they match then this item is returned
What does a binary search entail?
Splitting the set in two and then checking to see if the desired item is higher or lower, if it is lower the higher section of the set can be discarded and vice versa. This is repeated until the desired item is attained
Why do we test?
To reveal errors and prove that a system does not work
Define module testing
Ensuring a subprogram works correctly
Define program testing
Ensuring that each program within the system works in isolation
Define system testing
Ensuring that the whole system works and does what is required of it according to the specification
Why do programmers use testing plans?
To keep track of the result of tests and what parts of the system are/aren’t working
Define normal data
Data which the system should accept without any issue
Define boundary data
Data which is acceptable but sits either end of the range
Define erroneous data
Data which the system should not accept
How can trace table be useful to test an algorithm?
By tracing an algorithm you can test the predicted or actual outcome of the system at different stages during the program without implementation
Define abstraction
Identifying the difference between information that is relevant to the problem and that which is not and discarding what is not relevant
Define information hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
Give an example of information hiding
The London Underground Map
What is the link between high level languages and abstraction?
High level languages employ abstraction by ensuring that programmers only need to focus on what the computer is doing rather than how it is doing it, this contrasts with machine code
Define decomposition
Breaking down a problem into smaller sub-problems so that each sub-problem can be solved to accomplish an identifiable task
Define composition
Combining procedures which accomplish individual tasks to form a compound system which accomplishes the overall task
What is a finite state machine?
An abstract representation of how a system changes from one state to another in response to an external stimuli
What are the three main rules regarding finite state machines?
- They can only be in one state at a time
- It switches between states in response to an event of condition (this is called a transition)
- A finite state machine is defined by a list of states and conditions for each transition
Define representational abstraction
The process of removing unnecessary details so that only information that is required to solve the problem remains and the problem is in a state that can be solved
Define abstraction by generalisation
The concept of reducing problems by putting similar aspects of a problem into hierarchical categories
Define problem solving
The process of finding a solution to real-life problems
Define automation
Creating a computer model of a real-life situation and putting it into action
Define logical reasoning
The process of using a given set of facts to determine whether new facts are true or false
What does hand-tracing/dry running mean?
To follow a program through line by line to determine what is happening and identify problems before it is run
Give an example of abstraction by generalisation
Top down diagrams
Define top down diagram
Related to the modular approach to problem solving and is a diagram that starts with the main system at the top and breaks it down into smaller and smaller units
Define procedural abstraction
The concept that all solutions can be broken down into a series of procedures that can be executed one by one
Define functional abstraction
Breaking down a complex problem into a series of reusable functions
Define data abstraction
Hiding how data is represented so that it is easier to build a new kind of data object
Why is data abstraction beneficial for programmers?
Programmers can utilise the functions of data types without needing to know how they work
Define data composition
The process of combining data objects to create a compound structure
Define problem abstraction
Removing unnecessary details from a problem until the underlying problem is one that has already been solved
How are encapsulation and information hiding linked?
Encapsulation involves grouping data and methods together in classes which means hiding irrelevant information from other parts of the program
