Implementations/Solutions

1. Largest ten

An effecient implementation of finding the largest 10 elements in a sequence.

2. Polynomials

Let p(x) be a polynomial of degree n, that is

p(x) = a₀ + a₁x + a₂x² + ... + a_n-1x^n-1 + a_nxⁿ

1. An implementation of a simple O(n²)-time algorithm for computing p(x) in the polynomial_one() function.
2. An implementation of an O(n log n)-time algorithm for computing p(x), based upon a more efficient computation of xⁱ, in the polynomial_two() function.
3. An effectient implementation based on the rewriting of p(x) as

p(x) = a₀ + x(a₁ + x(a₂ + x(a₃ + ... + x(a_n-1 + xa_n)...)))

which is known as Horner's method in polynomial_three().

3. Pig Latin

Pig Latin is a simple transformation of English text. Each word of the text is converted as follows: move any consonant (or cluster of consonants) that appears at the beginning of a word to the end, then append ay. E.g. string - ingstray, latin - atinlay, idle - idleay (see this Wikipedia entry on Pig Latin for more information and examples). The PigLatinEncoder class realizes the following functions:

• encode_word(), to convert a word to Pig Latin. Your conversion function should preserve the original capitalization of the word (lowercase, titlecase or uppercase).

• a function that takes in an English text from a file, splits it into words, converts each word from English to Pig Latin and then writes out a new file containing the Pig Latin equivalent of the text. Make sure to update your word encoding function to take into account words that end with one or more punctuation characters - e.g. air, - airay,. Also, preserve the empty lines in the original text.

The data directory contains some text samples: a larger file, 2701-0.txt, containing the text of Herman Melville's Moby Dick, a smaller file, 2701-0-ch1.txt, containing only the first chapter of the book, and a file containing the first chapter converted to Pig Latin, 2701-0-ch1-pl.txt.

4. Randomized In-Place Quick-sort

An effecient implementation of randomized quicksort, with the approach of median-of-three.

5. String sorting(with radix sort)

An effecient implementation of string sorintg. Sorting a list of n strings of different lengths in lexicographic order in O(d(n+N)) time, where d is the maximum number of characters over all the n strings and N is the length of the letter alphabet over the n strings.