Problem Solving And Programming Flashcards
Programming Constructs
A crucial part of solving a problem is simplifying it to represent it in a way that makes it easier to understand and thus program. The following constructs are used to represent a program’s control flow in a popular subsection of procedural programming called structured programming:
- Sequence
Code is executed line-by-line, from top to bottom. - Branching
A certain block of code is run if a specific condition is met, using IF statements. This is also known as ‘selection’. - Iteration
A block of code is executed a certain number of times or while a condition is met. Iteration uses FOR, WHILE or REPEAT UNTIL loops.
Iteration can be either:
- Count-controlled
Iteration is repeated a given number of times.
for i in range (0,10):
print i
next i
- Condition-controlled
Iteration continues until a given condition is met.while i <= 20: print “Not true”; i=i+1 endwhile
Recursion
Recursion is a programming construct in which a subroutine calls itself during its execution. This continues until a certain condition - called the stopping condition - is met, at which point the recursion stops. Recursion produces the same result as iteration, but is more suited to certain problems which are more easily expressed using recursion.
Each time the function calls itself, a new stack frame is created within the call stack, where parameters, local variables and return addresses are stored. This information allows the subroutine to return to that particular point during its execution. A finite number of stack frames are created until the stopping condition, or base case, is reached at which point the subroutine unwinds. This refers to the process of information from the call stack being popped off the stack.
Recursion advantage and disadvantage
The advantage of using recursion for certain problems is that they can be represented in fewer lines of code, which makes them less prone to errors. However it is essential that recursive subroutines are clearly defined so as to reach a stopping condition after a finite number of function calls.
There are some disadvantages to recursion, the biggest being its inefficient use of memory. If the subroutine calls itself too many times, there is a danger of a stack overflow, which is when the call stack runs out of memory. This would cause the program to crash. Tail recursion is a form of recursion which is implemented in a more efficient way in which less stack space is required. Another problem with recursion is that it is difficult to trace, especially with more and more function calls.
Local variables
Local variables have limited scope which means that they can only be accessed within the block of code in which they were defined. If a local variable is defined within a subroutine, it can only be accessed within that subroutine. Therefore, multiple local variables with the same name can exist in different subroutines and will remain unaffected by each other. Using local variables is considered to be good programming practice because it ensures subroutines are self-contained, with no danger of variables being affected by code outside of the subroutine.
Global variables
Global variables, on the other hand, can be accessed across the whole program. All variables used in the main body of a program are automatically declared to be global. These are useful for values that need to be used by multiple parts of the program. On the whole, however, using global variables is not recommended because they can be unintentionally overwritten and edited. As global variables are not deleted until the program terminates, they require more memory than local variables which are deleted once the subroutine has been completed.
Modular programming
Modular programming is a programming technique used to split large, complex programs into smaller, self-contained modules. Modularity is essential to making a problem easier to understand and approach. A modular design also makes it easier to divide tasks between a team and manage, whilst simplifying the process of testing and maintenance, as each component can be dealt with individually. This improves the reusability of components, as once a module has been tested, it can be reused with confidence.
A popular technique used to modularise programs is called the top-down approach, in which the problem is continually broken down into sub-problems, until each can be represented as an individual, self-contained blackbox which performs a certain task.
This process is also known as stepwise refinement. These modules form blocks of code called subroutines, which can be categorised as either functions or procedures.
Procedures and functions
Procedures and functions are both named blocks of code that perform a specific task. While procedures do not have to return a value, functions must always return a value. Procedures can return multiple values whereas a function must return one, single value. Procedures are typically given data as parameters for manipulation while functions commonly make use of local variables.
IDE
An Integrated Development Environment, or IDE, is a program which provides a set of tools to make it easier for programmers to write, develop and debug code. Examples of IDEs include PyCharm, Eclipse, IDLE and Microsoft Visual Studio
Features of IDE:
- Stepping
This allows you to monitor the effect of each individual line of code by executing a single line at a time. - Variable watch
Sometimes used to pinpoint errors, this is a useful feature to observe how the contents of a variable change in real-time through the execution of a program. - Breakpoint
IDEs allow users to set a point in the program at which the program will stop. This can either be based on a condition or set to occur at a specific line. This can help to pinpoint where an error is occurring. - Source code editor
The editor aims to make the coding process easier by providing features such as autocompletion of words, indentation, syntax highlighting and automatic bracket completion. - Debugging tools
Some IDEs also provide run-time detection of errors with a guide as to where in the code they are likely to have occurred through line numbers and highlighting.
Use of object-oriented techniques
Object-oriented languages are built around the idea of classes. A class is a template for an object and defines the state and behaviour of an object. State is given by attributes which give an object’s properties. Behaviour is defined by the methods associated with a class, which describe the actions it can perform.
Classes can be used to create objects by a process called instantiation. An object is a particular instance of a class, and a class can be used to create multiple objects with the same set of attributes and methods.
In object-oriented programming, attributes are declared as private so can only be altered by public methods. This is called encapsulation. Encapsulation is a technique used throughout programming to implement the principle of information hiding. This is when programs are made less complex by protecting data from being accidentally edited by other parts of the program. Top-down design implements the same principle of encapsulation, as each module is designed to be self-contained.
Features that make a problem solvable by computational methods
Not all programs can be solved using computers. The first stage of problem solving is identifying whether or not a problem can be solved using computational methods. A problem that can be solved using an algorithm is computable. Problems can only be called computable if they can be solved within a finite, realistic amount of time. Problems that can be solved computationally typically consist of inputs, outputs and calculations.
Although some problems are computable, it may be impractical to solve them due to the amount of resources or length of time they require in order to be completed. The number of problems that are in fact solved computationally are constrained, therefore, by factors such as processing power, speed and memory. Breakthroughs in technology have made it feasible to solve more problems computationally than ever before.
Problem recognition
Once a problem has been determined to be computable, the next stage is to clearly identify what the problem is. Stakeholders state what they require from the finished product and this information is used to clearly define the problem and the system requirements. Requirements may be defined by:
● Analysing strengths and weaknesses with the current way this problem is being solved
● Considering types of data involved including inputs, outputs, stored data and amount of data
Problem decomposition
Once a problem has been clearly defined, it is continually broken down into smaller problems. This continues until each subproblem can be represented as a self-contained subroutine. This technique is called problem decomposition and aims to reduce the complexity of the problem by splitting it up into smaller sections which are more easy to understand. By identifying subproblems, programmers may find that certain sections of the program can be implemented using pre-coded modules or libraries which saves time which would otherwise have been spent on coding and testing.
Decomposition also makes the project easier to manage, as different software development teams can be assigned separate sections of the code according to their specialisms. These can be individually designed, developed and tested before being combined to produce a working piece of software at the end. Decomposition enables multiple parts of the project to be developed in parallel, making it possible to deliver projects faster. This technique makes debugging simpler and less-time consuming, as it is easier to identify, locate and mitigate errors in individual modules. Without problem decomposition, testing can only be carried out once the entire application has been produced therefore making it hard to pinpoint errors.
Divide and conquer
Divide and conquer is a problem-solving technique used widely across computer science. This strategy can be broken down into three parts: divide, conquer and merge. ‘Divide’ involves halving the size of the problem with every iteration. Each individual subproblem is solved in the ‘Conquer’ stage, often recursively. The solutions to the subproblems are then recombined during the ‘Merge’ stage to form the final solution to the problem.
One common use of divide and conquer is in binary search, in which the middle value of the sorted list to be searched is compared to the value to be found. If this value is smaller than the search value, the lower half of the list is discarded and the upper half of the list is recursively searched using the same technique: the midpoint is found and half of the list is discarded. If the middle value is found to be larger than the search value, the upper half of the list is discarded and the lower half is recursively searched. This continues until either the search value is found or the list is broken down until it contains one element, which means that the value does not exist in the list.
Divide and conquer is applied to problem-solving in quick sort and merge sort. The principle of divide and conquer is also used in problems which can be reduced by less than half in every iteration. This technique is sometimes called ‘Decrease and Conquer’.
Divide and conquer adv
The biggest advantage of using divide and conquer to solve problems is that the size of the problem is halved with each iteration which greatly simplifies very complex problems. This means that as the size of a problem grows, the time taken to solve it will not grow as significantly. The number of recursive calls made by a function that halves with each iteration is log2( n). Therefore, the time complexity of algorithms that use divide and conquer is of the order O(logn). As divide and conquer mostly makes use of recursion, it faces the same problems that all recursive functions face: stack overflow will cause the program to crash and large programs are very difficult to trace.
