Problem solving and programming Flashcards
Give a subsection of procedural programming
Structured programming
Sequence is a type of programming construct
What does it do?
Code is run line by line
Branching is a type of programming construct
What does it do?
Branching/selection
-Certain block of code is run if a SPECIFIC condition is met
(IF statements)
Iteration is a type of programming construct
What does it do?
Code is executed a certain number of times (countcontrolled) or while a condition is met (condition controlled)
Recursion is a programming construct
TRUE OR FALSE
TRUE
Give advantages of using recursion
-Problem can be solved with fewer lines of code
(perhaps making it less prone to errors)
What is essential for recursive subroutines?
They need to be clearly defined so that a base case is reached after a finite number of function calls
What does a stack frame contain?
-Parameters
-Local variables
-Return addresses
This info allows the subroutine to return to that particular point when that subroutine call is finished
Give disadvantages of recursion
-Stack overflow(call stack runs out of memory) if the base case isnt reached
-Extra function call overhead. Each recursive call involves storing the state of the function, including parameters and local variables, which consumes time and memory
-Can be hard to trace (specially when there is loads of function calls in a program) because the program’s flow involves multiple function calls.
-An iterative solution is easier to understand for humans
-Need well defined base case or could enter an infinite recursion
Recursive subroutines need to be clearly defined so that a base case is reached after a finite number of function calls
Can lead to stack overflow (call stack runs out of memory)
Why is tail recursion good?
Form of recursion which is implemented in a more efficient way by not requiring additional stack frames. (so avoids stack overflow)
Why are local variables considered good programming practices?
They have limited scope meaning they can only be accessed within the block of code they are defined in:
Ensures that subroutines are self contained so no code outside the subroutine will affect these variables
What is the difference between local and global variables?
Local= limited scope= can only be accessed within the block of code they are defined in
-Require less memory as they are deleted once subroutine terminates
Global= can be accessed accross whole program
-More memory is requeired as they are deleted once whole program terminates
In the event of a local variable within a subroutine with the same name as a global variable, the global variable will take precedence
TRUE OR FALSE
FALSE
Local variable will take precendence
Top down approach in Modular programming
A technique used to modularise programs
-The program is continually split into subproblems until each can be represented as an individual, selfcontained which performs a specific task
Subtasks are organised in a hierarchy from the most abstract (high-level) to the most detailed (low-level).
What is modular programming?
A programming technique used to split large and complex programs into smaller self contained modules
Give advantages of modular programming
-Makes code easier to understand
-Can divide a problem between a team as each component can be delt with individually and independently from the rest
-Once tested, components can be reused
-Easier to test (as it can be tested indepently of other components)
-Parts of program can be developed in parallel (so it takes less time for program to be delivered)
Classes can be used to create objects
What is this called?
Instantiation
What is meant by instantiation?
When an object from a class is created
An object can also be called…
an instance of a class
In OPP, how are attributes declared as private altered?
Using public methods
What is meant by encapsulation?
The process of combining attributes and methods that operate on data into a class. Protecting the integrity of data using access modifiers
What is a public access modifier?
Public:
Accessible from anywhere (inside and outside the class).
What is a private access modifier?
Private:
Accessible only within the class.
Used to protect data from being directly accessed or modified.
What is a protected access modifier?
Protected:
Accessible within the class and subclasses
Used to suggest the variable or method shouldn’t be accessed directly but isn’t strictly private.
What is an IDE?
Integrated development environment
-A program which provides a set of tools to make it easier for programmers to write, develop and debug code
Give examples of IDEs
Integrated development environments
IDLE
Microsoft visual studio
Eclipse
PyCharm
Microsoft visual studio
Eclipse
PyCharm
Are examples of:
Integrated development environments
Give common features of IDEs
Stepping
-Allows you to monitor the effect of each individual code by executing one line at a time
Variable watch
-Allows you to observe how the contents of a variable change during execution of program (GOOD FOR DEBUG)
Breakpoint
-Allows users to set a point in the program in which they want the program to stop (good for finding errors)
Source code editor
-Aims to make programming easier by using autocompletion, indentation, syntax highlightinh and automatic bracket completion
Debugging tools
-Some provide runtime detection of errors (shows where they likely ocurred suing line numbers and higlighting)
Why is variable watch a useful feature of an IDE when it comes to debugging?
-Allows you to observe how the contents of a variable change during execution of program (GOOD FOR DEBUG)
How does the Source code edition make programming easier in an IDE?
-Aims to make programming easier by using autocompletion, indentation, syntax highlightinh and automatic bracket completion
Explain breakpoints in IDEs
Breakpoint
-Allows users to set a point in the program in which they want the program to stop (good for finding errors)
What is meant by stepwise refinement?
Build on from a simpler problem to the overview
Give a differences between procedures and functions
Procedures CAN return a value but dont have to
Functions MUST return a value
Procedures can return multiple values
Functions must return a single value
When a parameter is passed by a value how is that different to when its passed by reference into a subroutine?
Value: effectively treated as a local variable, a copy of the value is passed into the subroutine and is then deleted when the subroutine terminates
-Any changes made to the variable inside the subroutine do not affect the original variable outside the subroutine
Reference: Address of parameter is given to subroutine, so the value of the parameter is updated at the given address
-Changes made to the variable in the subroutine affect the original variable because both refer to the same memory location.
The first stage of problem solving is….
Identifying whether or not a problem can be solved using computational methods
What is meant by a problem being computable?
A problem that can be solved using an algorithm
Problems can only be called computable when….
They can be solved within a finite, realistic amount of time
What do problems that can be solved computationally consist of?
Inputs, outputs and calculations
Once a problem is determined to be computable, what is the next stage?
Problem recognition
Stakeholders state what they want from finished product
This info is used to define ssytem requirements and problem by:
Analysing strenghts and weaknesses by the way the problem is currently being solved
Considering amount of data and types of data (e.g inputs, outputs) and store data involved
Once a problem has been determined to be computable and we have recognised the problem as it has been defined,
what happens next?
Problem decomposition
Problem is broken down into smaller subproblems which continues until each problem can be split into individual, selfcontained subroutines so that the problem is easier to understand
Explain divide and conquer as a problem solving technique
Divide: involves halving the size of the problem with every iteration
Conquer: Each subproblem is solved (conquered) often requersively
Merge: solutions to subproblems are recombined to form final solution
What is meant by ‘representational abstraction’?
Removing unnecessary details to simplify a problem
Often problems are reduced down to the point that preprogrammed modules and libraries can be used rather than coding from scratch
Using levels of abstraction allows large, complex problems to…
be split up into simpler components as we are removing unnecessary details to simplify problem
What is meant by abstraction by generalisation?
Grouping together different sections of the problem with similar functionalities
Prroblem solving techniques
What is backtracking?
Often done recursively
Works by visiting each path and building a solution based on the paths found to be correct
If a path is found to be invalid at some point, the algorithm backtracks
eg. Depthfirst algorithm uses it
Give the name of an algorithm which uses backtracking as a problem solving technique
Depth first graph traversal
What is meant by ‘data mining’?
A problem solving technique used to identify patterns or outliers in large sets of data
-Good for making predictions about future from previous trends
-Often used in marketing (e.g you can see people’s shopping habits)
What is meant by heuristics?
Non optimal approach to problem solving which finds an approximate solution
(The solution is not perfectly accurate/complete but its good enough)
-Used when the standards solution is timeconsuming or resourceintensive
What is meant by performance modelling?
Used to test safety critical systems
-Eliminates the need for actual performance testing by providing mathematical methods to test a variety of loads on different operating systems
-Used to identify potential inefficiencies or failures before implementing whole system
What is meant by pipeling as a problem solving strategy?
Allows projects to be delivered faster as modules are divided a into individual tasks which can then be developed in parallel
Within a module/subtask, there are stages in order (e.g., planning → design → development → testing).
As soon as one stage of a module is complete, the next stage begins, like an assembly line.( even if other modules are still in earlier stages)
(stages of different subtasks can overlap, even if the earlier stages of some subtasks haven’t been completed yet)
What is meant by visualisations as a problem solving strategy?
Data can be represented in a way that is easier for us to understand
-This makes it possible to identify trends that were not obvious before
-Data can be represented using trees, graphs, charts and tables…
-Used by businesses as well as data mining
Give a scenario of when performance modelling would be useful and why
Airplane
Because its used to test safety-critcal systems, those that would not be safe to do a real trial as it could lead to castastrophy
Give advantages of performance modelling
-Cheaper ( allows you to identify potential bottlenecks before further implementation)
-May reduce cost of expensive physical performance testing in the early stages. (when you dont know if it will work out)
-Less time consumming (Instead of running numerous physical tests/ full implementations, it provides quick insights through simulations..)
-Safer (avoids the risks of damage associated with testing on real systems)
Give advantages of using pipelining as a programming strategy
-Speeds up project delivery by overlapping tasks instead of waiting for one to finish before starting the next.
as different teams/individuals can work on separate tasks simultaneously.
Give disadvantages of using pipelining as a programming strategy
-Requires careful planning to avoid dependencies between tasks causing delays.
-Effective coordination to ensure the tasks align properly when combined.
Visualisation is a problem strategy used to present data in a way that is easier to understand.
Give ways in which the data can be represented
Graphs
Trees
Charts
Tables
Give problem solving strategies to solve problems computationally
Backtracking
Data mining
Heuristics
Perfomance modelling
Pipelining
Visualisation
Give problems that use heuristics
-A* algorithm (to determine shortest path)
-Travelling Salesman problem
Give examples of algorithms which use divide and conquer
-Quick sort
-Merge sort
-Binary search
What is an advantage of using divide and conquer in problem solving?
-Breaks down a large, complex problem into smaller, manageable subproblems, making it easier to understand and solve.
-Each smaller problem can be tackled independently.
Give disadvantages of using divide and conquer algorithms
Often they use recursion in the conquer stage
-Can lead to stack overflow
-Recursion can be hard to trace in large programs
What is the aim of using the top down design
To keep spliting problems into subproblems until each subproblem can be represented as a single and selfcontained blackbox/subroutine.
Where each task can be solved separetly
How would you solve a problem broken down using the top down design?
(because we broke down the problem we need to build up to its solution)
Start building it up from the lowest levels
Define ‘decision’
A result reached after some consideration
What is meant by concurrent processing?
The process of completing more than one task at a time
Each task is give a slice of processor time which makes it look like the tasks are being completed at the same time but they are actually being executed sequentially (one after the other)
What is the difference between concurrent processing and parallel processing?
Parallel= multiple processors complete multiple tasks at the same time
Concurrent= each task is give a slice of processor time which makes it look like the tasks are being completed at the same time but they are actually being executed sequentially (one after the other)
Give advantages of concurrent processing
-Can perform a higher number of tasks within the given time
-Less time is wasted for example when waiting for an input/user interaction as while doing this other tasks can be completed
Give disadvantages of concurrent processing
-Not all tasks are suited to being broken up and performed concurrently (like with parallel processing)
-Added overhead of coordinating and switching between processes
-Can take longer when there is a large number of tasks as processes cant be completed at once (as each task would get less time to execute (time-slicing)).
-If tasks depend on one another, some may need to wait for others to complete before they can proceed.
What is meant by the base case in recursion?
The terminating condition which doesnt use recursion to produce an output
Define recursion
When a subroutine calls itself
What is this called in IDEs?
Allows you to monitor the effect of each individual code by executing one line at a time
Stepping
Explain variable watch in IDEs
Variable watch
-Allows you to observe how the contents of a variable change during execution of program (GOOD FOR DEBUG)
Functions must return a single value
TRUE OR FALSE?
TRUE
Procedures must return a single value
TRUE OR FALSE?
FALSE
They can return more than a single value
