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

How To Guides
Virtualization
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 `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` .

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.

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

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.

`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 )

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

`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. if`prime`[ `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