# Problem Solving And Programming Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

Programming Constructs

A

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```
2
Q

Recursion

A

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.

3
Q

A

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.

4
Q

Local variables​

A

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.

5
Q

Global variables

A

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.

6
Q

Modular programming

A

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.

7
Q

Procedures and functions

A

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​.

8
Q

IDE

A

An​ Integrated Development Environment​, or IDE, is a ​program ​which provides a s​et 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

9
Q

Features of IDE:

A
• 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 error​s with a guide as to where in the code they are likely to have occurred through line numbers and highlighting.
10
Q

Use of object-oriented techniques

A

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.

11
Q

Features that make a problem solvable by computational methods

A

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.

12
Q

Problem recognition

A

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

13
Q

Problem decomposition

A

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.

14
Q

Divide and conquer​

A

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​’.

15
Q

A

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 ​log​2(​ 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​.

16
Q

Use of abstraction

A

Representational abstraction​ is a powerful technique that is key to solving a problem computationally. This is when excessive details are removed ​to​ simplify a problem​. Often, problems may be reduced down until they form problems that have already been solved which allows pre-programmed modules and libraries to be used rather than coding from scratch. Abstraction allows programmers to focus on the ​core aspects​ required of the solution rather than worrying about unnecessary details.

Using ​levels of abstraction​ allows a large, complex project and its functionality to be split up into simpler component parts. Individual components can then be dealt with by different teams, with details about other layers being hidden. This technique makes projects more manageable​.

Abstraction by generalisation​ may also be used to group together different sections of the problem with ​similar underlying functionality​. This allows for segments to be coded together and ​reused​, so ​saves time​. Once a problem has been abstracted into levels, abstract thinking is required to represent real-world entities with computational elements, such as tables and variables.

17
Q

Backtracking

A

Backtracking is a problem-solving technique implemented using ​algorithms​, often recursively​. It works by​ methodically visiting each path​ and​ building a solution based on the paths found to be correct​. If a path is found to be invalid at any point, the algorithm ​backtracks to the previous stage​ and visits an alternate path. ​Depth-first graph traversals​ are an example of backtracking.

This process can be visualised using the idea of a maze. There are many possible routes through a maze but only few lead to the correct destination. A maze is solved by visiting each path and, if a path leads to a dead end, ​returning back ​to the most recent stage where there are a selection of paths to choose from.

18
Q

Data mining

A

Data mining is a technique used to identify patterns or outliers in​ large sets of data​, termed big data​. Big data is typically collected from a ​variety of sources​. Data mining is used in software designed to ​spot trends or identify correlations​ between data which are​ not immediately obvious.

Data mining has also been used to reveal insights about people’s shopping habits and preferences based on their personal information. These insights can be used to inform marketing techniques.

However, as data mining often involves the​ handling of personal data​, it is crucial that it is dealt with in accordance with the present legislation regarding data protection. As of 2018, all data held and processed by organisations within the EU must follow the rules set by the ​GDPR​

Insights from data mining can be used to make ​predictions about the future based on previous trends​. This makes data mining a useful tool in ​assisting business and marketing decisions​. Data mining may uncover, for example, which products are bought at certain points of the year and this information can help shops prepare enough stock in advance.

19
Q

Heuristics

A

Heuristics are a ​non-optimal, ‘rule-of-thumb’ approach to problem-solving​ which are used to find an ​approximate solution​ to a problem when the ​standard solution is unreasonably time-consuming or resource-intensive​ to find. The solution found through using heuristics is ​not perfectly accurate or complete​; however, the focus is on finding a quick solution that is ‘good enough’ and heuristics provide a shortcut to this.

Heuristics are used to provide an estimated solution for intractable problems​ such as the renowned Travelling Salesman Problem as well as the A* algorithm, and are also used in machine learning and language recognition.

20
Q

Performance modelling

A

Performance modelling​ eliminates the need for true performance testing by providing mathematical methods​ to ​test a variety of loads on different operating systems​. Performance modelling provides a ​cheaper​, ​less time-consuming​ or ​safer ​method of testing applications. This is useful for safety-critical computer systems, such as those used on an airplane, where it is not safe to do a real trial run before the system can be implemented. The results of performance modelling can help companies judge the capabilities of a system​, how it will cope in different environments and assess whether it is safe to implement​.

21
Q

Pipelining

A

Pipelining​ is a process that allows for projects to be delivered faster, as modules are divided into individual tasks, with ​different tasks being developed in parallel​. Traditionally, the ​output of one process in pipelining becomes the input of another​, resembling a ​production line​.

22
Q

Visualisation

A

Data can be​ presented in a way that is easier for us to understand ​using ​visualisation​. This makes it possible to ​identify trends that were not otherwise obvious​, particularly amongst statistical data. Depending on the type of data, data may be represented as ​graphs, trees, charts and tables​. Visualisation is another technique that is used by businesses to pick up on patterns which can be used to inform business decisions.