text:
Prefix Sums and Their Applications
- Willa McCoy
- 2 years ago
- Views:
1 1 Prefix Sums and Their Applications Guy E. Blelloch School of Computer Science Carnegie Mellon University Pittsburgh, PA
2 36 Chapter 1. Prefix Sums and Their Applications 1.1 Introduction Experienced algorithm designers rely heavily on a set of building blocks and on the tools needed to put the blocks together into an algorithm. The understanding of these basic blocks and tools is therefore critical to the understanding of algorithms. Many of the blocks and tools needed for parallel algorithms extend from sequential algorithms, such as dynamic-programming and divide-and-conquer, but others are new. This chapter introduces one of the simplest and most useful building blocks for parallel algorithms: the all-prefix-sums operation. The chapter defines the operation, shows how to implement it on a PRAM and illustrates many applications of the operation. In addition to being a useful building block, the all-prefix-sums operation is a good example of a computation that seems inherently sequential, but for which there is an efficient parallel algorithm. The operation is defined as follows: DEFINITION The all-prefix-sums operation takes a binary associative operator, and an ordered set of n elements and returns the ordered set [a 0, a 1,..., a n 1 ], [a 0, (a 0 a 1 ),..., (a 0 a 1... a n 1 )]. For example, if is addition, then the all-prefix-sums operation on the ordered set would return [ ], [ ]. The uses of the all-prefix-sums operation are extensive. Here is a list of some of them: 1. To lexically compare strings of characters. For example, to determine that "strategy" should appear before "stratification" in a dictionary (see Problem 2).
3 1.1 Introduction To add multi precision numbers. These are numbers that cannot be represented in a single machine word (see Problem 3). 3. To evaluate polynomials (see Problem 6). 4. To solve recurrences. For example, to solve the recurrences x i = a i x i 1 + b i x i 2 and x i = a i + b i /x i 1 (see Section 1.4). 5. To implement radix sort (see Section 1.3). 6. To implement quicksort (see Section 1). 7. To solve tridiagonal linear systems (see Problem 12). 8. To delete marked elements from an array (see Section 1.3). 9. To dynamically allocate processors (see Section 1.6). 10. To perform lexical analysis. For example, to parse a program into tokens. 11. To search for regular expressions. For example, to implement the UNIX grep program. 12. To implement some tree operations. For example, to find the depth of every vertex in a tree (see Chapter 3). 13. To label components in two dimensional images. In fact, all-prefix-sums operations using addition, minimum and maximum are so useful in practice that they have been included as primitive instructions in some machines. Researchers have also suggested that a subclass of the all-prefix-sums operation be added to the PRAM model as a unit time primitive because of their efficient hardware implementation. Before describing the implementation we must consider how the definition of the all-prefix-sums operation relates to the PRAM model. The definition states that the operation takes an ordered set, but does not specify how the ordered set is laid out in memory. One way to lay out the elements is in contiguous locations of a vector (a one dimensional array). Another way is to use a linked-list with pointers from each element to the next. It turns out that both forms of the operation have uses. In the examples listed above, the component labeling and some of the tree operations require the linked-list version, while the other examples can use the vector version. Sequentially, both versions are easy to compute (see Figure 1.1). The vector version steps down the vector, adding each element into a sum and writing the sum back, while the linked-list version follows the pointers while keeping the running sum and writing it back. The algorithms in Figure 1.1 for both versions are inherently sequential: to calculate a value at any step, the result of the previous step is needed. The algorithms therefore require O(n) time. To execute the all-prefix-sums operation in parallel, the algorithms must
4 38 Chapter 1. Prefix Sums and Their Applications proc all-prefix-sums(out, In) i 0 sum In[0] Out[0] sum while (i < length) i i + 1 sum sum + In[i] Out[i] sum Vector Version proc all-prefix-sums(out, In) i 0 sum In[0].value Out[0] sum while (In[i].pointer EOL) i In[i].pointer sum sum + In[i].value Out[i] sum List Version FIGURE 1.1 Sequential algorithms for calculating the all-prefix-sums operation with operator + on a vector and on a linked-list. In the list version, each element of In consists of two fields: a value (.value), and a pointer to the next position in the list (.pointer). EOL means the end-of-list pointer. be changed significantly. The remainder of this chapter is concerned with the vector all-prefixsums operation. We will henceforth use the term scan for this operation. 1 DEFINITION The scan operation is a vector all-prefix-sums operation. Chapters 2, 3 and 4 discuss uses of the linked-list all-prefix-sums operation and derive an optimal deterministic algorithm for the problem on the PRAM. Sometimes it is useful for each element of the result vector to contain the sum of all the previous elements, but not the element itself. We call such an operation, a prescan. DEFINITION The prescan operation takes a binary associative operator with identity I, and a vector of n elements [a 0, a 1,..., a n 1 ], 1 The term scan comes from the computer language APL.
5 1.2 Implementation 39 and returns the vector [I, a 0, (a 0 a 1 ),..., (a 0 a 1... a n 2 )]. A prescan can be generated from a scan by shifting the vector right by one and inserting the identity. Similarly, the scan can be generated from the prescan by shifting left, and inserting at the end the sum of the last element of the prescan and the last element of the original vector. 1.2 Implementation This section describes an algorithm for calculating the scan operation in parallel. For p processors and a vector of length n on an EREW PRAM, the algorithm has a time complexity of O(n/p + lg p). The algorithm is simple and well suited for direct implementation in hardware. Chapter 4 shows how the time of the scan operation with certain operators can be reduced to O(n/p + lg p/ lglg p) on a CREW PRAM. Before describing the scan operation, we consider a simpler problem, that of generating only the final element of the scan. We call this the reduce operation. DEFINITION The reduce operation takes a binary associative operator with identity i, and an ordered set [a 0, a 1,..., a n 1 ] of n elements, and returns the value a 0 a 1... a n 1. Again we consider only the case where the ordered set is kept in a vector. A balanced binary tree can be used to implement the reduce operation by laying the tree over the values, and using to sum pairs at each vertex (see Figure 1.2a). The correctness of the result relies on being associative. The operator, however, does not need to be commutative since the order of the operands is maintained. On an EREW PRAM, each level of the tree can be executed in parallel, so the implementation can step from the leaves to the root of the tree (see Figure 1.2b); we call this an up-sweep. Since the tree is of depth lg n, and one processor is needed for every pair of elements, the algorithm requires O(lg n) time and n/2 processors. If we assume a fixed number of processors p, with n > p, then each processor can sum an n/p section of the vector to generate a processor sum; the
6 40 Chapter 1. Prefix Sums and Their Applications (a) Executing a +-reduce on a tree. Step for d from 0 to (lg n) 1 in parallel for i from 0 to n 1 by 2 d+1 a[i + 2 d+1 1] a[i + 2 d 1] + a[i + 2 d+1 1] Vector in Memory 0 [ ] 1 [ ] 2 [ ] 3 [ ] (b) Executing a +-reduce on a PRAM. FIGURE 1.2 An example of the reduce operation when is integer addition. The boxes in (b) show the locations that are modified on each step. The length of the vector is n and must be a power of two. The final result will reside in a[n 1]. tree technique can then be used to reduce the processor sums (see Figure 1.3). The time taken to generate the processor sums is n/p, so the total time required on an EREW PRAM is: T R (n, p) = n/p + lg p = O(n/p + lg p). (1.1) When n/p lg p the complexity is O(n/p). This time is an optimal speedup over the sequential algorithm given in Figure 1.1. We now return to the scan operation. We actually show how to imple-
7 1.2 Implementation 41 in parallel for each processor i sum[i] a[(n/p)i] for j from 1 to n/p sum[i] sum[i] + a[(n/p)i + j] result +-reduce(sum) [ } {{ } processor } {{ } processor } {{ } processor 2 1 } {{ 9 5 } ] processor 3 Processor Sums = [ ] Total Sum = 52 FIGURE 1.3 The +-reduce operation with more elements than processors. We assume that n/p is an integer. ment the prescan operation; the scan is then determined by shifting the result and putting the sum at the end. If we look at the tree generated by the reduce operation, it contains many partial sums over regions of the vector. It turns out that these partial sums can be used to generate all the prefix sums. This requires executing another sweep of the tree with one step per level, but this time starting at the root and going to the leaves (a down-sweep). Initially, the identity element is inserted at the root of the tree. On each step, each vertex at the current level passes to its left child its own value, and it passes to its right child, applied to the value from the left child from the up-sweep and its own value (see Figure 1.4a). Let us consider why the down-sweep works. We say that vertex x precedes vertex y if x appears before y in the preorder traversal of the tree (depth first, from left to right). THEOREM 1.1 After a complete down-sweep, each vertex of the tree contains the sum of all the leaf values that precede it. PROOF The proof is inductive from the root: we show that if a parent has the correct sum, both children must have the correct sum. The root has no elements preceding it, so its value is correctly the identity element.
8 42 Chapter 1. Prefix Sums and Their Applications (a) Executing a +-prescan on a tree. procedure down-sweep(a) a[n 1] 0 % Set the identity for d from (lg n) 1 downto 0 in parallel for i from 0 to n 1 by 2 d+1 t a[i + 2 d 1] % Save in temporary a[i + 2 d 1] a[i + 2 d+1 1] % Set left child a[i + 2 d+1 1] t + a[i + 2 d+1 1] % Set right child Step Vector in Memory 0 [ ] up 1 [ ] 2 [ ] 3 [ ] clear 4 [ ] down 5 [ ] 6 [ ] 7 [ ] (b) Executing a +-prescan on a PRAM. FIGURE 1.4 A parallel prescan on a tree using integer addition as the associative operator, and 0 as the identity.
9 1.2 Implementation 43 FIGURE 1.5 Illustration for Theorem 1.1. Consider Figure 1.5. The left child of any vertex has exactly the same leaves preceding it as the vertex itself (the leaves in region A in the figure). This is because the preorder traversal always visits the left child of a vertex immediately after the vertex. By the induction hypothesis, the parent has the correct sum, so it need only copy this sum to the left child. The right child of any vertex has two sets of leaves preceding it, the leaves preceding the parent (region A), and the leaves at or below the left child (region B). Therefore, by adding the parent s down-sweep value, which is correct by the induction hypothesis, and the left-child s up-sweep value, the right-child will contain the sum of all the leaves preceding it. Since the leaf values that precede any leaf are the values to the left of it in the scan order, the values at the leaves are the results of a left-to-right prescan. To implement the prescan on an EREW PRAM, the partial sums at each vertex must be kept during the up-sweep so they can be used during the down-sweep. We must therefore be careful not to overwrite them. In fact, this was the motivation for putting the sums on the right during the reduce in Figure 1.2b. Figure 1.4b shows the PRAM code for the down-sweep. Each step can execute in parallel, so the running time is 2 lg n. If we assume a fixed number of processors p, with n > p, we can use a similar method to that in the reduce operation to generate an optimal
10 44 Chapter 1. Prefix Sums and Their Applications [ } {{ } processor } {{ } processor } {{ } processor 2 1 } {{ 9 5 } ] processor 3 Sum = [ ] +-prescan = [ ] [ } {{ } processor } {{ } processor } {{ } processor 2 37 } 38 {{ 47 } ] processor 3 FIGURE 1.6 A +-prescan with more elements than processors. algorithm. Each processor first sums an n/p section of the vector to generate a processor sum, the tree technique is then used to prescan the processor sums. The results of the prescan of the processor sums are used as an offset for each processor to prescan within its n/p section (see Figure 1.6). The time complexity of the algorithm is: T S (n, p) = 2( n/p + lg p ) = O(n/p + lg n) (1.2) which is the same order as the reduce operation and is also an optimal speedup over the sequential version when n/p lg p. This section described how to implement the scan (prescan) operation. The rest of the chapter discusses its applications. 1.3 Line-of-Sight and Radix-Sort As an example of the use of a scan operation, consider a simple line-ofsight problem. The line-of-sight problem is: given a terrain map in the form of a grid of altitudes and an observation point X on the grid, find which points are visible along a ray originating at the observation point (see Figure 1.7). A point on a ray is visible if and only if no other point between it and the observation point has a greater vertical angle. To find if any previous point has a greater angle, the altitude of each point along the ray is placed in a vector (the altitude vector). These altitudes are then converted to angles and placed
11 1.3 Line-of-Sight and Radix-Sort 45 procedure line-of-sight(altitude) in parallel for each index i angle[i] arctan(scale (altitude[i] - altitude[0])/ i) max-previous-angle max-prescan(angle) in parallel for each index i if (angle[i] > max-previous-angle[i]) result[i] "visible" else result[i] not "visible" FIGURE 1.7 The line-of-sight algorithm for a single ray. The X marks the observation point. The visible points are shaded. A point on the ray is visible if no previous point has a greater angle. in the angle vector (see Figure 1.7). A prescan using the operator maximum (max-prescan) is then executed on the angle vector, which returns to each point the maximum previous angle. To test for visibility each point only needs to compare its angle to the result of the max-prescan. This can be generalized to finding all visible points on the grid. For n points on a ray, the complexity of the algorithm is the complexity of the scan, T S (n, p) = O(n/p + lg n) on an EREW PRAM. We now consider another example, a radix sort algorithm. The algorithm loops over the bits of the keys, starting at the lowest bit, executing a split
12 46 Chapter 1. Prefix Sums and Their Applications procedure split-radix-sort(a, number-of-bits) for i from 0 to (number-of-bits 1) A split(a, A i ) A = [ ] A 0 = [ ] A split(a, A 0 ) = [ ] A 1 = [ ] A split(a, A 1 ) = [ ] A 2 = [ ] A split(a, A 2 ) = [ ] FIGURE 1.8 An example of the split radix sort on a vector containing three bit values. The A n notation signifies extracting the n th bit of each element of the vector A. The split operation packs elements with a 0 flag to the bottom and with a 1 flag to the top. operation on each iteration (assume all keys have the same number of bits). The split operation packs the keys with a 0 in the corresponding bit to the bottom of a vector, and packs the keys with a 1 in the bit to the top of the same vector. It maintains the order within both groups. The sort works because each split operation sorts the keys with respect to the current bit (0 down, 1 up) and maintains the sorted order of all the lower bits since we iterate from the bottom bit up. Figure 1.8 shows an example of the sort. We now consider how the split operation can be implemented using a scan. The basic idea is to determine a new index for each element and then permute the elements to these new indices using an exclusive write. To determine the new indices for elements with a 0 in the bit, we invert the flags and execute a prescan with integer addition. To determine the new indices of elements with a 1 in the bit, we execute a +-scan in reverse order (starting at the top of the vector) and subtract the results from the length of the vector n. Figure 1.9 shows an example of the split operation along with code to implement it. Since the split operation just requires two scan operations, a few steps of exclusive memory accesses, and a few parallel arithmetic operations, it has the same asymptotic complexity as the scan: O(n/p + lg p) on an EREW
13 1.4 Recurrence Equations 47 procedure split(a, Flags) I-down +-prescan(not(flags)) I-up n - +-scan(reverse-order(flags)) in parallel for each index i if (Flags[i]) Index[i] I-up[i] else Index[i] I-down[i] result permute(a, Index) A = [ ] Flags = [ ] I-down = [ ] I-up = [ ] Index = [ ] permute(a, Index) = [ ] FIGURE 1.9 The split operation packs the elements with a 0 in the corresponding flag position to the bottom of a vector, and packs the elements with a 1 to the top of the same vector. The permute writes each element of A to the index specified by the corresponding position in Index. PRAM. 2 If we assume that n keys are each O(lg n) bits long, then the overall algorithm runs in time: O(( n p + lg p)lg n) = O(n lg n + lg n lg p). p 1.4 Recurrence Equations This section shows how various recurrence equations can be solved using the scan operation. A recurrence is a set of equations of the form x i = f i (x i 1, x i 2,,x i m ), m i < n (1.3) 2 On an CREW PRAM we can use the scan described in Chapter 4 to get a time of O(n/p+ lg p/lglg p).
14 48 Chapter 1. Prefix Sums and Their Applications along with a set of initial values x 0,,x m 1. The scan operation is the special case of a recurrence of the form x i = { a0 i = 0 x i 1 a i 0 < i < n, (1.4) where is any binary associative operator. This section shows how to reduce a more general class of recurrences to equation (1.4), and therefore how to use the scan algorithm discussed in Section 1.2 to solve these recurrences in parallel First-Order Recurrences We initially consider first-order recurrences of the following form x i = { b0 i = 0 (x i 1 a i ) b i 0 < i < n, (1.5) where the a i s and b i s are sets of n arbitrary constants (not necessarily scalars) and and are arbitrary binary operators that satisfy three restrictions: 1. is associative (i.e. (a b) c = a (b c)). 2. is semiassociative (i.e. there exists a binary associative operator such that (a b) c = a (b c)). 3. distributes over (i.e. a (b c) = (a b) (a c)). The operator is called the companion operator of. If is fully associative, then and are equivalent. We now show how (1.5) can be reduced to (1.4). Consider the set of pairs c i = [a i, b i ] (1.6) and define a new binary operator as follows: c i c j [c i,a c j,a, (c i,b c j,a ) c j,b ] (1.7) where c i,a and c i,b are the first and second elements of c i, respectively. Given the conditions on the operators and, the operator is associative as we show below: (c i c j ) c k = [c i,a c j,a, (c i,b c j,a ) c j,b ] c k = [(c i,a c j,a ) c k,a, (((c i,b c j,a ) c j,b ) c k,a ) c k,b ]
15 1.4 Recurrence Equations 49 = [c i,a (c j,a c k,a ), ((c i,b c j,a ) c k,a ) ((c j,b c k,a ) c k,b )] = [c i,a (c j,a c k,a ), (c i,b (c j,a c k,a )) ((c j,b c k,a ) c k,b )] = c i [c j,a c k,a, (c j,b c k,a ) c k,b ] = c i (c j c k ) We now define the ordered set s i = [y i, x i ], where the y i obey the recurrence y i = { a0 i = 0 y i 1 a i 0 < i < n, (1.8) and the x i are from (1.5). Using (1.5), (1.6) and (1.8) we obtain: s 0 = [y 0, x 0 ] = [a 0, b 0 ] = c 0 s i = [y i, x i ] 0 < i < n = [y i 1 a i, (x i 1 a i ) b i ] = [y i 1 c i,a, (x i 1 c i,a ) c i,b ] = [y i 1, x i 1 ] c i = s i 1 c i. Since is associative, we have reduced (1.5) to (1.4). The results x i are just the second values of s i (the s i,b ). This allows us to use the scan algorithm of Section 1.2 with operator to solve any recurrence of the form (1.5) on an EREW PRAM in time: (T + T + T )T S (n, p) = 2(T + T + T )(n/p + lg p) (1.9) where T, T and T are the times taken by, and ( makes one call to each). If all that is needed is the final value x n 1, then we can use a reduce instead of scan with the operator, and the running time is: (T + T + T )T R (n, p) = (T + T + T )(n/p + lg p) (1.10) which is asymptotically a factor of 2 faster than (1.9). Applications of first-order linear recurrences include the simulation of various time-varying linear systems, the backsubstitution phase of tridiagonal linear-systems solvers, and the evaluation of polynomials.
16 50 Chapter 1. Prefix Sums and Their Applications Higher Order Recurrences We now consider the more general order m recurrences of the form: x i = { bi 0 i < m (x i 1 a i,1 ) (x i m a i,m ) b i m i < n (1.11) where and are binary operators with the same three restrictions as in (1.5): is associative, is semiassociative, and distributes over. To convert this equation into the form (1.5), we define the following vector of variables: s i = [ x i x i m+1 ]. (1.12) Using (1.11) we can write (1.12) as: a i, s i = [ x i 1 x i m ] (v) (v) [ b i 0 0 ] a i,m = (s i 1 (v) A i ) (v) B i (1.13) where (v) is vector-matrix multiply and (v) is vector addition. If we use matrix-matrix multiply as the companion operator of (v), then (1.13) is in the form (1.5). The time taken for solving equations of the form (1.11) on an EREW PRAM is therefore: (T m m (m)+t v m (m)+t v v (m))t S (n, p) = O((n/p+lg p)t m m (m)) (1.14) where T m m (m) is the time taken by an m m matrix multiply. The sequential complexity for solving the equations is O(nm), so the parallel complexity is optimal in n when n/p lg p, but is not optimal in m the parallel algorithm performs a factor of O(T M M (m)/m) more work than the sequential algorithm. Applications of the recurrence (1.11) include solving recurrences of the form x i = a i + b i /x i 1 (see problem 10), and generating the first n Fibonacci numbers x 0 = x 1 = 1, x i = x i 1 + x i 2 (see problem 11).
17 1.5 Segmented Scans 51 a = [ ] f = [ ] segmented +-scan = [ ] segmented max-scan = [ ] FIGURE 1.10 The segmented scan operations restart at the beginning of each segment. The vector f contains flags that mark the beginning of the segments. 1.5 Segmented Scans This section shows how the vector operated on by a scan can be broken into segments with flags so that the scan starts again at each segment boundary (see Figure 1.10). Each of these scans takes two vectors of values: a data vector and a flag vector. The segmented scan operations present a convenient way to execute a scan independently over many sets of values. The next section shows how the segmented scans can be used to execute a parallel quicksort, by keeping each recursive call in a separate segment, and using a segmented +-scan to execute a split within each segment. The segmented scans satisfy the recurrence: x i = a 0 i = 0 { ai f i = 1 (x i 1 a i ) f i = 0 0 < i < n (1.15) where is the original associative scan operator. If has an identity I, then (1.15) can be written as: x i = where s is defined as: { a0 i = 0 (x i 1 s f i ) a i 0 < i < n (1.16) x s f = { I f = 1 x f = 0. (1.17) This is in the form (1.5) and s is semiassociative with logical or as the companion operator (see Problem 9). Since we have reduced (1.15) to the
18 52 Chapter 1. Prefix Sums and Their Applications form (1.5), we can use the technique described in Section 1 to execute the segmented scans in time (T or + T s + T )T S (n, p). (1.18) This time complexity is only a small constant factor greater than the unsegmented version since or and s are trivial operators Example: Quicksort To illustrate the use of segmented scans, we consider a parallel version of quicksort. Similar to the standard sequential version, the parallel version picks one of the keys as a pivot value, splits the keys into three sets keys lesser, equal and greater than the pivot and recurses on each set. 3 The parallel algorithm has an expected time complexity of O(T S (n, p) lg n) = O( n p lg n + lg2 n). The basic intuition of the parallel version is to keep each subset in its own segment, and to pick pivot values and split the keys independently within each segment. Figure 1.11 shows pseudocode for the parallel quicksort and gives an example. The steps of the sort are outlined as follows: 1. Check if the keys are sorted and exit the routine if they are. Each processor checks to see if the previous processor has a lesser or equal value. We execute a reduce with logical and to check if all the elements are in order. 2. Within each segment, pick a pivot and distribute it to the other elements. If we pick the first element as a pivot, we can use a segmented scan with the binary operator copy, which returns the first of its two arguments: a copy(a, b). This has the effect of copying the first element of each segment across the segment. The algorithm could also pick a random element within each segment (see Problem 15). 3. Within each segment, compare each element with the pivot and split based on the result of the comparison. For the split, we can use a version of the split operation described in Section 1.3 which splits into three sets instead of two, and which is 3 We do not need to recursively sort the keys equal to the pivot, but the algorithm as described below does.
19 1.5 Segmented Scans 53 procedure quicksort(keys) seg-flags[0] 1 while not-sorted(keys) pivots seg-copy(keys, seg-flags) f pivots <=> keys keys seg-split(keys, f, seg-flags) seg-flags new-seg-flags(keys, pivots, seg-flags) Key = [ ] Seg-Flags = [ ] Pivots = [ ] F = [= > < < > < > <] Key split(key, F) = [ ] Seg-Flags = [ ] Pivots = [ ] F = [= < > = = = < =] Key split(key, F) = [ ] Seg-Flags = [ ] FIGURE 1.11 An example of parallel quicksort. On each step, within each segment, we distribute the pivot, test whether each element is equal-to, less-than or greaterthan the pivot, split into three groups, and generate a new set of segment flags. The operation <=> returns one of three values depending on whether the first argument is less than, equal to or greater than the second. segmented. To implement such a segmented split, we can use a segmented version of the +-scan operation to generate indices relative to the beginning of each segment, and we can use a segmented copyscan to copy the offset of the beginning of each segment across the segment. We then add the offset to the segment indices to generate the location to which we permute each element. 4. Within each segment, insert additional segment flags to separate the split values. Knowing the pivot value, each element can determine if it is at the beginning of the segment by looking at the previous element. 5. Return to step 1.
20 54 Chapter 1. Prefix Sums and Their Applications Each iteration of this sort requires a constant number of calls to the scans and to the primitives of the PRAM. If we select pivots randomly within each segment, quicksort is expected to complete in O(lg n) iterations, and therefore has an expected running time of O(lg n T S (n, p)). The technique of recursively breaking segments into subsegments and operating independently within each segment can be used for many other divide-and-conquer algorithms, such as mergesort. 1.6 Allocating Processors Consider the following problem: given a set of processors, each containing an integer, allocate that integer number of new processors to each initial processor. Such allocation is necessary in the parallel line-drawing routine described in Section 1. In this line-drawing routine, each processor calculates the number of pixels in the line and dynamically allocates a processor for each pixel. Allocating new elements is also useful for the branching part of many branch-and-bound algorithms. Consider, for example, a brute force chess-playing algorithm that executes a fixed-depth search of possible moves to determine the best next move. We can test or search the moves in parallel by placing each possible move in a separate processor. Since the algorithm dynamically decides how many next moves to generate (depending on the position), we need to dynamically allocate new processing elements. More formally, given a length l vector A with integer elements a i, allocation is the task of creating a new vector B of length l 1 L = a i (1.19) i=0 with a i elements of B assigned to each position i of A. By assigned to, we mean that there must be some method for distributing a value at position i of a vector to the a i elements which are assigned to that position. Since there is a one-to-one correspondence between elements of a vector and processors, the original vector requires l processors and the new vector requires L processors. Typically, an algorithm does not operate on the two vectors at the same time, so that we can use the same processors for both. Allocation can be implemented by assigning a contiguous segment of elements to each position i of A. To allocate segments we execute a +-prescan
Parallel Prefix Sum (Scan) with CUDA. Mark Harris email@example.com
Parallel Prefix Sum (Scan) with CUDA Mark Harris email@example.com April 2007 Document Change History Version Date Responsible Reason for Change February 14, 2007 Mark Harris Initial release April 2007More information
Parallel Random Access Machine (PRAM) PRAM Algorithms. Shared Memory Access Conflicts. A Basic PRAM Algorithm. Time Optimality.
Parallel Random Access Machine (PRAM) PRAM Algorithms Arvind Krishnamurthy Fall 2 Collection of numbered processors Accessing shared memory cells Each processor could have local memory (registers) EachMore information
Why? A central concept in Computer Science. Algorithms are ubiquitous.
Analysis of Algorithms: A Brief Introduction Why? A central concept in Computer Science. Algorithms are ubiquitous. Using the Internet (sending email, transferring files, use of search engines, onlineMore information
Many algorithms, particularly divide and conquer algorithms, have time complexities which are naturally
Recurrence Relations Many algorithms, particularly divide and conquer algorithms, have time complexities which are naturally modeled by recurrence relations. A recurrence relation is an equation whichMore information
Cost Model: Work, Span and Parallelism. 1 The RAM model for sequential computation:
CSE341T 08/31/2015 Lecture 3 Cost Model: Work, Span and Parallelism In this lecture, we will look at how one analyze a parallel program written using Cilk Plus. When we analyze the cost of an algorithmMore information
Binary Search Trees. A Generic Tree. Binary Trees. Nodes in a binary search tree ( B-S-T) are of the form. P parent. Key. Satellite data L R
Binary Search Trees A Generic Tree Nodes in a binary search tree ( B-S-T) are of the form P parent Key A Satellite data L R B C D E F G H I J The B-S-T has a root node which is the only node whose parentMore information
The PRAM Model and Algorithms. Advanced Topics Spring 2008 Prof. Robert van Engelen
The PRAM Model and Algorithms Advanced Topics Spring 2008 Prof. Robert van Engelen Overview The PRAM model of parallel computation Simulations between PRAM models Work-time presentation framework of parallelMore information
Catalan Numbers. Thomas A. Dowling, Department of Mathematics, Ohio State Uni- versity.
7 Catalan Numbers Thomas A. Dowling, Department of Mathematics, Ohio State Uni- Author: versity. Prerequisites: The prerequisites for this chapter are recursive definitions, basic counting principles,More information
ML for the Working Programmer
ML for the Working Programmer 2nd edition Lawrence C. Paulson University of Cambridge CAMBRIDGE UNIVERSITY PRESS CONTENTS Preface to the Second Edition Preface xiii xv 1 Standard ML 1 Functional ProgrammingMore information
Divide And Conquer Algorithms
CSE341T/CSE549T 09/10/2014 Lecture 5 Divide And Conquer Algorithms Recall in last lecture, we looked at one way of parallelizing matrix multiplication. At the end of the lecture, we saw the reduce SUMMore information
Introduction to Algorithms March 10, 2004 Massachusetts Institute of Technology Professors Erik Demaine and Shafi Goldwasser Quiz 1.
Introduction to Algorithms March 10, 2004 Massachusetts Institute of Technology 6.046J/18.410J Professors Erik Demaine and Shafi Goldwasser Quiz 1 Quiz 1 Do not open this quiz booklet until you are directedMore information
Volume 2, No. 3, March 2011 Journal of Global Research in Computer Science RESEARCH PAPER Available Online at www.jgrcs.info IMPROVING PERFORMANCE OF RANDOMIZED SIGNATURE SORT USING HASHING AND BITWISEMore information
Intro. to the Divide-and-Conquer Strategy via Merge Sort CMPSC 465 CLRS Sections 2.3, Intro. to and various parts of Chapter 4
Intro. to the Divide-and-Conquer Strategy via Merge Sort CMPSC 465 CLRS Sections 2.3, Intro. to and various parts of Chapter 4 I. Algorithm Design and Divide-and-Conquer There are various strategies weMore information
MapReduce and Distributed Data Analysis. Sergei Vassilvitskii Google Research
MapReduce and Distributed Data Analysis Google Research 1 Dealing With Massive Data 2 2 Dealing With Massive Data Polynomial Memory Sublinear RAM Sketches External Memory Property Testing 3 3 Dealing WithMore information
Lecture 15 An Arithmetic Circuit Lowerbound and Flows in Graphs
CSE599s: Extremal Combinatorics November 21, 2011 Lecture 15 An Arithmetic Circuit Lowerbound and Flows in Graphs Lecturer: Anup Rao 1 An Arithmetic Circuit Lower Bound An arithmetic circuit is just likeMore information
Algorithms and Data Structures
Algorithm Analysis Page 1 BFH-TI: Softwareschule Schweiz Algorithm Analysis Dr. CAS SD01 Algorithm Analysis Page 2 Outline Course and Textbook Overview Analysis of Algorithm Pseudo-Code and Primitive OperationsMore information
2.1 Complexity Classes
15-859(M): Randomized Algorithms Lecturer: Shuchi Chawla Topic: Complexity classes, Identity checking Date: September 15, 2004 Scribe: Andrew Gilpin 2.1 Complexity Classes In this lecture we will lookMore information
Fast Sequential Summation Algorithms Using Augmented Data Structures
Fast Sequential Summation Algorithms Using Augmented Data Structures Vadim Stadnik firstname.lastname@example.com Abstract This paper provides an introduction to the design of augmented data structures that offerMore information
Approximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NP-Completeness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithmsMore information
CS473 - Algorithms I
CS473 - Algorithms I Lecture 9 Sorting in Linear Time View in slide-show mode 1 How Fast Can We Sort? The algorithms we have seen so far: Based on comparison of elements We only care about the relativeMore information
CSE373: Data Structures and Algorithms Lecture 3: Math Review; Algorithm Analysis. Linda Shapiro Winter 2015
CSE373: Data Structures and Algorithms Lecture 3: Math Review; Algorithm Analysis Linda Shapiro Today Registration should be done. Homework 1 due 11:59 pm next Wednesday, January 14 Review math essentialMore information
Converting a Number from Decimal to Binary
Converting a Number from Decimal to Binary Convert nonnegative integer in decimal format (base 10) into equivalent binary number (base 2) Rightmost bit of x Remainder of x after division by two RecursiveMore information
Homework 5 Solutions
Homework 5 Solutions 4.2: 2: a. 321 = 256 + 64 + 1 = (01000001) 2 b. 1023 = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = (1111111111) 2. Note that this is 1 less than the next power of 2, 1024, whichMore information
CS473 - Algorithms I
CS473 - Algorithms I Lecture 4 The Divide-and-Conquer Design Paradigm View in slide-show mode 1 Reminder: Merge Sort Input array A sort this half sort this half Divide Conquer merge two sorted halves CombineMore information
An Eective Load Balancing Policy for
An Eective Load Balancing Policy for Geometric Decaying Algorithms Joseph Gil y Dept. of Computer Science The Technion, Israel Technion City, Haifa 32000 ISRAEL Yossi Matias z AT&T Bell Laboratories 600More information
Analysis of Algorithms I: Binary Search Trees
Analysis of Algorithms I: Binary Search Trees Xi Chen Columbia University Hash table: A data structure that maintains a subset of keys from a universe set U = {0, 1,..., p 1} and supports all three dictionaryMore information
Mathematics of Cryptography
CHAPTER 2 Mathematics of Cryptography Part I: Modular Arithmetic, Congruence, and Matrices Objectives This chapter is intended to prepare the reader for the next few chapters in cryptography. The chapterMore information
Bounded Cost Algorithms for Multivalued Consensus Using Binary Consensus Instances
Bounded Cost Algorithms for Multivalued Consensus Using Binary Consensus Instances Jialin Zhang Tsinghua University firstname.lastname@example.com Wei Chen Microsoft Research Asia firstname.lastname@example.com AbstractMore information
Rethinking SIMD Vectorization for In-Memory Databases
SIGMOD 215, Melbourne, Victoria, Australia Rethinking SIMD Vectorization for In-Memory Databases Orestis Polychroniou Columbia University Arun Raghavan Oracle Labs Kenneth A. Ross Columbia University LatestMore information
CMPS 102 Solutions to Homework 1
CMPS 0 Solutions to Homework Lindsay Brown, email@example.com September 9, 005 Problem..- p. 3 For inputs of size n insertion sort runs in 8n steps, while merge sort runs in 64n lg n steps. For whichMore information
Binary search tree with SIMD bandwidth optimization using SSE
Binary search tree with SIMD bandwidth optimization using SSE Bowen Zhang, Xinwei Li 1.ABSTRACT In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendousMore information
A Note on Maximum Independent Sets in Rectangle Intersection Graphs
A Note on Maximum Independent Sets in Rectangle Intersection Graphs Timothy M. Chan School of Computer Science University of Waterloo Waterloo, Ontario N2L 3G1, Canada firstname.lastname@example.com September 12,More information
Mathematics for Algorithm and System Analysis
Mathematics for Algorithm and System Analysis for students of computer and computational science Edward A. Bender S. Gill Williamson c Edward A. Bender & S. Gill Williamson 2005. All rights reserved. PrefaceMore information
12 Abstract Data Types
12 Abstract Data Types 12.1 Source: Foundations of Computer Science Cengage Learning Objectives After studying this chapter, the student should be able to: Define the concept of an abstract data type (ADT).More information
Scan Primitives for Vector Computers*
Scan Primitives for Vector Computers* Siddhartha Chatterjee Guy E. Blelloch School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213-3890 Marco Zagha Abstract Ibis paper describes anMore information
Mergesort and Quicksort
Mergesort Mergesort and Quicksort Basic plan: Divide array into two halves. Recursively sort each half. Merge two halves to make sorted whole. mergesort mergesort analysis quicksort quicksort analysisMore information
The Union-Find Problem Kruskal s algorithm for finding an MST presented us with a problem in data-structure design. As we looked at each edge,
The Union-Find Problem Kruskal s algorithm for finding an MST presented us with a problem in data-structure design. As we looked at each edge, cheapest first, we had to determine whether its two endpointsMore information
Lecture 3: Linear Programming Relaxations and Rounding
Lecture 3: Linear Programming Relaxations and Rounding 1 Approximation Algorithms and Linear Relaxations For the time being, suppose we have a minimization problem. Many times, the problem at hand canMore information
Fundamental Computer Science Concepts Sequence TCSU CSCI SEQ A
Fundamental Computer Science Concepts Sequence TCSU CSCI SEQ A A. Description Introduction to the discipline of computer science; covers the material traditionally found in courses that introduce problemMore information
The following themes form the major topics of this chapter: The terms and concepts related to trees (Section 5.2).
CHAPTER 5 The Tree Data Model There are many situations in which information has a hierarchical or nested structure like that found in family trees or organization charts. The abstraction that models hierarchicalMore information
The program also provides supplemental modules on topics in geometry and probability and statistics.
Algebra 1 Course Overview Students develop algebraic fluency by learning the skills needed to solve equations and perform important manipulations with numbers, variables, equations, and inequalities. StudentsMore information
Quicksort is a divide-and-conquer sorting algorithm in which division is dynamically carried out (as opposed to static division in Mergesort).
Chapter 7: Quicksort Quicksort is a divide-and-conquer sorting algorithm in which division is dynamically carried out (as opposed to static division in Mergesort). The three steps of Quicksort are as follows:More information
Thnkwell s Homeschool Precalculus Course Lesson Plan: 36 weeks
Thnkwell s Homeschool Precalculus Course Lesson Plan: 36 weeks Welcome to Thinkwell s Homeschool Precalculus! We re thrilled that you ve decided to make us part of your homeschool curriculum. This lessonMore information
Merge Sort. 2004 Goodrich, Tamassia. Merge Sort 1
Merge Sort 7 2 9 4 2 4 7 9 7 2 2 7 9 4 4 9 7 7 2 2 9 9 4 4 Merge Sort 1 Divide-and-Conquer Divide-and conquer is a general algorithm design paradigm: Divide: divide the input data S in two disjoint subsetsMore information
Genetic Algorithms commonly used selection, replacement, and variation operators Fernando Lobo University of Algarve
Genetic Algorithms commonly used selection, replacement, and variation operators Fernando Lobo University of Algarve Outline Selection methods Replacement methods Variation operators Selection MethodsMore information
December 4, 2013 MATH 171 BASIC LINEAR ALGEBRA B. KITCHENS
December 4, 2013 MATH 171 BASIC LINEAR ALGEBRA B KITCHENS The equation 1 Lines in two-dimensional space (1) 2x y = 3 describes a line in two-dimensional space The coefficients of x and y in the equationMore information
Exam study sheet for CS2711. List of topics
Exam study sheet for CS2711 Here is the list of topics you need to know for the final exam. For each data structure listed below, make sure you can do the following: 1. Give an example of this data structureMore information
Sorting revisited. Build the binary search tree: O(n^2) Traverse the binary tree: O(n) Total: O(n^2) + O(n) = O(n^2)
Sorting revisited How did we use a binary search tree to sort an array of elements? Tree Sort Algorithm Given: An array of elements to sort 1. Build a binary search tree out of the elements 2. TraverseMore information
Symbol Tables. Introduction
Symbol Tables Introduction A compiler needs to collect and use information about the names appearing in the source program. This information is entered into a data structure called a symbol table. TheMore information
PARALLEL PROGRAMMING TECHNIQUES AND APPLICATIONS USING NETWORKED WORKSTATIONS AND PARALLEL COMPUTERS 2nd Edition BARRY WILKINSON University of North Carolina at Charlotte Western Carolina University MICHAELMore information
Mathematics of Cryptography Modular Arithmetic, Congruence, and Matrices. A Biswas, IT, BESU SHIBPUR
Mathematics of Cryptography Modular Arithmetic, Congruence, and Matrices A Biswas, IT, BESU SHIBPUR McGraw-Hill The McGraw-Hill Companies, Inc., 2000 Set of Integers The set of integers, denoted by Z,More information
Solution of Linear Systems
Chapter 3 Solution of Linear Systems In this chapter we study algorithms for possibly the most commonly occurring problem in scientific computing, the solution of linear systems of equations. We startMore information
Data Structure with C
Subject: Data Structure with C Topic : Tree Tree A tree is a set of nodes that either:is empty or has a designated node, called the root, from which hierarchically descend zero or more subtrees, whichMore information
1) The postfix expression for the infix expression A+B*(C+D)/F+D*E is ABCD+*F/DE*++
Answer the following 1) The postfix expression for the infix expression A+B*(C+D)/F+D*E is ABCD+*F/DE*++ 2) Which data structure is needed to convert infix notations to postfix notations? Stack 3) TheMore information
Vector storage and access; algorithms in GIS. This is lecture 6
Vector storage and access; algorithms in GIS This is lecture 6 Vector data storage and access Vectors are built from points, line and areas. (x,y) Surface: (x,y,z) Vector data access Access to vectorMore information
1/1 7/4 2/2 12/7 10/30 12/25
Binary Heaps A binary heap is dened to be a binary tree with a key in each node such that: 1. All leaves are on, at most, two adjacent levels. 2. All leaves on the lowest level occur to the left, and allMore information
Answer: (a) Since we cannot repeat men on the committee, and the order we select them in does not matter, ( )
1. (Chapter 1 supplementary, problem 7): There are 12 men at a dance. (a) In how many ways can eight of them be selected to form a cleanup crew? (b) How many ways are there to pair off eight women at theMore information
DATA STRUCTURES USING C QUESTION BANK UNIT I 1. Define data. 2. Define Entity. 3. Define information. 4. Define Array. 5. Define data structure. 6. Give any two applications of data structures. 7. GiveMore information
Parallelization: Binary Tree Traversal
By Aaron Weeden and Patrick Royal Shodor Education Foundation, Inc. August 2012 Introduction: According to Moore s law, the number of transistors on a computer chip doubles roughly every two years. FirstMore information
Dynamic Programming. Lecture 11. 11.1 Overview. 11.2 Introduction
Lecture 11 Dynamic Programming 11.1 Overview Dynamic Programming is a powerful technique that allows one to solve many different types of problems in time O(n 2 ) or O(n 3 ) for which a naive approachMore information
Image Compression through DCT and Huffman Coding Technique
International Journal of Current Engineering and Technology E-ISSN 2277 4106, P-ISSN 2347 5161 2015 INPRESSCO, All Rights Reserved Available at http://inpressco.com/category/ijcet Research Article RahulMore information
Indiana State Core Curriculum Standards updated 2009 Algebra I
Indiana State Core Curriculum Standards updated 2009 Algebra I Strand Description Boardworks High School Algebra presentations Operations With Real Numbers Linear Equations and A1.1 Students simplify andMore information
Linear Codes. Chapter 3. 3.1 Basics
Chapter 3 Linear Codes In order to define codes that we can encode and decode efficiently, we add more structure to the codespace. We shall be mainly interested in linear codes. A linear code of lengthMore information
An Efficient RNS to Binary Converter Using the Moduli Set {2n + 1, 2n, 2n 1}
An Efficient RNS to Binary Converter Using the oduli Set {n + 1, n, n 1} Kazeem Alagbe Gbolagade 1,, ember, IEEE and Sorin Dan Cotofana 1, Senior ember IEEE, 1. Computer Engineering Laboratory, Delft UniversityMore information
Reminder: Complexity (1) Parallel Complexity Theory. Reminder: Complexity (2) Complexity-new
Reminder: Complexity (1) Parallel Complexity Theory Lecture 6 Number of steps or memory units required to compute some result In terms of input size Using a single processor O(1) says that regardless ofMore information
Reminder: Complexity (1) Parallel Complexity Theory. Reminder: Complexity (2) Complexity-new GAP (2) Graph Accessibility Problem (GAP) (1)
Reminder: Complexity (1) Parallel Complexity Theory Lecture 6 Number of steps or memory units required to compute some result In terms of input size Using a single processor O(1) says that regardless ofMore information
Memory Systems. Static Random Access Memory (SRAM) Cell
Memory Systems This chapter begins the discussion of memory systems from the implementation of a single bit. The architecture of memory chips is then constructed using arrays of bit implementations coupledMore information
Fairness in Routing and Load Balancing
Fairness in Routing and Load Balancing Jon Kleinberg Yuval Rabani Éva Tardos Abstract We consider the issue of network routing subject to explicit fairness conditions. The optimization of fairness criteriaMore information
AP Computer Science AB Syllabus 1
AP Computer Science AB Syllabus 1 Course Resources Java Software Solutions for AP Computer Science, J. Lewis, W. Loftus, and C. Cocking, First Edition, 2004, Prentice Hall. Video: Sorting Out Sorting,More information
ACADEMIC YEAR: 0 7 VALLIAMMAI ENGINEERING COLLEGE SRM NAGAR, KATTANKULATHUR 0 0 SEMESTER: ODD BRANCH: MCA YEAR: I SEMESTER: I SUBJECT CODE AND NAME: MC70 Problem Solving and Programming NAME OF THE FACULTYMore information
Modern Optimization Methods for Big Data Problems MATH11146 The University of Edinburgh
Modern Optimization Methods for Big Data Problems MATH11146 The University of Edinburgh Peter Richtárik Week 3 Randomized Coordinate Descent With Arbitrary Sampling January 27, 2016 1 / 30 The ProblemMore information
2. (a) Explain the strassen s matrix multiplication. (b) Write deletion algorithm, of Binary search tree. [8+8]
Code No: R05220502 Set No. 1 1. (a) Describe the performance analysis in detail. (b) Show that f 1 (n)+f 2 (n) = 0(max(g 1 (n), g 2 (n)) where f 1 (n) = 0(g 1 (n)) and f 2 (n) = 0(g 2 (n)). [8+8] 2. (a)More information
Linear Programming Problems
Linear Programming Problems Linear programming problems come up in many applications. In a linear programming problem, we have a function, called the objective function, which depends linearly on a numberMore information
The Set Data Model CHAPTER 7. 7.1 What This Chapter Is About
CHAPTER 7 The Set Data Model The set is the most fundamental data model of mathematics. Every concept in mathematics, from trees to real numbers, is expressible as a special kind of set. In this book,More information
ENGINEERING PROBLEM SOLVING WITH C++ Third Edition Delores M. Etter Electrical Engineering Department Southern Methodist University, Dallas, TX Jeanine A. Ingber Accurate Solutions in Applied Physics,More information
CSC148 Lecture 8. Algorithm Analysis Binary Search Sorting
CSC148 Lecture 8 Algorithm Analysis Binary Search Sorting Algorithm Analysis Recall definition of Big Oh: We say a function f(n) is O(g(n)) if there exists positive constants c,b such that f(n)More information
MPI Hands-On List of the exercises
MPI Hands-On List of the exercises 1 MPI Hands-On Exercise 1: MPI Environment.... 2 2 MPI Hands-On Exercise 2: Ping-pong...3 3 MPI Hands-On Exercise 3: Collective communications and reductions... 5 4 MPIMore information
Some Polynomial Theorems. John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 firstname.lastname@example.com.
Some Polynomial Theorems by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 email@example.com This paper contains a collection of 31 theorems, lemmas,More information
Utah Core Curriculum for Mathematics
Core Curriculum for Mathematics correlated to correlated to 2005 Chapter 1 (pp. 2 57) Variables, Expressions, and Integers Lesson 1.1 (pp. 5 9) Expressions and Variables 2.2.1 Evaluate algebraic expressionsMore information
Parallel Algorithms. Introduction
Parallel Algorithms Guy E. Blelloch and Bruce M. Maggs School of Computer Science Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 email@example.com, email@example.com Introduction The subjectMore information
Cryptography and Network Security Department of Computer Science and Engineering Indian Institute of Technology Kharagpur
Cryptography and Network Security Department of Computer Science and Engineering Indian Institute of Technology Kharagpur Module No. # 01 Lecture No. # 05 Classic Cryptosystems (Refer Slide Time: 00:42)More information
CS 10: SOLUTIONS TO DIVIDE AND CONQUER ALGORITHMS (ASSGN 4) Problem 1. a. Consider the modified binary search algorithm so that it splits the input not into two sets of almost-equal sizes, but into threeMore information
Home Page. Data Structures. Title Page. Page 1 of 24. Go Back. Full Screen. Close. Quit
Data Structures Page 1 of 24 A.1. Arrays (Vectors) n-element vector start address + ielementsize 0 +1 +2 +3 +4... +n-1 start address continuous memory block static, if size is known at compile time dynamic,More information
RN-Codings: New Insights and Some Applications
RN-Codings: New Insights and Some Applications Abstract During any composite computation there is a constant need for rounding intermediate results before they can participate in further processing. RecentlyMore information
Integer Factorization using the Quadratic Sieve
Integer Factorization using the Quadratic Sieve Chad Seibert* Division of Science and Mathematics University of Minnesota, Morris Morris, MN 56567 firstname.lastname@example.com March 16, 2011 Abstract We giveMore information
Outline BST Operations Worst case Average case Balancing AVL Red-black B-trees. Binary Search Trees. Lecturer: Georgy Gimel farb
Binary Search Trees Lecturer: Georgy Gimel farb COMPSCI 220 Algorithms and Data Structures 1 / 27 1 Properties of Binary Search Trees 2 Basic BST operations The worst-case time complexity of BST operationsMore information
Lecture 7: Approximation via Randomized Rounding
Lecture 7: Approximation via Randomized Rounding Often LPs return a fractional solution where the solution x, which is supposed to be in {0, } n, is in [0, ] n instead. There is a generic way of obtainingMore information
Load balancing Static Load Balancing
Chapter 7 Load Balancing and Termination Detection Load balancing used to distribute computations fairly across processors in order to obtain the highest possible execution speed. Termination detectionMore information
1. The memory address of the first element of an array is called A. floor address B. foundation addressc. first address D.
1. The memory address of the first element of an array is called A. floor address B. foundation addressc. first address D. base address 2. The memory address of fifth element of an array can be calculatedMore information
Data Structure [Question Bank]
Unit I (Analysis of Algorithms) 1. What are algorithms and how they are useful? 2. Describe the factor on best algorithms depends on? 3. Differentiate: Correct & Incorrect Algorithms? 4. Write short note:More information
New Hash Function Construction for Textual and Geometric Data Retrieval
Latest Trends on Computers, Vol., pp.483-489, ISBN 978-96-474-3-4, ISSN 79-45, CSCC conference, Corfu, Greece, New Hash Function Construction for Textual and Geometric Data Retrieval Václav Skala, JanMore information
Mathematics Course 111: Algebra I Part IV: Vector Spaces
Mathematics Course 111: Algebra I Part IV: Vector Spaces D. R. Wilkins Academic Year 1996-7 9 Vector Spaces A vector space over some field K is an algebraic structure consisting of a set V on which areMore information
Binary Heap Algorithms
CS Data Structures and Algorithms Lecture Slides Wednesday, April 5, 2009 Glenn G. Chappell Department of Computer Science University of Alaska Fairbanks firstname.lastname@example.com 2005 2009 Glenn G. ChappellMore information
The LCA Problem Revisited
The LA Problem Revisited Michael A. Bender Martín Farach-olton SUNY Stony Brook Rutgers University May 16, 2000 Abstract We present a very simple algorithm for the Least ommon Ancestor problem. We thusMore information
. INNER PRODUCT SPACES.. Definition So far we have studied abstract vector spaces. These are a generalisation of the geometric spaces R and R. But these have more structure than just that of a vector space.More information
Mathematical Induction. Lecture 10-11
Mathematical Induction Lecture 10-11 Menu Mathematical Induction Strong Induction Recursive Definitions Structural Induction Climbing an Infinite Ladder Suppose we have an infinite ladder: 1. We can reachMore information
princeton univ. F 13 cos 521: Advanced Algorithm Design Lecture 6: Provable Approximation via Linear Programming Lecturer: Sanjeev Arora
princeton univ. F 13 cos 521: Advanced Algorithm Design Lecture 6: Provable Approximation via Linear Programming Lecturer: Sanjeev Arora Scribe: One of the running themes in this course is the notion ofMore information
Linear Programming. March 14, 2014
Linear Programming March 1, 01 Parts of this introduction to linear programming were adapted from Chapter 9 of Introduction to Algorithms, Second Edition, by Cormen, Leiserson, Rivest and Stein [1]. 1More information
ALLIED PAPER : DISCRETE MATHEMATICS (for B.Sc. Computer Technology & B.Sc. Multimedia and Web Technology)
ALLIED PAPER : DISCRETE MATHEMATICS (for B.Sc. Computer Technology & B.Sc. Multimedia and Web Technology) Subject Description: This subject deals with discrete structures like set theory, mathematicalMore information
PES Institute of Technology-BSC QUESTION BANK
PES Institute of Technology-BSC Faculty: Mrs. R.Bharathi CS35: Data Structures Using C QUESTION BANK UNIT I -BASIC CONCEPTS 1. What is an ADT? Briefly explain the categories that classify the functionsMore information


text: A beverage quaffed directly after drinking another (usually alcoholic) potable. Retrieved from "http://recipes.wikia.com/wiki/Chaser?oldid=648323" Ad blocker interference detected! Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers Wikia is not accessible if you've made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected. Categories: Liquids and beverages Add category Cancel Save

subset: commoncrawl


text:
Coltrane's genius shines through in these stunning tenor sax transcriptions of classic solos from 14 tunes in the great American songbook, including: All or Nothing at All; The Inch Worm; It's Easy
This item has been discontinued and we can only sell our remaining stock. Add to cart to check availability and for more information.
This amazing collection of 24 transcribed solos represents some of the world's greatest saxophone artists, including: St. Thomas (Sonny Rollins); Body and Soul (Coleman Hawkins);
This historical edition includes complete transcriptions of every recorded solo by jazz master John Coltrane on his legendary composition Giant Steps...all 96 choruses! It also includes analyses of
Here are note-for-note solo transcriptions of 19 songs from this gifted saxophonist, including: Cajun; Chime This; Don't Try This at Home; Escher Sketch; Funky Sea, Funky Dew; Inside Out; Itsbynne Reel;
Includes 17 classic transcriptions including: Audry, Bossa Antiqua, Jazzabelle, Take Five, Take Ten and many more! Chord symbols included. Play in the style of Dave Brubeck's legendary sideman!
Orchestrate Your Inbox
What are your interests? Fine-tune your email so you receive only what's important to you.
Thank you! Please check your inbox. We've sent an email with a link to update your preferences.
Pepper Music eClubs
Everything you need for the upcoming season and special recommendations from our editors! Each club is sent monthly (unless otherwise noted).
General Music
Music Library
Cued In - The Pepper Blog
A weekly digest of insightful articles, helpful resources, and interviews with leading composers and arrangers
Subscribe to Cued In
Thanks, you're almost done! Please check your inbox and click the link to complete your subscription.


text:
新幻想郷Timeline: Scenario: Desire Drive
|New Hakurei
|Electro Yen
Neo Gensokyo is a nation and a planet in the Sunflower Galaxy. It was established in Year 800,000,000 by many Earth residents, mainly from Japan, China, Korea, South East Asia, and India.
The planet was one of the few to be built by complex technology. Its environment is similar to Earth, though is Twenty Degrees Celsius cooler on average. The planet is slightly larger than Saturn. Over Fifty-Five Percent of Neo Gensokyo is covered in water, while the rest consisting of continents and islands which together have many lakes and other sources of water that contribute to the hydrosphere. The poles are covered in Ice Sheets, like Earth.
Neo Gensokyo has Eleven Continents, with Two of them located at the North and South Pole. Despite this, all of them have Permanent Humanoid settlements, with the Poles containing the least population.
Here is a list of continents:
- Yangtze
- New India
- Hokkai
- Meikai (冥界)
- Borderland
- Mononobe
- Zhōngjiāndàlù (中間大陸)
- New Indonesia
- New Shikoku
- Kōritairiku (氷大陸) (South Pole)
- Iceland (North Pole)


text:
Tuesday, August 29, 2006
VitalStream Gets Win At ABC Radio
Irvine-based VitalStream has signed on ABC Radio to provide online ad-insertion and streaming media, the firm reported Monday. Vitalstream said that it will provide Windows Media Streaming Services for the majority of ABC's radio stations and network properties, and will also represent ABC Radio's streaming inventory for advertising sales. Terms of the deal were not disclosed. VitalStream provides streaming media services to online media providers.


text: Last week I was invited to Washington D.C. to participate in an elite panel on the future of retirement savings, a discussion sponsored by the Aspen Institute. One highly respected expert started talking about investments and savings, noting that along with Social Security, they were the basis of boomer retirement income. I could barely contain my reaction as I waved my hand to comment: "If you believe in the Social Security 'Trust Fund,' you must also believe in the tooth fairy!" I said. There was stunned silence. I suggested that if we were to come up with solutions, we'd have to start from the truth. And the truth is, this recession has brought the Social Security crisis even closer to the brink. The recent rise in unemployment translates into a sharp drop in payroll "contributions." The problem of the future is now in the present. Since the late 1980s, the government budget has been combining the "accounting surplus" in the so-called Social Security "trust fund" with the continuing requirements of government spending. Thus, this year's $1.8 trillion budget deficit, or whatever it turns out to be, is consuming almost every bit of that "surplus" that was supposed to be accumulating to pay baby boomers' retirement benefits! Open that "shoebox in Maryland" (if you don't understand that expression, you are so young, you will get nothing from Social Security) and all you'll find are paper IOUs from the federal government.


text:
We'd love to hear from you, and we'd also love to share the latest news as soon as it's available. Enter your email address and we'll keep you in the loop.
"Like" us on Facebook and become part of the conversation as this new instrument comes into being.
Acoustic Synthesis
Promote Your Page Too
We'd love to hear from you too. Use the contact form below if you'd like to send us a message.
[contact-form][contact-field label='Name' type='name' required='1'/][contact-field label='Email' type='email' required='1'/][contact-field label='Website' type='url'/][contact-field label='Comment' type='textarea' required='1'/][/contact-form]


text:
You know what they say, if the dress fits… buy it in every color.
I live in Phoenix where the average summer temperature is 112 degrees. I like to look polished and professional but still try to stay cool. Dresses and skirts do the trick for me. Every summer it is a challenge to try and find such garments that are not lined in heat trapping, sweat inducing polyester or rayon.
Cruising through TJ Maxx I spotted a classic cotton sundress. It was unlined, but the fabric was a good weight. (Remember I always wear a cotton slip underneath anyways.) I saw that it came in three prints and two solids (pink and navy). Although I didn't need the solid colors, I hemmed and hawed for a good 15 minutes asking myself "Should I buy the same exact dress?"
I then looked at the price tag again. $15.99. Yes, yes I should. If you have a need you should too.
Linking to:


text:
Welcome to the ineedhits Search Engine Marketing blog, where we share the latest search engine and online marketing news, releases, industry trends and great DIY tips and advice.
A recent study by Harvard professor Ben Edelman has uncovered a sneaky tactic by Google from its toolbar.
Google's Toolbar acts as a gateway, for searchers, to a variety of Google software services. Of course, many of these services require a user to provide Google with information on the site that's currently displayed in the browser and this is where the problem lies.
Edelman has discovered that the Google toolbar keeps tracking your browsing even after you disable that option.
Here is a rundown from his study:
In this article, I provide evidence calling into question the ability of users to disable Google Toolbar transmissions.
I begin by reviewing the contents of Google's "Enhanced Features" transmissions. I then offer screenshot and video proof showing that even when users specifically instruct that the Google Toolbar be "disable[d]", and even when the Google Toolbar seems to be disabled (e.g., because it disappears from view), Google Toolbar continues tracking users' browsing.
I then revisit how Google Toolbar's Enhanced Features get turned on in the first place – noting the striking ease of activating Enhanced Features, and the remarkable absence of a button or option to disable Enhanced Features once they are turned on. I criticize the fact that Google's disclosures have worsened over time, and I conclude by identifying changes necessary to fulfill users' expectations and protect users' privacy.
Edelman used a network sniffer to see exactly how the toolbar sends data back to Google even though it has been disabled. There is a video screen cast here if you would like to see the experiment in detail.
So what has Google got to say for itself? A Google spokesperson tells us this has now been fixed:
To be clear, this is only an issue until a user restarts the browser, and it only affects the currently open tabs for a small number of users.
Specifically it affects those using Google Toolbar versions 6.3.911.1819 through 6.4.1311.42 in Internet Explorer, with enhanced features enabled, who chose to disable Toolbar without uninstalling it. Once the user restarts the browser, the issue is no longer present. A fix that doesn't require a browser restart is now available on www.google.com/toolbar and in an automatic update to Google Toolbar that we are starting today.
This is an interesting find, especially in the wake of the latest privacy issues in China causing Google to consider pulling out. Although Google was quick to attack the Chinese government for abusing privacy rights, it seems they have a few privacy concerns of their own to resolve.
Keep up to date with the latest from our blogs.
The List: What Has Google Done for You Lately?
To say that Google is a busy company is probably an understatement. Almost every week we hear of either a ...


text:
Question: Describe the accounting policies that MHR uses to account for
Describe the accounting policies that MHR uses to account for its inventory. What costs are included in the Canadian product inventory? What does the term "net realiz able value" mean? How would MHR know the net realizable value of its inventory?
View Solution:
View Solution:
Answer to relevant QuestionsWhat was the cost of goods sold by MHR in 2011 and 2010? What was the cost of inventory recognized as an expense in each year? Why do the amounts differ? Calculate MHR's gross margin and gross margin percentage for 2011 and ...An important part of MHR's business is publishing and selling textbooks (like this one). What do you think are some of the challenges MHR faces with respect to managing its textbook inventory? What important decisions must ...Academic research has shown that the stock price of a public company isn't affected by the depreciation method an entity uses. Why do you think this is the case? Does the depreciation method an entity uses ever matter? ...For each business identified below, explain how the capital asset contributes to generating revenue by the business:Business Asseta. Lawn care Lawn mowerb. Arena Zamboni machinec. Jewellery store Display casesd. Doctor's ...Explain why repairs are expensed whereas betterments are capitalized.
Post your question


text:
Matching: httpd X
- Sort by:
- Date ▼
- Title
- Likes/Votes
- Comments
- Views
Find long-running IHS (web) requests
Quick way to locate or watch for long-running IHS requests: Logging response times Enable microsecond response time logging with the %D LogFormat option . For example: LogFormat "%h %l %u %t...Modified on by DougBreaux
mod_mpmstats to analyze thread usage in IBM HTTP Server
(Related to my earlier post on mod_status .) Found this useful tidbit today from IBM HTTP Server Performance Tuning : For IBM HTTP Server 7.0 and later, mod_mpmstats is enabled automatically. Check entries like this in the error...Modified on by DougBreaux
Using IBM HTTP Server 6.1 diagnostic capabilities with WebSphere
DougBreaux Tags: httpd plugin apache debugging mod_status diagnostic websphere ihs 1 Comment 5,826 Views
Using IBM HTTP Server 6.1 and later diagnostic capabilities with WebSphere This could be useful. Apache mod_status is available in IHS, and when it's enabled it provides information about the individual threads running under the httpd processes. The...
Tip: Finding exact version and applied patches of IBM HTTP Server
DougBreaux Tags: web-server tips ihs patch httpd apache maintenance 7 Comments 4,948 Views
apachectl -V For instance Server version: IBM_HTTP_Server/188.8.131.52 Apache/2.0.47 Server built: Mar 3 2010 21:55:48 Build level: IHS60/webIHS1009.03 Server's Module Magic Number: 20020903:4 Architecture: 32-bit Server compiled with.... -D...


text: Maintree Walkeline de Ferrières (-c1040) Henry de Ferrières (c1030-) Retrieved from "http://familypedia.wikia.com/wiki/Henry_de_Ferri%C3%A8res_(c1030-)/tree?oldid=835420" Ad blocker interference detected! Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers Wikia is not accessible if you've made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected. Hidden category: Tree pages


text:
This disambiguation page lists articles that might otherwise share the same title.
If an article link led you here, please change the link to point directly to the intended page.
Tank can refer to:
- Alex Sione Tauoa: also known as Alofa The Samoan Tank
- Mike Hallick: Also known as Tank in the USWA and WWF
- Christian Vester
- Christos Gabriel: Also known as Tank in the IWS
- David Lee Abbott: also known as Tank Abbot
- Kerry Diamond
- Jonathan Michael Toland: also known as Tank Toland
- Michael Hallick
- Paul McManus
- Sean Allen
- Tank Bishop
- Tank Douglas
- Tank Lawson
- Tank O Rooney
- Tank Thomas
- Warren Hullander: Also known as Tank


text:
Auditing and examining Travel and Entertainment Expenses: Expense Reimbursement Fraud
Product ID: 703767
- Duration: 90 Min
Customer Care
Fax: +1-650-565-8542
Email: email@example.com
This training program will address why internal controls over travel and entertainment (T&E) expenditures are a critical component of the control environment. Although the topic of travel and entertainment abuse is not one that management likes to address, it is a very important indicator of the adequacy of a company's control environment.
Why Should You Attend:
If you are reviewing entertainment expenses and find discrepancies, how often do you hear management say, "What's the big deal? How bad could it be?" This is a prime indicator that there is a gap in understanding of the importance of simple internal controls and a sound control environment.
With today's advanced technology and digital media one would think that tracking simple T&E expenditures would be efficient. Yet with technological advancements comes new and innovative ways for individuals to side-step control procedures and slip the inadvertent expense through the system.
This webinar will discuss the impact of T&E abuse on various risk areas. Among other discussions, the course will also highlight areas of T&E abuse that often go unnoticed and result in expenditure fraud.
Areas Covered in the Webinar:
- Why internal controls over T&E expenditures are a critical component of the control environment.
- The impact abuse of T&E can have on various risk areas.
- Areas of T&E abuse that often go unnoticed and can result in expenditure fraud.
- Identifying T&E red flags for fraud with data analytics.
- The role of technology in the advancement of control gaps.
- How to talk to management about identified findings.
Who Will Benefit:
- CEOs/CFOs
- Board Members
- Internal Auditors
- Compliance Professionals
- Operational Professionals
- Audit and Risk Professionals
- Finance Professionals
- Legal Department
- HR Personnel/Managers/Staff
Lynn Fountain
Former Chief Audit Executive, Aquila
Lynn Fountain has over 35 years of experience spanning public accounting, corporate accounting and consulting. She has 20 years of experience working in the areas of internal and external auditing. She is a subject matter expert in multiple fields including internal audit, ethics, fraud evaluations, Sarbanes-Oxley, enterprise risk management, governance, financial management and compliance.
Ms. Fountain has held two chief audit executive positions for international companies. Since 2008, she has served in positions where she was responsible for internal audit, enterprise risk management and Sarbanes-Oxley. Ms. Fountain has a private consulting and training business, and she has developed and delivered leading edge training sessions on COSO, internal audit, ERM, accounting, leadership, governance, compliance and ethics. She delivers training for the American Institute of Certified Public Accountants, Institute of Internal Auditors, and multiple seminar and training groups.
Ms. Fountain is the author of two technical books that released in 2015: Raise the Red Flag – The Internal Auditors Guide to Fraud Evaluations; Leading the Internal Audit Function. In addition, Ms. Fountain is a frequent blogger on the LinkedIn platform and has also had numerous articles published in professional and technical publications. She is currently authoring a third technical book on corporate ethics and the internal auditor's challenge.
She has performed as an adjunct instructor for the School of Business for Grantham University and developed the first internal audit curriculum for the School of Business at the University of Kansas. Ms. Fountain obtained her BSBA from Pittsburg State University and her MBA from Washburn University in Kansas. She has her CGMA, CRMA credentials and CPA certificate (non-active).
Topic Background:
Although travel and entertainment expenses are often a small component of overall corporate expenditures, they are one of the highest inherent risk areas for inappropriate costs and fraud. Expenditures are a businessman's best friend but can be management or an auditor's worst nightmare if not properly handled. This process area inherently provides prime opportunity for unauthorized or inappropriate and lavish expenditures by executives and personnel. When this occurs, there is more than just dollars at stake for the company. Uncontrolled and mismanaged travel and entertainment expenditures can impact reputation, operations and compliance areas.
Regulators and several legislations suggest annual review of executive expenditures. However, this can be a risk laden area for compliance professionals to review due to the internal political ramifications. In today's world of transparency and increasing frauds, management must learn that attention, monitoring and periodic review of travel and entertainment expenses is an important component of maintaining proper internal controls.
More Trainings by Expert
Auditing of Environmental, Health and Safety programs for the non-technical auditor
Internal Controls - What Every Manager Needs to Know
Why Fraud Happens and What to do: Critical Concepts on How to Prevent, Detect and Mitigate Fraud
Refund Policy
Registrants may cancel up to two working days prior to the course start date and will receive a letter of credit to be used towards a future course up to one year from date of issuance. ComplianceOnline would process/provide refund if the Live Webinar has been cancelled. The attendee could choose between the recorded version of the webinar or refund for any cancelled webinar. Refunds will not be given to participants who do not show up for the webinar. On-Demand Recordings can be requested in exchange.
Webinar may be cancelled due to lack of enrolment or unavoidable factors. Registrants will be notified 24hours in advance if a cancellation occurs. Substitutions can happen any time.
If you have any concern about the content of the webinar and not satisfied please contact us at below email or by call mentioning your feedback for resolution of the matter.
We respect feedback/opinions of our customers which enables us to improve our products and services. To contact us please email email@example.com call +1-888-717-2436 (Toll Free).
Product Reviews
This product hasn't received any reviews yet. Be the first to review this product! Write review
Pharmaceutical Compressed Air - Quality GMP Standards and RequirementsBy: Roger Cowan
Price: $249
How to Conduct a HIPAA Risk AssessmentBy: Brian Tuttle
Price: $249
Building a Vendor Qualification Program for FDA Regulated IndustriesBy: Jonathan M Lewis
Price: $249
FDA Regulations for Marketing OTC Drugs in the U.S.By: Norma Skolnik
Price: $249
Effective Annual U.S. FDA CGMP TrainingBy: John E Lincoln
Price: $249
CDISC Mapping 1: Specifications and FDA RequirementsBy: Sunil Gupta
Price: $249
Extractables and Leachables in Early Phase DevelopmentBy: Wayland Rushing
Price: $279
Veterinary Medicine and the DEA Due Diligence Requirement for Dispensing and Prescribing...By: Carlos Aquinos
Price: $229
1099 & W-9 Update - Complying with IRS Information Reporting GuidelinesBy: Miles Hutchinson
Price: $149
OSHA Recordkeeping for 2015: Beyond the OSHA 300 SummaryBy: David A. Casavant
Price: $149
Form I-9 and E-Verify, getting and staying compliantBy: Cathleen Hampton
Price: $149
Affordable Care Act Updates: What Employers need to do to PrepareBy: Vanessa G Nelson
Price: $149
Child Support: What Payroll Doesn't Know Can Hurt YouBy: Vicki M. Lambert
Price: $229
Detecting and Preventing Embezzlement in Your OrganizationBy: Peter Goldmann
Price: $249
What Employers Need to Know About Severance AgreementsBy: Janette Levey Frisch
Price: $229
FDA's Regulation of Regenerative Medicine including Stem Cell Treatments, Tissue...
Newark, NJ | Oct 19-20, 2017
FDA's New Import Program for 2017 - Strict Precision: 2-Day In-Person Seminar by Ex-FDA Official
Philadelphia, PA | Aug 24-25, 2017
Navigating the Maze for Post-Market Compliance -- Complaint Handling, MDRs, Recalls...
Minneapolis, MN | Oct 19-20, 2017
21 CFR Part 11 Compliance for SaaS/Cloud Applications: 2-day In-person Seminar
Philadelphia, PA | Sep 14-15, 2017
Quality Control Laboratory Compliance - cGMPs and GLPs: One and a Half-day In-person Seminar
San Francisco, CA | Nov 9-10, 2017
Effective Quality Oversight of Pharmaceutical Contract Manufacturing Organizati...
San Francisco, CA | Jul 27-28, 2017
Latin America: Regulatory Compliance Requirements for Life Science Products...
Philadelphia, PA | Aug 24-25, 2017
Computer System Validation - Reduce Costs and Avoid 483s: 2-Day In-Person Seminar
Philadelphia, PA | Sep 14-15, 2017
Complete 1099, TIN Matching, B-Notice, FATCA and Nonresident Alien 1042-S Compl...
San Francisco, CA | Jul 27-28, 2017
Ensuring Compliance with Advertising and Promotional Requirements for Drugs and...
Boston, MA | Nov 9-10, 2017
Managing Your FDA Inspection: Before, During and After: 2-Day In-Person Seminar by Ex-FDA Official
Tampa, FL | Aug 17-18, 2017
ACH Risk Management: 2-day Workshop
Boston, MA | Jul 20-21, 2017
Metrics & Predictive Analytics in Human Resources-Reducing Risk and Improving...
Washington, DC | Sep 14-15, 2017
Designing and Sustaining New and Existing Product Stability Testing Program
San Diego, CA | Sep 4-5, 2017
Managing an Effective AML Compliance Program: 2-day In-Person Seminar
Chicago, IL | July 20-21, 2017
General requirements for the competence of testing and calibration laboratoriesProvider: ANSI
Price: $142
IEC 62304:2015 ''Medical Device Software - Software Life Cycle Processes''Provider: SEPT
Price: $299
IEC 62304:2015 ''Medical Device Software - Software Life Cycle Processes''Provider: SEPT
Price: $149
ISO 13485 Procedure 754-Customer PropertyProvider: 13485 Store
Price: $12
Measurement management systems - Requirements for measurement processes and measuring equipmentProvider: ANSI
Price: $120
Geometrical Product Specifications (GPS) - Geometrical tolerancing - Tolerances of form, orientation...Provider: ANSI
Price: $250
Templates and Plans for Software Configuration Management Documents-Version 6.0Provider: SEPT
Price: $299
Computer System Validation Master PlanProvider: LabCompliance
Price: $90
Zero Acceptance Number Sampling Plan for Receiving, In-Process and Final InspectionProvider: Quality-Control-Plan
Price: $37
Standard Operating Procedure: FDA InspectionsProvider: LabCompliance
Price: $49
AS9003 Comprehensive Quality System Kit for Inspection and Test Quality Control SystemProvider: At-PQC
Price: $397
ISO 13485 and FDA Compliant Internal Audit Tools: Checklist, Procedure and FormsProvider: 13485 Store
Price: $95
Template for a Software Maintenance Plan - Fourth EditionProvider: SEPT
Price: $99
Sarbanes Oxley Treasury Risks and ControlsProvider: Audit Net
Price: $50
ISO 13485 Gap ChecklistProvider: 13485 Store
Price: $59


text:
'Bomb the Republic': What British spooks told Brian Nelson
British intelligence spooks told Brian Nelson to get the UDA to bomb the Republic.
And they even suggested a strategic economic target – an oil terminal in Cork, thought to be the Whiddy Oil terminal.
Revelations that elements within the British military establishment were advocating bombing raids on a neighbouring state will stun observers.
The cross-border raid was intended to pressurise the Dublin government into rethinking its extradition policy.
The British were constantly thwarted and frustrated in their attempts to bring suspected republican terrorists back from the Republic to stand trial.
It wasn't the first time the secret hand of British spooks was seen to be guiding loyalist paramilitaries. Security service involvement was always suspected in the Dublin/Monaghan bombings 13 years earlier.
The Nelson files reveal for the first time the lengths to which spymasters were prepared to go to force Dublin's hand.
And he reveals that were it not for the IRA murder of UDA boss John McMichael in December 1987, the bombing raid would have gone ahead.
The target had been scouted, pictures taken and a plan drawn up – the fruition of a British military plot to bomb Ireland.
In his own words Nelson describes how the plot was first mooted during a routine meeting with handlers at which he was showing off listening devices he had persuaded UDA chiefs to buy with the intention of bugging Sinn Fein offices in west Belfast.
"I had informed BMI [British Military Intelligence] by telephone that I had been given these items of interest and I was instructed to bring them along with me to our next de-briefing," he writes.
"I was told by Mags [Margaret, one of his handlers] that the Boss would be coming along. During the de-brief all what I had been given... was photographed."
He said the Boss had been impressed with the UDA use of intelligence fed to them through Nelson by military intelligence.
"After the de-brief proper finished the Boss was chatting to me about the UDA and the personalities at the top of the organisation, when he said to me that the UDA should think about undertaking an economic bombing campaign down South across the border.
"He then went on to explain what he meant and the reason.
"He put it to me that if the UDA were to conduct a bombing campaign on carefully selected targets that would cause maximum economic damage, because of the present state of Eire's economy a campaign directed at commercial targets, if they were successful, would put an enormous strain upon an already troubled economy, and would cause the Eire government to have a re-think on their extradition policy."
It was clear the British had already identified and researched what they thought would be the ideal target.
By his own hand: Brian Nelson describes how spooks asked him to get UDA to bomb the Republic
When Nelson said he was confident the UDA had the capability to carry out a raid deep inside the Republic, his spymaster replied simply "good".
"He then told me that the oil terminal outside Cork would be well worth a look at. I said I would have to talk to the right people but I didn't see any problems.
"The Boss replied: 'I'll leave it with you then.'"
"That was that. Shortly after this the Boss left and after finishing the de-brief I was given my customary escort part way back to Belfast. "
Nelson set about planting the idea, broaching the subject with Tucker Lyttle a couple of days later.
But he says he was told to "forget about it and concentrate our efforts this side of the border".
Behind Lyttle's back, Nelson a meeting with overall UDA boss John McMichael.
His file on that meeting reads that he met McMichael "in private" in the kitchen of the UDA's headquarters in Gawn Street in east Belfast.
"Once there I went over what had been put to me by the Boss and included the likely target of the oil terminal at Cork which if done properly with a few supermarkets could produce the desired effect. The cost in compensation would run to millions which would have to be paid by the (Dublin) government."
There is no mention of possible civilian casualties, even though bombing supermarkets is cited.
"Bearing in mind at that time Eire's attitude on extradition was a thorny issue that rankled deeply, so therefore I was able to use the Boss's rational (sic) on the outcome of a successful campaign."
McMichael, he said, was totally taken with the idea. "When I related to my Handlers that McMichael had undertaken the Eire project, no comment was made."
Nelson says that weeks later he met McMichael again, and asked him "how he was getting on down south".
He says McMichael told him he'd had "problems finding someone with the necessary skill to make a bomb that would produce the desired effect with oil tanks, but he reckoned he'd found someone who could do what he required".
But before McMichael could get the bomb and order the bombing of the Cork oil terminals, he himself was murdered by a Provo boobytrap bomb, in December, 1987.
The Nelson files also reveal that McMichael had sent a male and female couple to Cork to 'recce' the terminal target, and take photographs and notes. Nelson made copies, handing them to his handlers.


text:
November 4, 2009 BY Sneaker News
For those of you Air Max heads who have enjoyed the recent simple synthetic suede and mesh Air Max 1 releases will continue to have a number of clean colorways in stores soon. This new Air Max 1 features a simple white and neutral grey base and a vibrant yellow pop for the mid body. The upper body and mudguard is a synthetic suede, while the mesh is a jersey mesh. Look for these at select Nike Sportswear retailers very soon.
Style: 308866-102
Color: Neutral Grey/Vibrant Yellow
Filed under: Air Max 1 Just Released Nike Air Max


text:
June 12, 2017
Nordic Testing Days
The Nordic Testing Days is an international testing conference for software testers from all over the world. It takes place in Tallinn, Estonia, and has a duration of 2 days plus a tutorial day. I heard a lot of interesting things concerning the topic of software testing and I want to give you a summary about what I've heard.


text:
A collection of SasuSaku One-shots written by yours truly.
Golden_Angel5125 Jul 14
Really?? I want to taste some bitter-sweet thingies like that!!
That_one_girl91 Nov 07, 2016
Modern: Sasuke is a teacher and hears Ino and Sakura talking about him and how Sakura haves feelings for him. He acts all cold but he actually is all flustered? This idea sounded a lot better in my head....
HutchinsonGirl4Ever Nov 26, 2014
modern: sakura tutors sasuke for a class hes failing thank you
MistyAnnE_04 Oct 29, 2014
@AmericaS16 you're welcome! it's the least I can do to show how much I appreciate you guys. ♡
MistyAnnE_04 Oct 29, 2014
@AmericaS16 sure! I'll make one and dedicate it to you by tomorrow, is that okay? :)


text:
Our Girls
Aya Abdelaziz
Member since: 2012 "I found that by investing in myself as an Egyptian female artist and activist I was investing in the world around me."Read More
Dinae Anderson
Member since: 2012 "Now I know the power of my writing. Gloria Steinem, our Special Advisor, made time to read my work. Need I say more?"Read More
Noura Boustany Jost
Member Since: 2013 "GBH addresses issues that people don't want to hear. We take the issues that are happening right now and talk about them because everybody, everybody, needs our help."Read More
Aimee Buchannan
Member Since: 2014 "Going onstage, telling your story, and just being you is really empowering. GBH has brought me to places I could never have imagined."Read More
Shenny De Los Angeles
Member Since: 2014 "Girl Be Heard has enhanced me as a human being, making me a voice for those who have been silenced."Read More
Ayanda Diamini
Member Since: 2013 "I love my Girl Be Heard family!"Read More
Bintou Diaou
Member Since: 2013 "Now I have a whole new community of friends at Girl Be Heard who love me for exactly who I am."Read More
Tiffani-Amber DiGrazia
Member Since: 2010 "Girl Be Heard has been a beacon of light through the hardships of my life."Read More
Avery Dresel Kurt
Member Since: 2014 "Girl Be Heard created a safe space to share my writing and allowed me to unapologetically be myself."Read More
Dominique Fishback
Member since: 2008 "GBH has given me many cinderella moments and has helped some of my dreams come true to the extent that I had to make room for more. So I am forever thankful."Read More
Mildred Victoria Hamm
Member since: 2012 "Girl Be Heard has given me a sense of understanding of my artistic voice, and a platform to speak for the voiceless".Read More
Destini Henry
Member Since: 2014 "GBH is about giving girls voices. I want people, especially little girls, to hear our words and find the courage to make themselves heard. There is no reason for anyone to silence you."Read More
Deanna Alexandra Ibrahim
Member Since: 2009 "GBH has encouraged me to use art as a tool for social change. It's a movement like nothing else I've ever experienced."Read More
Kayla Irizarry
Member Since: 2013 "I didn't even know how much I needed this until it was given to me, and it has truly been a blessing in my life that has also allowed me to find my passion in feminist theatre."Read More
Larissa M. Jeanniton
Member Since: 2014 "GBH is a power source. It has helped me feed my own presence and my own voice. I am now confident speaking as myself."Read More
Ebony Kennedy
Member Since: 2014 "These incredible ladies have inspired me to ask the tough questions in both my writing and my life. Being a company member of GBH has changed my life."Read More
Alex Lee
Member Since: 2014 "Girl Be Heard is my safe haven. I've fallen in love with people I can finally trust, and it's amazing."Read More
Noelia Mann
Member since: 2012 "Girl Be Heard has changed my life forever. I've finally found a home for my inner artist and activist..."Read More
Veronica Marks
Member since: 2013 "I never knew that writing and performing could change the world until I learned about Girl Be Heard."Read More
Allie Marotta
Member since: 2013 "Working with so many talented young girls has proven to be a constant inspiration and has contributed to my best work to date."Read More
Breani Michele
Member since: 2011 "I did not have the confidence to let people hear my writing until I joined Girl Be Heard. I love my Girl Be Heard family; they are like the sisters I never had."Read More
Isabella Olaguera
Member since: 2011 "I hope to inspire others through my work with Girl Be Heard and voice issues that are relevant to girls both nearby and worldwide."Read More
Halle Paredes
Member Since: March 2013 "Once I joined Girl Be Heard, I gained a positive way to use my talent and a loving and supportive family of girls who knew what it was like to struggle like I did."Read More
Victoria Pannell
Member Since: 2014 "Girl Be Heard has given me a platform to express myself without shame or judgment. It has made me feel beautiful."Read More
Shaquilla Parker
Member since: 2013 "I can now vent and release everything I have buried within myself for all these years. Girl Be Heard has given me the power to be free and happy."Read More
Betsy Perez
Member since: 2011 "Girl Be Heard has given me new life by giving me the space to breathe, yell, sing, write, dance, laugh, and be a girl. I'm a girl who is now being heard."Read More
Jewel Phillips
Member Since: 2014 "GBH taught me that I don't have to keep everything inside. They have taught me that my point of view is okay, because you are you and you are beautiful."Read More
Allysia Potter
Member since: 2012 "I am a first generation college student and thanks to Girl Be Heard, I will one day be the first in my family to receive a college degree."Read More
Jai Raphael
Member since: 2011 "I've entered a gateway filled with open-hearted girls working together to change the world. These girls are my new best friends. There's no better feeling than being surrounded by positivity."Read More
Tiff Roma
Member since: 2010 "Girl Be Heard has helped me realize the true power and importance we hold as performers. It is our job as artists to be activists and advocates for those who are forgotten and for the issues that are under the rug."Read More
Krystal Rosa
Member Since: 2013 "I finally found another family called Girl Be Heard. They took me in as one of their own. I love every single one of my girls."Read More
Sophie Rotenier
Member Since: 2014 "Girl Be Heard has not only made me a better writer, but a better person."Read More
Brianna Schwartz
Member since: 2013 "I have learned what it means to be a sister, an ensemble member. I have made stronger bonds in my first three months at Girl Be Heard than I have in three years."Read More
Julia Seng-Sourinho
Member since: 2013 "I've realized how powerful the female voice truly is, and how much of a difference a group of girls can make."Read More
Shalika Shoulders
Member since: 2012 "These girls inspire me every time I see them on stage. So proud to be a member of Girl Be Heard."Read More
Kristi Tartaglione
Member since: 2012 "I've always been invested in listening to others and learning from people and the world around me. The brilliant part of Girl Be Heard is we are a family."Read More
Melanie Thompson
Member since: 2012 "Girl Be Heard has helped me develop as an artist and has given me a 3rd family. GBH is the safest and one of the only places I want to be."Read More
Karen Lee Vigo
Member since: 2010 "Girl Be Heard made me not only want to be an actress and performer, but also an activist and feminist. GBH has made me appreciate the opportunities in my life and made me want to speak out for girls..."Read More
Sophie Walker
Member Since: 2011 "I am forever thankful to Girl Be Heard for teaching me that I am a writer."Read More
Laura Wynne
Member Since: 2014 "Through Girl Be Heard I have learned to channel my creative writing into something that can become more than another page in a journal. GBH has made me feel like I can change the world."Read More
Bleu Zephra Santiago
Member Since: 2013 "Girl Be Heard has taught me that my art is about more than just me and my passion, it is also about the people that see and are influenced by my art."Read More


text:
After the War
Press [Alt] + 1 + B on level 1, or [Alt] + 1 + M for level 2.
Level 2 Password
Enter 101069 at the password screen.
Know Something We Don't?
You can submit new cheats for this game and help our users gain an edge.
Have We Been Fooled?
You can submit a problem report for any non-working or fake code in the lists above.


text:
Online Electrical Services | Commercial Electrical Services | LED Lighting Systems
approva.net - Environmental Benefits using solar power for commercial and residential. Telecommunication services and LED Lighting are a cost effective solution. CAE Services expertise in LED lighting systems and lighting systems.
Telecommunication Services
www.caeservices.com.au - Environmental Benefits using solar power for commercial and residential. Telecommunication services and LED Lighting are a cost effective solution. CAE Services expertise in LED lighting systems and lighting systems.
Race Bibs Holder
www.runningonthewall.com - Display your running medals with a nice running medal holder. Running on the Wall provides the attractive race bibs holder and marathon medals display which are designed using the wooden frames and stands which can also be used in home ...
Running Medal Displays
www.runningonthewall.com - Running on the Wall designs and produces running medal displays and holders, race bibs holder to show off the medals and racing bibs in attractive way created with wooden displays containing a home décor style.
Rocks And Minerals For Sale
mineralgallery.net - Searching for fossils and crystals for sale? Find here the best antique rocks and minerals for sale where the art of nature is sculpted on the stone at reasonable cost.
Businesses For Sale
www.mergersandacquisitionsaustralia.com.au - Mergers and acquisitions services are offered at reasonable and unbeatable cost at Australia. Increase the sale of business by consuming our quality services for selling business.
Blood Sugar Chart
www.living-healthy-with-diabetes.com - Here blood sugar chart remains an excellent way to track your own blood glucose levels, so that you can avoid running into problems at a given time of the day.
Pre Diabetes
www.living-healthy-with-diabetes.com - When you go into the beginning stages of diabetes, it means that you are at the beginning of this process. You will likely feel a decrease in energy because the glucose is not reaching your cells.
Testing For Diabetes
www.living-healthy-with-diabetes.com - This test requires you to have kept your stomach empty of all food for at least 8 hours, and, fortunately, it is most effective in the morning.
Glucose Monitors
www.living-healthy-with-diabetes.com - Glucose monitors are an easy and portable way to keep an eye on your blood glucose levels throughout the day. You should test your levels before and after meals, as well as at random times daily to ensure that your ...


text: Hi, It would be nice if we had an automatic sitemap generator which automatically generates sitemaps and notifies the search engines about them. It can set the priority of the links according to the activity on each thread and updates it all the time a new site map is re-generated. Thanks!