- Intro
- Decomposition & Divide and Conquer
- Abstraction
- Backtracking
- Data Mining
- Heuristics
- Performance Modelling
- Pipelining
- Tasks
- End of topic assessment
Computational Methods
What you need to learn:
(a) Features that make a problem solvable by computational methods. (b) Problem recognition. (c) Problem decomposition. (d) Use of divide and conquer. (e) Use of abstraction. (f) Learners should apply their knowledge of: • backtracking • data mining • heuristics • performance modelling • pipelining • visualisation to solve problems.
Starter video -Be Inspired
For those of you that want to be part of the future of computing and computational thinking, you may want to start learning about the emerging field of Quantum Computing. Here's an interesting video that introduces the concept
Visualisation?
What to visualise? Programming is a complex activity requiring the acquisition of non trivial new concepts, new facts and new skills, and it involves learning relationships between many things which cannot be identified except by their relationships. Programming languages deal with the unfamiliar world of data structures and algorithms. This makes them less tractable for novices. Various diagramming techniques to represent algorithms have been used to overcome some of the problems. Usually, these representations were used to guide writing program code not necessarily done by the same person. The standardisation of graphical design notations using the flowchart was popular in some earlier Visualisation Techniques for Learning and Teaching Programming
Decomposition
Divide and Conquer
The divide-and-conquer strategy solves a problem by:
1. Breaking it into subproblems that are themselves smaller instances of the same type of problem
2. Recursively solving these subproblems
3. Appropriately combiningthe solutionsto subproblems to create a solution to the original problem.
The real work is done piecemeal, in three different places: in the partitioning of problems into subproblems; at the very tail end of the recursion, when the subproblems are so small that they are solved outright; and in the gluing together of partial answers. These are held together and coordinated by the algorithm’s core recursive structure
An example of divide and conquer
Sorting
Problem SORT:
- Input: an array A of integers.
- Output: an array with all elements of A in increasing order.
example:
+----+----+----+----+----+----+----+----+ A = | 19 | 1 | 29 | 30 | 6 | 15 | 2 | 5 | +----+----+----+----+----+----+----+----+ +----+----+----+----+----+----+----+----+ return | 1 | 2 | 5 | 6 | 15 | 19 | 29 | 30 | +----+----+----+----+----+----+----+----+
Merge-Sort
Algorithm M-Sort(A):
if a's length > 1, then:
return A.
else:
Let AL be the first half of A.
Let AR be the second half of A.
return Merge(M-Sort(AL), M-Sort(AR))
end of if
Abstraction
Computer scientists use abstraction to make models that can be used and re-used without having to re-write all the program code for each new application on every different type of computer.
They communicate their solutions with the computer by writing source code in some particular computer language which can be translated into machine code for different types of computers to execute.
Abstraction allows program designers to separate categories and concepts related to computing problems from specific instances of implementation. This means that the program code can be written so that it does not depend on the specific details of supporting applications, operating system software or hardware, but on an abstract concept of the solution to the problem that can then be integrated with the system with minimal additional work.
Definition for you:
Backtracking is used in a declarative type of programming language that will allow for more than one solution to be found, if a solution is found/not found the program will ‘backtrack’ and explore other paths/possibilities to try to find alternatives. http://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html
More Information
Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.
The classic textbook example of the use of backtracking is the eight queens puzzle, that asks for all arrangements of eight chess queens on a standard chessboard so that no queen attacks any other. In the common backtracking approach, the partial candidates are arrangements of k queens in the first k rows of the board, all in different rows and columns. Any partial solution that contains two mutually attacking queens can be abandoned.
Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution. It is useless, for example, for locating a given value in an unordered table. When it is applicable, however, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.
Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient[citation needed]) technique for parsing, for the knapsack problem and other combinatorial optimization problems. It is also the basis of the so-called logic programming languages such as Icon, Planner and Prolog.
Backtracking depends on user-given "black box procedures" that define the problem to be solved, the nature of the partial candidates, and how they are extended into complete candidates. It is therefore a metaheuristic rather than a specific algorithm – although, unlike many other meta-heuristics, it is guaranteed to find all solutions to a finite problem in a bounded amount of time.
Source:https://en.wikipedia.org/wiki/Backtracking
The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s.[3] The pioneer string-processing language SNOBOL (1962) may have been the first to provide a built-in general backtracking facility.
Data Mining
In short data mining - the process of looking for general trends in large sets of data. http://www.anderson.ucla.edu/faculty/jason.frand/teacher/technologies/palace/datamining.htm
More Information
Data mining is an interdisciplinary subfield of computer science. It is the computational process of discovering patterns in large data sets involving methods at the intersection of artificial intelligence, machine learning, statistics, and database systems.
The overall goal of the data mining process is to extract information from a data set and transform it into an understandable structure for further use. Aside from the raw analysis step, it involves database and data management aspects, data pre-processing, model and inference considerations, interestingness metrics, complexity considerations, post-processing of discovered structures, visualization, and online updating. Data mining is the analysis step of the "knowledge discovery in databases" process, or KDD.
Another one on Data Mining
Heuristics
In short, heuristics: - think about it and try different alternatives, use common sense, generalise rather than be specific. http://www.education.com/reference/article/problemsolving-strategies-algorithms/
More Information
In computer science, artificial intelligence, and mathematical optimization, a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow, or for finding an approximate solution when classic methods fail to find any exact solution. This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.
A heuristic function, also called simply a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution.
The objective of a heuristic?
The objective of a heuristic is to produce a solution in a reasonable time frame that is good enough for solving the problem at hand. This solution may not be the best of all the actual solutions to this problem, or it may simply approximate the exact solution. But it is still valuable because finding it does not require a prohibitively long time.
Heuristics may produce results by themselves, or they may be used in conjunction with optimization algorithms to improve their efficiency (e.g., they may be used to generate good seed values).
Results about NP-hardness in theoretical computer science make heuristics the only viable option for a variety of complex optimization problems that need to be routinely solved in real-world applications.
Heuristics underlie the whole field of Artificial Intelligence and the computer simulation of thinking, as they may be used in situations where there are no known algorithms.
Trade-off
The trade-off criteria for deciding whether to use a heuristic for solving a given problem include the following:
Optimality: When several solutions exist for a given problem, does the heuristic guarantee that the best solution will be found? Is it actually necessary to find the best solution?
Completeness: When several solutions exist for a given problem, can the heuristic find them all? Do we actually need all solutions? Many heuristics are only meant to find one solution.
Accuracy and precision: Can the heuristic provide a confidence interval for the purported solution? Is the error bar on the solution unreasonably large?
Execution time: Is this the best known heuristic for solving this type of problem? Some heuristics converge faster than others. Some heuristics are only marginally quicker than classic methods.
In some cases, it may be difficult to decide whether the solution found by the heuristic is good enough, because the theory underlying that heuristic is not very elaborate.
Examples
Simpler problem
One way of achieving the computational performance gain expected of a heuristic consists in solving a simpler problem whose solution is also a solution to the initial problem. Such a heuristic is unable to find all the solutions to the initial problem, but it may find one much faster because the simple problem is easy to solve.
Traveling salesman problem
An example of approximation is described by Jon Bentley for solving the traveling salesman problem (TSP) so as to select the order to draw using a pen plotter. TSP is known to be NP-Complete so an optimal solution for even a moderate size problem is intractable. Instead, the greedy algorithm can be used to give a good but not optimal solution (it is an approximation to the optimal answer) in a reasonably short amount of time. The greedy algorithm heuristic says to pick whatever is currently the best next step regardless of whether that precludes good steps later. It is a heuristic in that practice says it is a good enough solution, theory says there are better solutions (and even can tell how much better in some cases).
Search
Another example of heuristic making an algorithm faster occurs in certain search problems. Initially, the heuristic tries every possibility at each step, like the full-space search algorithm. But it can stop the search at any time if the current possibility is already worse than the best solution already found. In such search problems, a heuristic can be used to try good choices first so that bad paths can be eliminated early (see alpha-beta pruning).
Newell and Simon: heuristic search hypothesis
In their Turing Award acceptance speech, Allen Newell and Herbert A. Simon discuss the heuristic search hypothesis: a physical symbol system will repeatedly generate and modify known symbol structures until the created structure matches the solution structure. Each successive iteration depends upon the step before it, thus the heuristic search learns what avenues to pursue and which ones to disregard by measuring how close the current iteration is to the solution. Therefore, some possibilities will never be generated as they are measured to be less likely to complete the solution.
A heuristic method can accomplish its task by using search trees. However, instead of generating all possible solution branches, a heuristic selects branches more likely to produce outcomes than other branches. It is selective at each decision point, picking branches that are more likely to produce solutions.
Virus scanning
Many virus scanners use heuristic rules for detecting viruses and other forms of malware. Heuristic scanning looks for code and/or behavioral patterns indicative of a class or family of viruses, with different sets of rules for different viruses. If a file or executing process is observed to contain matching code patterns and/or to be performing that set of activities, then the scanner infers that the file is infected. The most advanced part of behavior-based heuristic scanning is that it can work against highly randomized polymorphic viruses, which simpler string scanning-only approaches cannot reliably detect. Heuristic scanning has the potential to detect many future viruses without requiring the virus to be detected somewhere, submitted to the virus scanner developer, analyzed, and a detection update for the scanner provided to the scanner's users.
Source:https://en.wikipedia.org/wiki/Heuristic_(computer_science)]
Performance Modelling
In short, performance modelling is designing test criteria to see if a program/ task is successful or not.
The below video is on Performance Testing in companies
Pipelining
pipelining – pipelining is the same as running a multi-tasking system, a task can be in one of three states:
Running,
where the task is being processed.
Ready,
where it waiting to be processed.
Blocked,
where it is awaiting an input.
A possible way of utilising multi-core processors more efficiently. http://msdn.microsoft.com/en-us/library/ff963548.aspx http://link.springer.com/chapter/10.1007%2F978-3-642-24322-6_14#page-1
Tasks
Your teacher may ask you to do one or more of the following tasks
Worksheet
Learning Poster
1. Complete a learning poster (a single slide) in which all of the learning objectives for this topic are explained
*Refer to the theory PowerPoint and the "What you will learn objectives" slide.
Research Power Point
1. Complete a research powerpoint on the topic selected by your teacher using the following template.
End of topic assessment
Well done on completing this topic!
Your teacher will direct you as to which task needs to be handed in
What to submit
-learning poster
-research powerpoint
-worksheet
