Python - List Exercises

List Exercises
	Chapter 14. Lists

List Exercises

Accumulating Unique Values. This uses the Bounded Linear Search algorithm to locate duplicate values in a sequence. This is a powerful technique to eliminate sorting from a wide variety of summary-type reports. Failure to use this algorithm leads to excessive processing in many types of applications.
Procedure 14.1. Unique Values of a Sequence, seq
1. Initalize
  
  set a ← an empty sequence.
2. Loop. For each value, v, in seq .
  
  We'll use the Bounded Linear Search for v in a.
  1. Initialize
    
    i ← 0.
    
    Append v to the list a.
  2. Search. while a[i] ≠ v, increment i.
    
    At this point a[i] = v. The question is whether i = len( a ) or not.
  3. New Value? if i = len( a ), then v is unique.
  4. Existing Value? if i ≠ len( a ), then v is a duplicate of a[i]; a[-1] can be removed.
3. Result. Return array a, which has unique values from seq .
Binary Search. This is not as universally useful as the Bounded Linear Search (above) because it requires the data be sorted.
Procedure 14.2. Binary Search a sorted Sequence, seq , for a target value, tgt
1. Initialize
  
  l←0.
  
  h←len( seq ).
  
  m←(l+h)÷2.
2. Loop. While l+1<h and seq [m] ≠ tgt
  1. If tgt < seq [m], then h←m
  2. If tgt > seq [m], then l←m
  3. m←(l+h)÷2.
3. If tgt = seq [m], then return m
  
  If tgt ≠ seq [m], then return -1 as a code for “not found”.
Quicksort. The super-fast sort routine

As a series of loops it is rather complex. As a recursion it is quite short. This is the same basic algorithm in the C libraries.

Quicksort proceeds by partitioning the list into two regions: one has all of the high values, the other has all the low values. Each of these regions is then individually sorted into order using the quicksort algorithm. This means the each region will be subdivided and sorted.

For now, we'll sort an array of simple numbers. Later, we can generalize this to sort generic objects.
Procedure 14.3. Quicksort a List, a between elements lo and hi
1. Partition
  
  Initialize. middle ← (hi+lo)÷2.
  
  ls ← lo
  
  hs ← hi
  
  Swap To Partition. while ls < hs
  1. If a [ls].key ≤ a [middle].key, increment ls
  2. If a [ls].key > a [middle].key, swap ls with middle
  3. If a [hs].key ≥ a [middle].key, decrement hs
  4. If a [hs].key < a [middle].key, swap hs with middle
2. Quicksort Each Partition
  
  QuickSort( a , lo, middle )
  
  QuickSort( a , middle+1, hi )
Recursive Search. This is also a binary search: it works using a design called “divide and conquer”. Rather than search the whole list, we divide it in half and search just half the list. This version, however is defined with a recusive function instead of a loop. This can often be faster than the looping version shown in exercise 2.
Procedure 14.4. Recursive Search a List, seq for a target, tgt , in the region between elements lo and hi
1. Empty Region? If lo +1 = hi , then return -1 as a code for “not found”.
2. Middle Element. m ← ( lo + hi )÷2
3. Found? If seq [m] = tgt , then return m
4. Lower Half? If seq [m] < tgt , then return recursiveSearch ( seq , tgt , lo , m )
5. Upper Half? If seq [m] > tgt , then return recursiveSearch ( seq , tgt , m , hi )
Sieve of Eratosthenes. This is an algorithm which locates prime numbers. A prime number can only be divided evenly by 1 and itself. We locate primes by making a table of all numbers, and then crossing out the numbers which are multiples of other numbers. What is left must be prime.
Procedure 14.5. Sieve of Eratosthenes - List Version
1. Initialize
  
  Create a list, prime of 5000 booleans, all True, initially.
  
  p ← 2
2. Generate Primes. while 2 ≤ p < 5000
  1. Find Next Prime. while not prime[p] and 2 ≤ p < 5000: increment p.
    
    At this point, p is prime.
  2. Remove Multiples
    
    k ← p + p
    
    while k < 5000
    1. prime[k] ← false
    2. k ← k + p
  3. Next p. increment p
3. Report
  
  At this point, for all p if prime[ p ] is true, p is prime.
  
  while 2 ≤ p < 5000
  1. ifprime[ p ], print p
Polynomial Arithmetic. We can represent numbers as polynomials. We can represent polynomials as arrays of their coefficients. This is covered in detail in [Knuth73], section 2.2.4 algorithms A and M.

Example: 4x³ + 3x + 1 has the following coefficients: ( 4, 0, 3, 1 ).

2x² - 3x - 4 is represented as ( 2, -3, -4 ).

The sum is 4x³ + 2x² - 3, ( 4, 2, 0, -3 ).

The product is 8x⁵ - 12x⁴ - 10x³ - 7x² - 15x - 4, ( 8, -12, -10, -7, -15, -4 ).

You can apply this to large decimal numbers. In this case, x is assumed to be a power of 10, and the coefficients must all be between 0 and x-1. For example, 1987 is 1x³ + 9x² + 8x + 7, when x = 10.
Procedure 14.6. Add Polynomials, p , q
1. Result Size. rSize ← the larger of len( p ) and len( q ).
2. Pad P? If len( p ) < rSize, create p1 from zeroes on the left + p .
  
  Else, p1 ← p .
3. Pad Q? If len( q ) < rSize, create q1 from zeroes on the left + q .
  
  Else, q1 ← q .
4. Add. Add matching elements from p1 and q1 to create result, r
5. Result. Return r as the sum of p and q .
Procedure 14.7. Multiply Polynomials, x , y
1. Result Size. rSize ← the sum of len( x ) + len( y ).
  
  Initialize the result array, r, to all zeroes, with a size of rSize.
2. For all elements of x. while 0 ≤ i < len( x ) loop
  1. For all elements of y. do while 0 ≤ j < len( y ) loop
    1. add x [i] * y [j] to r[i+j]
3. Result. Return r as the product of x and y .
Random Number Evaluation. Before using a new random number generator, it is wise to evaluate the degree of randomness in the numbers produced. A variety of clever algorithms look for certain types of expected distributions of numbers, pairs, triples, etc. This is one of many random number tests.

Use random.random to generate an array of random samples. These numbers will be uniform over the interval 0..1
Procedure 14.8. Distribution test of a sequence of random samples, u
1. Initialize
  
  Initialize count to a list of 10 zeroes.
2. Examine Samples. for each sample value, v in u
  1. Coerce Into Range. Multiply v by 10 and truncate to get a value x in 0..9 range
  2. Count. increment count[x]
3. Report. Display counts, % of total, deviation from expected count of 1/10th of available samples
Dutch National Flag. A challenging problem, one of the hardest in this set. This is from Edsger Dijkstra's book, A Discipline of Programming [Dijkstra76].

Imagine a board with a row of holes filled with red, white, and blue pegs. Develop an algorithm which will swap pegs to make three bands of red, white, and blue (like the Dutch flag). You must also satisfy this additional constraint: each peg must be examined exactly once.

Without the additional constraint, this is a relatively simple sorting problem. The additional constraint requires that instead of a simple sort which passes over the data several times, we need a more clever sort.

Hint: You will need four partitions in the array. Initially, every peg is in the “Unknown” partition. The other three partitions (“Red”, “White” and “Blue”) are empty. As the algorithm proceeds, pegs are swapped into the Red, White or Blue partition from the Unknown partition. When you are done, the unknown partition is reduced to zero elements, and the other three partitions have known numbers of elements.


List Methods		Chapter 15. Mappings and Dictionaries