Embedded Files
GENERAL KNOWLEDGE /
1. WRITING TECHNIQUES, BUILDING BLOCKS, CORRECTNESS, ANALYSIS
An algorithm is a way to execute a series of activities in a specified way.
An algorithm can be written in:
natural language
flow-chart
pseudo code
programming language
Using natural language it is easy to express the desired steps, but it has the less effectiveness.
Flow-charts are very good to present the logic but it needs more effort to translate it to any programming languages.
Pseudo codes have many forms and syntaxes, it is the nearest to programming languages but they are independent from them, and needs programming skills to master them; used by scientists and students worldwide.
Algorithm building blocks:
sequental statements: statements are following each other (linear flow)
conditional statements: depending on the result of the condition, the algorithm divides into branches (divided flow)
iteration: statements are organized into a loop (repeated flow)
An algorithm is correct: it always produces the expected output for the range of inputs and it eventually terminates.
The formal reasoning and mathematical reasoning are the only way to prove whether the algorithm is correct. Forms of formal reasoning:
proof by induction
proof by contradiction
proof by exhaustion
Programmers use empirical analysis to find faults in an algorithm (tests), but only formal reasoning can prove total correctness. An empirical analysis uses specific inputs to find out whether the algorithm fails to produce the correct results, which means the algorithm is not correct. If the tests show that for the chosen inputs the results are correct, we assume that the algorithm is correct. With this type of analysis we can not prove the correctness of an algorithm.
An empirical analysis is one based on actual experimentation and observation of the results. In the world of algorithms, that means the algorithm must actually be translated into a programming language and executed on a computer.
The empirical analysis is about dividing the test for cases: a case defines specific input values and the test is to determine whether the algorithm provides the expected outputs. Choosing the right test cases results a good look on the robustness (trustwortiness) of the algorithm. We must assume that the algorithm works the same way between the test cases, therefore he empirical analysis will not prove that the algorithm is correct but raising the robustness to a level which makes the algorithm trustworty enough.
The important cases are:
edge cases (e.g. in a list the first and the last elements)
average case (e.g. in a list an average element like the middle one
special cases (e.g. not in the list, or there is no list)
2. EFFECIENCY, RUNTIME COMPLEXITY
Next to the correctness, an algorithm must be efficient as well: takes the least amount of execution time and memory usage possible while still yielding a correct answer. The execution time depends on the hardware and software background on the computer, properties of the programming language, and the algorithm written by the programmer. After the previous ones are given or a prior decided, the programmer ultimately can have effect on the number of executed statements which leads to the compexity of the algorithm.
The runtime complexity marks how many time a method must run in order to finish a task.
The O letter marks the complexity. The n letter means the amount of input data.
For defining the complexity, use the scale of need.
Runtime is dependent on existence of parallel execution method. However, because the given programming language directs how the parallel execution is done, and there can be cases when the language can not execute parallel even if we let it doing it, we must assume the maximum runtime without parallel ways.
O(1), O(nº):
constant runtime
process which must be executed once only, independent of the amount of data
EXAMPLE FOR O(1) IN JAVA:
O(n), O(n¹):
linear runtime
the numbers of executions depends on the number of data
typically processing collections or arrays by their elements in 1D
linear search on unsorted collection or array in 1D
EXAMPLE FOR O(N) IN JAVA:
O(m + n):
iterating through 2 different collections or arrays with 2 independent loops
EXAMPLE FOR O(M + N) IN JAVA:
O(n²):
quadratic runtime
when every element must be compared with all other elements in a collection or array in 1D
usually goes for minimum needed complexity of sorting processes (using iteration or recursion does not matter)
2 nested loops (e.g. processing all elements of collections or arrays in 2D)
The less optimized sorting algorithms (e.g. Selection Sort) linearly steps an index from a base point, then repeats the execution from the next base point. With element of the low index all other elements will be compared. The execution number would be: (n - 1) + (n - 2) + (n - 3) + ... + (n - (n-1)) = (n² - n) / 2.
EXAMPLE FOR O(N²) IN JAVA:
O(nª), O(2ⁿ):
exponential runtime
typically upon generating variations of the input elements
O(log(n)):
logarithmic runtime
logarithmic search (binary search) on sorted collection or array in 1D
Merge Sort (mathematically proven that the most optimized sorting algorithm needs log(n) executions)
O(n * log(n)):
quasilinear runtime
standard sorting algorithms
Scientists categorize the runtime complexities into two groups:
polynomial: the time does not increase faster than nª (nº, log(n), n¹, n², n³, nª)
superpolinomial: the time does increase faster than nª (aⁿ, n!, ...)
Superpolynomial runtime means a time scale comparable or greater than the age of the universe even on relatively smaller amount of input, therefore these runtimes are unreasonables.
The polynomial runtime is reasonable.
3. BRUTE FORCE, HEURISTICS, UNDECIDABLE PROBLEMS
Brute force solution: tries all possible solutions and then compares all to the conditions to choose the right one. In many cases this approach is exponential, superpolynomial. Therefore, instead of finding the perfect solution, we search for an approximate solution.
One way of approximate solutions is using a heuristic. This is a condition (a restrain) developed before running the algorithm, e.g. based on human-like consideration. A well-choosen pre-condition can push the algorithm into polynomial territory. A heuristic is a shortcut to solve a problem that will often give you an answer that is "close enough" to the right one.
Traveling Salesperson Problem (TSP): to find the shortest root between cities. Using brute force, the algorithm must find all possible roads between all cities, the runtime grows exponencially. Heuristic: find only the nearest city from the actual point ("nearest neighbour heuristic"). This significally decreases the number of checked roads. The result will not be perfect but approximate, there can be some situations in which an other set of roots would be shorter but the new result will be optimal if we need a solution in reasonable time. In some cases this heuristic gives the worst possible solution. There are other heuristics to solve the TSP (e.g. "ant colony optimization").
Knapsack problem: there are a set of weight and value pairs, and items which are rendered to these pairs, find the set of items with which the total weigth is below the given limit and the total value is maximized. Heuristic: sort by value/weight ratio when selecting the next item to pack.
Game playing problem: find the best ways to win or lose considerable agains a human player. In this case the brute force solution would anticipate all possible steps the human could make from a certain moment until the final move. Heuristic: "minimax".
Facility location problem: based on given locations of stations and given number of servers (or facilities and warehouses), find the optimal positions to the servers (warehouses) by minimizing the costs and maximizing devivery speed. Heuristic: "local search".
An undecidable problem is one that should give a "yes" or "no" answer, but yet no algorithm exists that can answer correctly on all inputs.
The halting problem (Alan Turing): based on its code and an input, will a particular program ever finish running? With the proof of contradiction, Turing showed that a software which analyses another code with a given particular input, can not determine if the checked algorithm leads to infinite loop. We assume that such algorithm exists: based on the code of the analysed program, if we give an input to that, our algorithm returns true or false, regarding that the program halts or results in infinite loop. Then we create another algorithm which gets only the analysed code as an input. This new algorithm runs the analyser, giving it the analysed program and a pre-determined input: if the analyser returns true (the program will halt) the new algorithm will restart itself in a loop (which will lead to infinite loop if the checked program does not enter into infinite loop); if the analyser returns false (the program enters into an infinite loop), the new algorithm halts. Then, we give itself to this new algorithm as an input (so it tries to determine whether itself will have a halt or steps into infinite loop). The new algorithm will not be able to determine whether the original program halts or not (paradox).
There is one way to determine whether a program entered into an infinite loop and that is not with analysing the code: whether the runtime of the program steps over a tolerable time interval.
4. SEQUENTIAL, PARALLEL AND DISTRIBUTED COMPUTING, SCALABILITY
The standard programming model is sequential computing: the computer executes each operation of the program in order, one at a time.
Multi-core processors can take advantage of parallel computing, a computational model that breaks programs into smaller sequential operations (threads) and performs those smaller operations in parallel. The parts must be independent from each other.
Because the parallel parts (threads) might need different processing time, the system in the background will not use dedicated processors or cores per part, instead, tries to optimizing the program by sending parts to cores immediately as cores became idle. In some programming languages and solutions it is possible to dedicate algorithm parts to certain processors though, as per the need designed by the programmer.
Parallelization is possible within a browser as well. A browser executes softwares coded in PHP, HTML, JS and so on so naturally it is capable to offer parallel execution. Threads in browser environment is called workers. In the background, workers are ultimately projected to threads.
Speedup: full sequential time / paralellized time.
An Intel processor core is able to run two threads virtually parallel, this technology is called hyperthreading. Thanks to this, developers (and browsers) can see double of the physical number of cores under Intel architecture. As a result, when testing a well-parallelizable algorithm, the maximum speedup will trend to reach two in case of two physical cores, four in case of four psysical cores, and will not trend toward the number of logical processors. The hyperthreaded system works with the most efficiency if the threads do different type of tasks (e.g. mathematical operations vs. image content detection) instead of handling the same task (image content detection on all threads).
When looking from wider perspective, all active softwares can have multiple threads, and the total number of threads is way more than the available workers or threads the architecture offers. The active applications and services has software threads. The processors will share CPU time with these threads, get a thread package, work with them, then freeze them and get the next package. Therefore when measuring execution time of an application, the results will depend on the scale of parallelization of the algorithm, the number of physical and virtual CPU cores, the already existing threads of other softwares, and the priority difference between the totality of threads.
Distributed computing: distributing the parallelized algorithm between multiple computing devices in a network. Although every computing devices can have multiple cores, the data flow on the network has its speed limitations with which the programmer and-or the distribution system must deal with.
A computer cluster can reduce the inter-computer data flow limitations. A cluster means computers at the same location, built together into a common frame, using special cables and interfaces, and used for one computation task a time. No internet data flow, no individual general-purpose computers, speed is greater.
Cloud computing: offered service where the distribution is handled by the service provider, uses multiple clusters between which the threads are divided by tasks or functionality.
An algorithm is designed on a certain scale, e.g. processing football winners data in a city. If the final aim is to work with other scales as well (e.g. data from a country or the world), considerations must be made.
An algorithm is scalable if it can handle the task on any scale (from micro to macro).
A solution is scalable in case it is prepared to have results on changing scales: on macro by utilizing parallel and distributed techniques, while on micro concentrates on single and straightforward execution.
5. ERRORS
Syntax error: a mistake in typed code that violates the rules of the programming language.
Logic error: a mistake in an algorithm or program that causes it to behave unexpectedly or return the incorrect value.
Run-time error: a mistake in a program that happens only when the program is actually run, such as a program attempting to access memory that does not exist.
Overflow error: error that results when the number of bits is not enough to represent the number.
Google Sites
Report abuse