A statistical compression method that converts characters into variable length bit strings. Most-frequently occurring characters are converted to shortest bit strings; least frequent, the longest. Compression takes two passes. The first pass analyzes a block of data and creates a tree model based on its contents. The second pass compresses the data via the model. Decompression decodes the variable length strings via the tree.
Read more:
http://www.answers.com/topic/huffman-coding
2007-04-22
Radix Sort
A radix sort is an algorithm, a procedure, which can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. Integer representations can be used to represent things such as strings of characters (names of people, places, things, the words and characters that you are reading now, dates, etc.) and specially formatted floating point numbers as well as integers. So, anything which can be represented as an ordered sequence of integer representations can be rearranged to be in order by a radix sort. Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least significant digit and move the processing towards the most significant digit. MSD radix sorts process the integer representations starting from the most significant digit and move the processing towards the least significant digit. The integer representations that are processed by sorting algorithms are often called, "keys," which can exist all by themselves or be associated with other data. LSD radix sorts typically use the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, such as the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. MSD radix sorts use lexicographic order, which is suitable for sorting strings, such as words, or fixed-length integer representations. A sequence such as b, c, d, e, f, g, h, i, j, ba would be lexicographically sorted as b, ba, c, d, e, f, g, h, i, j. If lexicographic ordering is used to sort variable-length integer representations, then the representations of the numbers from 1 to 10 would be output as 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key for the purpose of determining sorted order.
Read more:
http://www.answers.com/topic/radix-sort
Read more:
http://www.answers.com/topic/radix-sort
Quick Sort
Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(n log n) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(n log n) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the possibility of requiring quadratic time. Quicksort is a comparison sort and, in efficient implementations, is a stable sort.
Read more...
Shell Sort
Shell sort is a sorting algorithm that, with its original implementation, requires O(n2) comparisons and exchanges in the worst case. A minor change given in V. Pratt's book produces an implementation with worst case performance of O(nlog2 n). This is better than the O(n2) comparisons required by naive algorithms but worse than the optimal O(n log n) (see comparison sort). Although it is easy to develop an intuitive sense of how this algorithm works, it is very difficult to analyze its execution time.
Shell sort is a generalization of insertion sort, with two observations in mind:
1. Insertion sort is efficient if the input is "almost sorted".
2. Insertion sort is inefficient, on average, because it moves values just one position at a time.
Shell sort improves insertion sort by comparing elements separated by a gap of several positions. This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.
Consider a small value that is initially stored in the wrong end of the array. Using an O(n2) sort such as bubble sort or insertion sort, it will take roughly n comparisons and exchanges to move this value all the way to the other end of the array. Shell sort first moves values using giant step sizes, so a small value will move a long way towards its final position, with just a few comparisons and exchanges.
Read more...
Shell sort is a generalization of insertion sort, with two observations in mind:
1. Insertion sort is efficient if the input is "almost sorted".
2. Insertion sort is inefficient, on average, because it moves values just one position at a time.
Shell sort improves insertion sort by comparing elements separated by a gap of several positions. This lets an element take "bigger steps" toward its expected position. Multiple passes over the data are taken with smaller and smaller gap sizes. The last step of Shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted.
Consider a small value that is initially stored in the wrong end of the array. Using an O(n2) sort such as bubble sort or insertion sort, it will take roughly n comparisons and exchanges to move this value all the way to the other end of the array. Shell sort first moves values using giant step sizes, so a small value will move a long way towards its final position, with just a few comparisons and exchanges.
Read more...
2007-04-21
Knapsack Problem
Knapsack Problem(mathematics) The problem, given a set of integers {A1, A2, …, An} and a target integer B, of determining whether a subset of the Ai can be selected without repetition so that their sum is the target B.
(Wikipedia) The knapsack problem is a problem in combinatorial optimization. It derives its name from the maximization problem of choosing possible essentials that can fit into one bag (of maximum weight) to be carried on a trip. A similar problem very often appears in business, combinatorics, complexity theory, cryptography and applied mathematics. Given a set of items, each with a cost and a value, then determine the number of each item to include in a collection so that the total cost is less than some given cost and the total value is as large as possible.
The decision problem form of the knapsack problem is the question "can a value of at least V be achieved without exceeding the cost C?"
A simple knapsack implementation with recursion. Source: http://codebus.googlepages.com/knapsack
2007-01-14
Josephus Problem
The fllowing description is copied from www.answers.com.
The Josephus problem is a theoretic problem occurring in computer science and mathematics.
There are n people standing in a circle waiting to be executed. After the first man is executed, k−1 people are skipped and the k-th man is executed. Then again, k−1 people are skipped and the k-th man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.
The task is to choose the place in the initial circle so that you survive (remain the last one), given n and k.
History
The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. As the legend goes, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they will form a circle and start killing themselves using a step of three. As Josephus did not want to die, he was able to find the safe place, and stayed alive, later joining the Romans who captured him.
Solution
Using arrays in Java, copied from csdn
http://codebus.googlepages.com/josephusarray
Solution 2:
Using circularly-linked list
http://codebus.googlepages.com/josephus
The Josephus problem is a theoretic problem occurring in computer science and mathematics.
There are n people standing in a circle waiting to be executed. After the first man is executed, k−1 people are skipped and the k-th man is executed. Then again, k−1 people are skipped and the k-th man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.
The task is to choose the place in the initial circle so that you survive (remain the last one), given n and k.
History
The problem is named after Flavius Josephus, a Jewish historian living in the 1st century. As the legend goes, he and his 40 comrade soldiers were trapped in a cave, surrounded by Romans. They chose suicide over capture and decided that they will form a circle and start killing themselves using a step of three. As Josephus did not want to die, he was able to find the safe place, and stayed alive, later joining the Romans who captured him.
Solution
Using arrays in Java, copied from csdn
http://codebus.googlepages.com/josephusarray
Solution 2:
Using circularly-linked list
http://codebus.googlepages.com/josephus
Subscribe to:
Posts (Atom)