TECHARRAZ

1. Randomized algorithms ::

Randomized algorithms rely on the statistical properties of random numbers. One example of a randomized algorithm is quicksort.
In quicksort we take a set of data, sort it selecting a pivot value, ie; we select a central value(as in having a central tendency) and then sort all the elements before and after it. Then, as the two halves are sorted, we perform the operation on the two new sets recursively.
In order to achieve good performance, quicksort relies on the fact that each time we partition the checks, we end up with two partitions that are nearly equal in size. To accomplish this, ideally we need to look up the median value of the check numbers before partitioning the checks. However, since determining the median requires scanning all of the checks, we do not do this. Instead, we randomly select a check around which to partition. Quicksort performs well on average because the normal distribution of random numbers leads to relatively balanced partitioning overall.

2. Divide-and-conquer algorithms ::

Divide-and-conquer algorithms revolve around three steps: divide, conquer, and combine.
In the divide step, we divide the data into smaller, more manageable pieces.
In the conquer step, we process each division by performing some operation on it.
In the combine step, we recombine the processed divisions. One example of a divide-and-conquer algorithm is merge sort.
Merge sort works as follows. In merge sort, we start with a set of data and divide it repeatedly until we get atleast one check, ie;least two elements in each sub-set which is caled pile.Once all piles contain a single check, we merge the piles two by two so that each new pile is a sorted combination of the two that were merged. With this process being repeated, the checks are sorted and so are the data subsets along with the sets.

3. Dynamic-programming solutions ::

Dynamic-programming solutions are similar to divide-and-conquer methods in that both solve problems by breaking larger problems into subproblems whose results are later recombined. So, it is the concept of the problem which is broken, and not the problem data set(in the literal sense of breakage, otherwise breaking the concept involves automatic segregation of data).
However, the approaches differ in how subproblems are related. In divide-and-conquer algorithms, each subproblem is independent of the others. Therefore, we solve each subproblem using recursion and combine its result with the results of other subproblems.
A dynamic-programming solution is better than a divide-and-conquer approach in a problem with independent sub-programs because the latter approach will do more work than necessary, as shared subproblems are solved more than once.

4. Greedy algorithms ::

Greedy algorithms make decisions that look best at the moment. In other words, they make decisions that are locally optimal in the hope that they will lead to globally optimal solutions. Unfortunately, decisions that look best at the moment are not always the best in the long run. Therefore, greedy algorithms do not always produce optimal results; however, in some cases they do. One example of a greedy algorithm is Huffman coding, which is an algorithm for data compression.
The most significant part of Huffman coding is building a Huffman tree. To build a Huffman tree, we proceed from its leaf nodes upward. We begin by placing each symbol to compress and the number of times it occurs in the data (its frequency) in the root node of its own binary tree. Next, we merge the two trees whose root nodes have the smallest frequencies and store the sum of the frequencies in the new tree’s root. We then repeat this process until we end up with a single tree, which is the final Huffman tree. The root node of this tree contains the total number of symbols in the data, and its leaf nodes contain the original symbols and their frequencies. Huffman coding is greedy because it continually seeks out the two trees that appear to be the best to merge at any given time.

5. Approximation algorithms ::

Approximation algorithms are algorithms that do not compute optimal solutions; instead, they compute solutions that are “good enough.” Often we use approximation algorithms to solve problems that are computationally expensive but are too significant to give up on altogether. This algorithm finds use in finding optimal solutions. The traveling-salesman problem is one example of a problem usually solved using an approximation algorithm.
Imagine a salesman who needs to visit a number of cities as part of the route he works. The goal in the traveling-salesman problem is to find the shortest route possible by which the salesman can visit every city exactly once before returning to the point at which he starts. Since an optimal solution to the traveling-salesman problem is possible but computationally expensive, we use a heuristic to come up with an approximate solution. A heuristic is a less than optimal strategy that we are willing to accept when an optimal strategy is not feasible or not defined accurately.
The traveling-salesman problem can be represented graphically by depicting the cities the salesman must visit as points on a grid. We then look for the shortest tour of the points by applying the following heuristic. Begin with a tour consisting of only the point at which the salesman starts. Color this point black. All other points are white until added to the tour. So, they are all initially black. Next, for each point X closest to Y, and not already in the tour, compute the distance between the last point Y added to the tour and the new point X. Repeat this process until all points have been colored black. Lastly, add the starting point to the tour. This gives the approximately shortest distance.

No Responses to “Algorithms”

No comments yet

Leave a Reply