Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

  




 

 

List Exercises

  1. 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 ilen( 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 .

  2. 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.

      hlen( seq ).

      m←(l+h)÷2.

    2. Loop. While l+1<h and seq [m] ≠ tgt

      1. If tgt < seq [m], then hm

      2. If tgt > seq [m], then lm

      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”.

  3. 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.

      lslo

      hshi

      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 )

  4. 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 )

  5. 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

        kp + p

        while k < 5000

        1. prime[k] ← false

        2. kk + p

      3. Next pincrement 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

  6. 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: 4x3 + 3x + 1 has the following coefficients: ( 4, 0, 3, 1 ).

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

    The sum is 4x3 + 2x2 - 3, ( 4, 2, 0, -3 ).

    The product is 8x5 - 12x4 - 10x3 - 7x2 - 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 1x3 + 9x2 + 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 .

  7. 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

  8. 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.


 
 
  Published under the terms of the Open Publication License Design by Interspire