text:
Chapter 7. Data Structures for Strings
- Jessica White
- 2 years ago
- Views:
1 Chapter 7 Data Structures for Strings In this chapter, we consider data structures for storing strings; sequences of characters taken from some alphabet. Data structures for strings are an important part of any system that does text processing, whether it be a text-editor, word-processor, or Perl interpreter. Formally, we study data structures for storing sequences of symbols over the alphabet Σ = {0,..., Σ 1}. We assume that all strings are terminated with the special character $ = Σ 1 and that $ only appears as the last character of any string. In real applications, Σ might be the ASCII alphabet ( Σ = 128); extended ASCII or ANSI ( Σ = 256), or even Unicode ( Σ = 95, 221 as of Version 3.2 of the Unicode standard). Storing strings of this kind is very dierent from storing other types of comparable data. On the one hand, we have the advantage that, because the characters are integers, we can use them as indices into arrays. On the other hand, because strings have variable length, comparison of two strings is not a constant time operations. In fact, the only a priori upper bound on the cost of comparing two strings s 1 and s 2 is O(min( s 1, s 2 }), where s denotes the length of the string s. 7.1 Two Basic Representations In most programming languages, strings are built in as part of the language and they take one of two basic representations, both of which involve storing the characters of the string in an array. Both representations are illustrated in Figure 7.1. In the null-terminated representation, strings are represented as (a pointer to) an array of characters that ends with the special null terminator $. This representation is used, for example, in the C and C++ programming languages. This representation is fairly straightforward. Any character of the string can be accessed by its index in constant time. Computing the length, s, of a string s takes O( s ) time since we have to walk through the array, one character at a time until we nd the null terminator. Less common is the pointer/length representation in which a string is represented as (a pointer 43
2 CHAPTER 7. DATA STRUCTURES FOR STRINGS 44 g r a i n - f e d o r g a n i c $ p g r a i n - f e d o r g a n i c l 17 5 organ Figure 7.1: The string \grain-fed organic" represented in both the null-terminated and the pointer/length representations. In the pointer/length representation we can extract the string \organ" in constant time. to) an array of characters along with a integer that stores the length of the string. The pointer/length representation is a little more exible and more ecient for some operations. For example, in the pointer/length representation, determining the length of the string takes only constant time, since it is already stored. More importantly, it is possible to extract any substring in constant time: If a string s is represented as (p, l) where p is the starting location and l is the length, then we can extract the substring s i, s i+1,..., s i+m by creating the pair (p + i, m). For this reason several of the data structures in this chapter will use the pointer/length representation of strings. 7.2 Ropes A common problem that occurs when developing, for example, a text editor is how to represent a very long string (text le) so that operations on the string (insertions, deletions, jumping to a particular point in the le) can be done eciently. In this section we describe a data structure for just such a problem. However, we begin by describing a data structure for storing a sequence of weights. A prex tree T is a binary tree in which each node v stores two additional values weight(v) and size(v). The value of weight(v) is a number that is assigned to a node when it is created and which may be modied later. The value of size(v) is the sum of all the weight values stored in the subtree rooted at v, i.e., size(v) = weight(u). u2t (v) It follows immediately that size(v) is equal to the sum of the sizes of v's two children, i.e., size(v) = size(left(v)) + size(right(v)). (7.1) When we insert a new node u by making it a child of some node already in T, the only size values that change are those on the path from u to the root of T. Therefore, we can perform such an insertion in time proportional to the depth of node u. Furthermore, because of identity (7.1), if all the size values in T are correct, it is not dicult to implement a left or right rotation so that the size values
3 CHAPTER 7. DATA STRUCTURES FOR STRINGS 45 remain correct after the rotation. Therefore, by using the treap rebalancing scheme (Section 2.2), we can maintain a prex-tree under insertions and deletions in O(log n) expected time per operation. Notice that, just as a binary search tree represents its elements in sorted order, a prex tree implicitly represents a sequence of weights that are the weights of nodes we encounter while travering T using an in-order (left-to-right) traversal. Let u 1,..., u n be the nodes of T in left-to-right order. We can use prex-trees to perform searches on the set i W = w i : w i = weight(u i ). j=1 That is, we can nd the smallest value of i such that w i x for any query value x. To execute this kind of query we begin our search at the root of T. When the search reaches some node u, there are three cases 1. x < weight(left(u)). In this case, we continue the search for x in left(u). 2. weight(left(u)) x < weight(left(u)) + weight(u). In this case, u is the node we are searching for, so we report it. 3. weight(left(u)) + weight(u) x. In this case, we search for the value in the subtree rooted at right(u). x 0 = x size(left(u)) weight(u) Since each step of this search only takes constant time, the overall search time is proportional to the length of the path we follow. Therefore, if T is rebalanced as a treap then the expected search time is O(log n). Furthermore, we can support Split and Join operations in O(log n) time using prex trees. Given a value x, we can split a prex tree into two trees, where one tree contains all nodes u i such that i weight(u i ) x j=1 and the other tree contains all the remaining nodes. Given two prex trees T 1 and T 2 whose nodes in left-to-right order are u 1,..., u n and v 1,..., v m we can create a new tree T 0 whose nodes in left-to-right order are u 1,..., u n, v 1,..., v n. Next, consider how we could use a prex-tree to store a very long string t = t 1,..., t n so that it supports the following operations. 1. Insert(i, s). Insert the string s beginning at position t i in the string t, to form a new string t 1,..., t i 1 s t i+1,..., t n Delete(i, l). Delete the substring t i,..., t i+l 1 from S to form a new string t 1,..., t i 1, t i+l,..., t n. 1 Here, and throughout, s 1 s 2 denotes the concatenation of strings s 1 and s 2.
4 CHAPTER 7. DATA STRUCTURES FOR STRINGS Report(i, l). Output the string t i,..., t i+l 1. To implement these operations, we use a prex-tree in which each node u has an extra eld, string(u). In this implementation, weight(u) is always equal to the length of string(u) and we can reconstruct the string S by concatenating string(u 1 )string(u 2 ) string(u n ). From this it follows that we can nd the character at position i in S by searching for the value i in the prex tree, which will give us the node u that contains the character t i. To perform an insertion we rst create a new node v and set string(v) = s 0. We then nd the node u that contains t i and we split string(u) into two parts at t i ; one part contains t i and the characters that occur before it and the second part contains the remaining characters (that occur after t i ). We reset string(u) so that it contains the rst part and create a new node w so that it string(w) contains the second part. Note that this split can be done in constant time if each string is represented using the pointer/length representation. At this point the nodes v and w are not yet attached to T. To attach v, we nd the leftmost descendant of right(u) and attach v as the left child of this node. We then update all nodes on the path from v to the root of T and perform rotations to rebalance T according to the treap rebalancing scheme. Once v is inserted, we insert w in the same way, i.e., by nding the leftmost descendant of right(v). The cost of an insertion is clearly proportional to the length of the search paths for v and w, which are O(log n) in expectation. To perform a deletion, we apply the Split operation on treaps to make three trees. The tree T 1 contains t 1,..., t i 1, the tree T 2 contains t i,..., t i+l 1 and the treap T 3 that contains t i+l,..., t n. This may require splitting the two substrings stored in nodes of T that contain the indices i and l, but the details are straightforward. We then use the Merge operation of treaps to merge T 1 and T 3 and discard T 2. Since Split and Merge in treaps each take O(log n) expected time, the entire delete operation takes in O(log n) expected time. To report the string t i,..., t i+l 1 we rst search for the node u that contains t i and then traverse T starting at node u. We can then output t i,..., t i+l 1 in O(l + log n) expected time by doing an in-order traversal of T starting at node u. The details of this traversal and its analysis are left as an exercise to the reader. Theorem 18. Ropes support the operations Insert and Delete on a string of length n in O(log n) expected time and Report in O(l + log n) expected time. 7.3 Tries Next, we consider the problem of storing a collection of strings so that we can quickly test if a query string is in the collection. The most obvious application of such a data structure is in a spell-checker. A trie is a rooted tree T in which each node has somewhere between 0 and Σ children. All edges of T are assigned labels in Σ such that all the edges leading to the children of a particular node receive dierent labels. Strings are stored as root-to-leaf paths in the trie so that, if the null-terminated string s is stored in T, then there is a leaf v in T such that the sequence of edge labels encountered on the path from the root of T to v is precisely the string s, including the null terminator. An example is
5 CHAPTER 7. DATA STRUCTURES FOR STRINGS 47 a o p r e p g $ l a e n $ $ i s m $ Figure 7.2: A trie containing the strings \ape", \apple", \organ", and \organism". shown in Figure 7.2. Notice that it is important that the strings stored in a trie are null-terminated, so that no string is the prex of any other string. If this were not the case, it would be impossible to distinguish, for example, a trie that contained both \organism" and \organ" from a trie that contained just \organism". Implementation-wise, a trie node is represented as an array of pointers of size Σ, which point to the children of the node. In this way, the labelling of edges is implicit, since the ith element of the array can represent the edge with label i 1. When we create a new node, we initialize all of its Σ pointers to nil. Searching for the string s in a trie, T, is a simple operation. We examine each of the characters of s in turn and follow the appropriate pointers in the tree. If at any time we attempt to follow a pointer that is nil we conclude that s is not stored in T. Otherwise we reach a leaf v that represents s and we conclude that s is stored in T. Since the edges at each vertex are stored in an array and the individual characters of s are integers, we can follow each pointer in constant time. Thus, the cost of searching for s is O( s ). Insertion into a trie is not any more dicult. We simply the follow the search path for s, and any time we encounter a nil pointer we create a new node. Since a trie node has size O( Σ ), this insertion
6 CHAPTER 7. DATA STRUCTURES FOR STRINGS 48 ap organ e$ ple$ $ ism$ Figure 7.3: A Patricia tree containing the strings \ape", \apple", \organ", and \organism". procedure runs in O( s Σ ) time. Deletion from a trie is again very similar. We search for the leaf v that represents s. Once we have found it, we delete all nodes on the path from s to the root of T until we reach a node with more than 1 child. This algorithm is easily seen to run in O( s Σ ) time. If a trie holds a set of n strings, S, which have a total length of N then the total size of the trie is O(N Σ ). This follows from the fact that each character of each string results in the creation of at most 1 trie node. Theorem 19. Tries support insertion or deletion of a string s in O( s Σ ) time and searching for s in O( s ) time. If N is the total length of all strings stored in a trie then the storage used by the trie is O(N Σ ). 7.4 Patricia Trees A Patricia tree (a.k.a. a compressed trie) is a simple variant on a trie in which any path whose interior vertices all have only one child is compressed into a single edge. For this to make sense, we now label the edges with strings, so that the string corresponding to a leaf v is the concatenation of all the edge labels we encounter on the path from the root of T to v. An example is given in Figure 7.3. The edge labels of a Patricia tree are represented using the pointer/length representation for strings. As with tries, and for the same reason, it is important that the strings stored in a patricia tree are null-terminated. Implementation-wise, it makes sense to store the edge label of an edge uw directed from a parent u to it's child w in the node the w (since nodes can have many children, but at most one parent). See Figure 7.4 for an example. Searching for a string s in a Patricia tree is similar to searching in a trie, except that when the search traverses an edge it checks the edge label against a whole substring of s, not just a single character. If the substring matches, the edge is traversed. If there is a mismatch, the search fails without nding s. If the search uses up all the characters of s, then it succeeds by reaching a leaf corresponding to s. In any case, this takes O( s ) time. Descriptions of the insertion and deletion algorithms follow below. Figure 7.5 illustrates the
7 CHAPTER 7. DATA STRUCTURES FOR STRINGS 49 ap 2 organ 5 o r g a n i s m $ e$ ple$ $ ism$ a p e $ a p p l e $ o r g a n $ Figure 7.4: The edge labels of a Patricia tree use the pointer/length representation. Insert( organism ) Delete( orange ) orange$ or$ 2 organism$ ange$ ganism$ o r a n g e $ o r g a n i s m $ Figure 7.5: The evolution of a Patricia tree containing \orange$" as the string \organism$" is inserted and the string \orange$" is deleted. actions of these algorithms. In this gure, a Patricia tree that initially stores only the string \orange" has the string \organism" added to it and then has the string \orange" deleted from it. Inserting a string s into a Patricia tree is similar to searching right up until the point where the search gets stuck because s is not in the tree. If the search gets stuck in the middle of an edge, e, then e is split into two new edges joined by a new node, u, and the remainder of the string s becomes the edge label of the edge leading from u to a newly created leaf. If the search gets stuck at a node, u, then the remainder of s is used as an edge label for a new edge leading from u to a newly created leaf. Either case takes O( s + Σ ) time, since they each involve a search for s followed by the creation of at most two new nodes, each of size O( Σ ). Removing a string s from a Patricia tree is the opposite of insertion. We rst locate the leaf corresponding to s and remove it from the tree. If the parent, u, of this leaf is left with only one child, w, then we also remove u and replace it with a single edge, e, joining u's parent to w. The label for e is obtained in constant time by extending the edge label that was previously on the edge uw. How long
8 CHAPTER 7. DATA STRUCTURES FOR STRINGS 50 this takes depends on how long it takes to delete two nodes of size Σ. If we consider this deletion to be a constant time operation, then running time is O( s ). If we consider this deletion to take O(N) time, then the running time is O( s + N). An important dierence between Patricia trees and tries is that Patricia trees contain no nodes with only one child. Every node is either a leaf or has at least two children. This immediately implies that the number of internal (non-leaf) nodes does not exceed the number of leaves. Now, recall that each leaf corresponds to a string that is stored in the Patricia tree so if the Patricia tree stores n strings, the total storage used by nodes is O(n Σ ). Of course, this requires that we also store the strings separately at a cost of O(N). (As before, N is the total length of all strings stored in the Patricia tree.) Theorem 20. Patricia trees support insertion or deletion of any string s in O( s + Σ ) time and searching for s in O( s ) time. If N is the total length of all strings and n is the number of all strings stored in a Patricia tree then the storage used is O(n Σ + N). In addition to the operations described in the preceding theorem, Patricia trees also support prex matches; they can return a list of all strings that have some not-null-terminated string s as a prex. This is done by searching for s in the usual way until running out of characters in s. At this point, every leaf in the subtree that the search ended at corresponds to a string that starts with s. Since every internal node has at least two children, this subtree can be traversed in O(k) time, where k is the number of leaves in the subtree. If we are only interested in reporting one string that has s as a prex, we can look at the edge label of the last edge on the search path for s. This edge label is represented using the pointer/length representation and the pointer points to a longer string that has s as a prex (consider, for example, the edge labelled \ple$" in Figure 7.4, whose pointer points to the second `p' of \apple$"). This edge label can therefore be extended backwards to report the actual string that contains this label. Theorem 21. For a query string s, a Patricia tree can report one string that has s as a prex in O( s ) time and can report all strings that have s as a prex in O( s + k) time, where k is the number of strings that have s as a prex. 7.5 Suffix Trees Suppose we have a large body of text and we would like a data structure that allows us to query if particular strings occur in the text. Given a string t of length n, we can insert each of the n suxes of t into a Patricia tree. We call the resulting tree the sux tree for t. Now, if we want to know if some string s occurs in t we need only do a prex search for s in the Patricia tree. Thus, we can test if s occurs in t in O( s ) time. In the same amount of time, we can locate some occurrence of s in t and in O( s + k) time we can locate all occurrences of s in t, where k is the number of occurrences. What is the storage required by the sux tree for T? Since we only insert n suxes, the storage required by tree nodes is O(n Σ ). Furthermore, recall that the labels on edges of T are represented as pointers into the strings that were inserted into T. However, every string that is inserted into T is a sux of t, so all labels can be represented as pointers into a single copy of t, so the total spaced used to store t and all its edge labels is only O(n). Thus, the total storage used by a sux tree is O(n Σ ). The cost of constructing the sux tree for t can be split into two parts: The cost of creating
9 CHAPTER 7. DATA STRUCTURES FOR STRINGS 51 and initializing new nodes, which is clearly O(n Σ ) because there are only O(n) nodes; and the cost of following paths, which is clearly O(n 2 ). Theorem 22. The sux tree for a string t of length n can be constructed in O(n Σ + n 2 ) time and uses O(n Σ ) storage. The sux tree can be used to determine if any string s is a substring of t in O( s ) time. The sux tree can also report the locations of all occurrences of s in t in O(m + k) time, where k is the number of occurrences of s in t. The construction time in Theorem 22 is non-optimal. In particular, the O(n 2 ) term is unnecessary. In the next few section we will develop the tools needed to construct a sux tree in O(n Σ ) time. 7.6 Suffix Arrays The sux array A 1,..., A n of a string t = t 1,..., t n lists the suxes of t in lexicographically increasing order. That is, A i is the index such that t Ai,..., t n has rank i among all suxes of A. For example, consider the string t = \counterrevoluationary$": c o u n t e r r e v o l u t i o n a r y $ The sux array for t is A = h18, 1, 6, 9, 15, 12, 17, 4, 11, 16, 2, 8, 7, 19, 5, 14, 3, 13, 10, 20, 21i. This is hard to verify, so here is a table that helps: i A i t Ai,..., t n 1 18 s 1 = \ary$" 2 1 s 2 = \counterrevolutionary$" 3 6 s 3 = \errevolutionary$" 4 9 s 4 = \evolutionary$" 5 15 s 4 = \ionary$" 6 12 s 5 = \lutionary$" 7 17 s 7 = \nary$" 8 4 s 8 = \nterrevolutionary$" 9 11 s 9 = \olutionary$" s 10 = \onary$" 11 2 s 11 = \ounterrevolutionary$" 12 8 s 12 = \revolutionary$" 13 7 s 13 = \rrevolutionary$" s 14 = \ry$" 15 5 s 15 = \terrevolutionary$" s 16 = \tionary$" 17 3 s 17 = \unterrevolutionary$" s 18 = \utionary$" s 19 = \volutionary$" s 20 = \y$" s 21 = \$"
10 CHAPTER 7. DATA STRUCTURES FOR STRINGS 52 Given a sux-array A = A 1,..., A n for t and a not-null-terminated query string s one can do binary search in O( s log n) time to determine whether s occurs in t; binary search uses O(log n) comparison and each comparison takes O( s ) time Faster Searching with an l Matrix We can do searches a little faster in O( s + log n) time if, in addition to the sux array, we have a little more information. Let s i = t Ai, t Ai+1,..., t n. In other words, s i is the string in the ith row of the preceding table. In other other words the string s i is the ith sux of t when all suxes of t are sorted in lexicographic order. Suppose, that we have access to a table l, where, for any pair of indices (i, j) with 1 i j n, l i,j is the length of the longest common prex of s i and s j. In our running example, l 9,11 = 1, since s 9 = \olutionary$ 00 and s 11 = \ounterrevolutionary" have the rst character \o" in common but dier on their second character. Notice that this also implies that s 10 starts with the same letter as s 9 and s 11, otherwise s 10 would not be between s 9 and s 11 in sorted order. More generally, if l i,j = r, then the suxes s i, s i+1,..., s j all start with the same r characters. The value l i,j is called the longest common prex (LCP) of s i and s j since it is the length of the longest string s 0 that is a prex of both s i and s j. With the extra LCP information provided by l, binary search on the sux array can be sped up. The sped-up binary search routine maintains four integer values i, j, a and b. At all times, the search has deduced that a matching string if it is exists is among s i, s i+1,..., s j (because s i < s < s j ) and that the longest prexes of s i and s j that match s have length a and b respectively. The algorithm starts with (i = 1, j = n, a, b = 0) where the value of a is obtained by comparing s with s 1. Suppose, without loss of generality, that a b (the case where b > a is symmetric). Now, consider the entry l i,m which tells us how many characters of s m match s i. As an example, suppose we are searching for the string s = \programmer", and we have reached a state where s i = \programmable... $", s j = \protectionism", so a = 8 and b = 3.: s i = \programmable... $". s m = \pro... $". s j = \protectionism... $" Since s i and s j share the common prex \pro" of length min{a, b} = 3, we are certain that s m must also have \pro" as a prex. There are now three cases to consider: 1. If l i,m < a, then we can immediately conclude that s m > s. This is because s m > s i, so the
11 CHAPTER 7. DATA STRUCTURES FOR STRINGS 53 character at position l i,m + 1 in s m is greater than the corresponding character in s i and s. An example of this occurs when s m = \progress... $", so that l i,m = 5 and character at position 6 in s m (an `e') is greater than the character at position 6 in s i and s (an `a'). Therefore, our search can now be restricted to s i,..., s m. Furthermore, we know that the longest prex of s m that matches s has length b 0 = l i,m. Therefore, we can recursively search s i,..., s m using the values a 0 = a and b 0 = l i,m. That is, we recurse with the values (i, m, a, l i,m ) 2. If l i,m > a, then we can immediately conclude that s m < s, for the same reason that s i < s; namely s i and s dier in character a + 1 and this character is greater in s than it is in s i and s m. In this case, we recurse with the values (m, j, a, b). An example of this occurs when s m = \programmatically... $", so that l i,m = 9. In this case s i and s m both have a `a' at position a + 1 = 9 while s has an `e'. 3. If l i,m = a, then we can begin comparing s m and s starting at the (a + 1)th character position. After matching k 0 additional characters of s and s m this will eventually result in one of three possible outcomes: (a) If s < s m, then the search can recursive on the set s i,... s m using the values (i, m, a, a + k). An example of this occurs when s m = \programmes... $", so k = 1 and we recurse on (i, m, 8, 9). (b) If s > s m, then the search can recurse on the set s m,..., s j using the values (m, j, a+k, b). An example of this occurs when s m = \programmed... $", so k = 1 and we recurse on (m, j, 9, 3). (c) If all characters of s match the rst s characters of s m, then s m represents an occurrence of s in the text. An example of this occurs when s m = \programmers... $". The search can proceed in this manner, until the string is found at some s m or until j = i + 1. In the latter case, the algorithm concludes that s does not occur as a substring of t since s i < s < s i+1. To see that this search runs in O( s + log n) time, notice that each stage of the search reduces j i by roughly a factor of 2, so there are only O(log n) stages. Now, the time spent during a stage is proportional to k, the number of additional characters of s m that match s. Observe that, at the end of the phase max{a, b} is increased by at least k. Since a and b are indices into s, a s and b s. Therefore, the total sum of all k values during all phases is at most s. Thus, the total time spent searching for s is O( s + log n). In case the search is successful, it is even possible to nd all occurences of s in time proportional to the number of occurrences. This is done by the nding the maximal integers x and y such that l m x,m+y s. Finding x is easily done by trying x = 1, 2, 3,... until nding a value, x + 1, such that l m (x+1),m is less than s. Finding y is done in the same way. When this happens, all strings s m x,..., s m+y have s as a prex. Unfortunately, the assumption that we have an access to a longest common prex matrix l, is n unrealistic and impractical, since this matrix has 2 entries. Note, however, that we do not need to store l i,j for every value i, j 2 {1,..., n}. For example, when n is one more than a power of 2, then we only need to know l i,j for values in which i = 1 + q2 p and j = i + 2 p, with p 2 {0,...,blog nc} and q 2 {0,...,bn/2 p c}. This means that the longest common prex information stored in l consists of no more than blog nc i=0 n/2 i < 2n
12 CHAPTER 7. DATA STRUCTURES FOR STRINGS 54 values. In the next two sections we will show how the sux array and the longest common prex information can be computed eciently given the string t Constructing the Suffix Array in Linear Time Next, we show that a sux array can be constructed in linear time from the input string, t. The algorithm we present makes use of the radix-sort algorithm, which allows us to sort an array of n integers whose values are in the set {0,..., n c 1} in O(cn) time. In addition to being a sorting algorithm, we can also think of radix-sort as a compression algorithm. It can be used to convert a sequence, X, of n integers in the range {0,..., n c 1} into a sequence, Y, of n integers in the range {0,..., n 1}. The resulting sequence, Y, preserves the ordering of X, so that Y i < Y j if and only if X i < X j for all i, j 2 {1,..., n}. The sux-array construction algorithm, which is called the skew algorithm is recursive. It takes as input a string s whose length is n, which is terminated with two $ characters, and whose characters come from the alphabet {0,... n}. Let S denote the set of all suxes of t, and let S r, for r 2 {0, 1, 2} denote the set of suxes t i, t i+1,..., t n where i r (mod 3). That is, we partition the sets of suxes into three sets, each having roughly n/3 suxes in them. The outline of the algorithm is as follows: 1. Recursively sort the suxes in S 1 [ S Use radix-sort to sort the suxes in S Merge the two sorted sets resulting from steps 1 and 2 to obtain the sorted order of the suxes in S 0 [ S 1 [ S 2 = S. If the overall running time of the algorithm is denoted by T(n), then the rst step takes T(2n/3) time and we will show, shortly, that steps 2 and 3 each take O(n) time. Thus, the total running time of the algorithm is given by the recurrence T(n) cn + T(2n/3) cn (2/3) i 3cn. Next we describe how to implement each of the three steps eciently. i=0 Step 1. Assume n = 3k+1 for some integer k. If not, then append at most two additional $ characters to the end of t to make it so. To implement Step 1, we transform the string t into the sequence of triples: t 0 = (t 1, t 2, t 3 ), (t 4, t 5, t 6 ),..., (t n 3, t n 2, t n 1 ), (t } {{ } 2, t 3, t 4 ), (t 5, t 6, t 7 ),..., (t n 2, t n 1, t n ) } {{ } suxes in S 1 suxes in S 2 Observe that each sux in S 1 [ S 2 is represented somewhere in this sequence. That, is, for any t i, t i+1,..., t n with i 6 0 (mod 3), the sux (t i, t i+1, t i+2 ), (t i+3, t i+4, t i+5 ),..., (t i+3d(n i)/3e, t i+3d(n i)/3e+1, t i+3d(n i)/3e+2 )
13 CHAPTER 7. DATA STRUCTURES FOR STRINGS 55 appears in our transformed string. Therefore, if we can sort the suxes of the transformed string, we will have sorted all the suxes in S 1 [ S 2. The string t 0 contains about 2n/3 characters, as required, but each character is a triple of characters in the range (1,..., n), so we cannot immediately recurse on t 0. Instead, we rst apply radix sort to relabel each triple with an integer in the range 1,..., 2n/3. We can now recursively sort the relabelled transformed string which contains 2n/3 characters in the range 1,..., 2n/3 and undo the relabelling to obtain the sorted order of S 1 [ S 2. Aside from the recursive call, which takes T(2n/3) time, all of the sorting and relabelling takes only O(n) time. When Step 1 is done, we know, for each index i 6 0 (mod 3), the rank of the sux t i,..., t n in the set S 1 [ S 2. This means that for any pair of indices i, j 6 0 (mod 3), we can determine in constant time, by comparing ranks if the sux t i,..., t n comes before or after the sux t j,..., t n. Step 2. To implement Step 2, we observe that every sux in S 0 starts with a single character and is the followed by a sux in S 1. That is, each sux t i,..., t n with i 0 (mod 3) can be represented as a pair (t i, l) where l 2 {1,..., 2n/3) is the rank of the sux t i+1,..., t n obtained during Step 1. Applying radix sort to all of these pairs allows us to sort S 0 in O(n) time. Step 3. To implement Step 3, we have to merge two sorted lists, one of length 2n/3 and one of length n/3 in O(n) time. Merging two sorted lists using O(n) comparisons is straightforward. Therefore, the only trick here is to ensure that we can compare two elements one from the rst list and one from the second list in constant time. To see why this is possible, suppose we are comparing t i,..., t n 2 S 0 with t j,..., t n 2 S 1. Then we can write these as comparing t i, t i+1,..., t n } {{ } a sux in S 1 and t j, t j+1,..., t n. } {{ } a sux in S 2 Now this can certainly be done in constant time, by comparing t i and t j and, in case of a tie, comparing two suxes whose relative order was already determined in Step 1. Similarly, if we are comparing t i,..., t n 2 S 0 with t j,..., t n 2 S 2, then we can treat this as comparing t i, t i+1, t i+2,..., t n } {{ } a sux in S 2 and t j, t j+1, t j+2,..., t n. } {{ } a sux in S 1 This can also be done in constant time, by comparing at most two pairs of characters in t and, if necessary an sux in S 1 with a sux in S 2. The relative order of the suxes in S 1 and S 2 were determined in Step 1 of the algorithm. This completes the description of all the steps required to construct a sux array in O(n) time.
Learning Outcomes. COMP202 Complexity of Algorithms. Binary Search Trees and Other Search Trees
Learning Outcomes COMP202 Complexity of Algorithms Binary Search Trees and Other Search Trees [See relevant sections in chapters 2 and 3 in Goodrich and Tamassia.] At the conclusion of this set of lectureMore 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
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
Lecture 10 Union-Find The union-nd data structure is motivated by Kruskal's minimum spanning tree algorithm (Algorithm 2.6), in which we needed two operations on disjoint sets of vertices: determine whetherMore information
root node level: internal node edge leaf node CS@VT Data Structures & Algorithms 2000-2009 McQuain
inary Trees 1 A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root, which are disjoint from eachMore information
On line construction of suffix trees 1
(To appear in ALGORITHMICA) On line construction of suffix trees 1 Esko Ukkonen Department of Computer Science, University of Helsinki, P. O. Box 26 (Teollisuuskatu 23), FIN 00014 University of Helsinki,More 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
An Evaluation of Self-adjusting Binary Search Tree Techniques
SOFTWARE PRACTICE AND EXPERIENCE, VOL. 23(4), 369 382 (APRIL 1993) An Evaluation of Self-adjusting Binary Search Tree Techniques jim bell and gopal gupta Department of Computer Science, James Cook University,More 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
Persistent Data Structures
6.854 Advanced Algorithms Lecture 2: September 9, 2005 Scribes: Sommer Gentry, Eddie Kohler Lecturer: David Karger Persistent Data Structures 2.1 Introduction and motivation So far, we ve seen only ephemeralMore 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
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay
Information Theory and Coding Prof. S. N. Merchant Department of Electrical Engineering Indian Institute of Technology, Bombay Lecture - 17 Shannon-Fano-Elias Coding and Introduction to Arithmetic CodingMore 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
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
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
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
1 2-3 Trees: The Basics
CS10: Data Structures and Object-Oriented Design (Fall 2013) November 1, 2013: 2-3 Trees: Inserting and Deleting Scribes: CS 10 Teaching Team Lecture Summary In this class, we investigated 2-3 Trees inMore information
Fast Sequential Summation Algorithms Using Augmented Data Structures
Fast Sequential Summation Algorithms Using Augmented Data Structures Vadim Stadnik email@example.com Abstract This paper provides an introduction to the design of augmented data structures that offerMore 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
Binary Trees and Huffman Encoding Binary Search Trees
Binary Trees and Huffman Encoding Binary Search Trees Computer Science E119 Harvard Extension School Fall 2012 David G. Sullivan, Ph.D. Motivation: Maintaining a Sorted Collection of Data A data dictionaryMore information
Complexity of Union-Split-Find Problems. Katherine Jane Lai
Complexity of Union-Split-Find Problems by Katherine Jane Lai S.B., Electrical Engineering and Computer Science, MIT, 2007 S.B., Mathematics, MIT, 2007 Submitted to the Department of Electrical EngineeringMore information
CS711008Z Algorithm Design and Analysis
CS711008Z Algorithm Design and Analysis Lecture 7 Binary heap, binomial heap, and Fibonacci heap 1 Dongbo Bu Institute of Computing Technology Chinese Academy of Sciences, Beijing, China 1 The slides wereMore 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
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
S I N S UN I ER E P S I T VER M A TA S CONSTRUCTING A BINARY TREE EFFICIENTLYFROM ITS TRAVERSALS DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF TAMPERE REPORT A-1998-5 UNIVERSITY OF TAMPERE DEPARTMENT OFMore 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
Analysis of Algorithms, I
Analysis of Algorithms, I CSOR W4231.002 Eleni Drinea Computer Science Department Columbia University Thursday, February 26, 2015 Outline 1 Recap 2 Representing graphs 3 Breadth-first search (BFS) 4 ApplicationsMore information
The Goldberg Rao Algorithm for the Maximum Flow Problem
The Goldberg Rao Algorithm for the Maximum Flow Problem COS 528 class notes October 18, 2006 Scribe: Dávid Papp Main idea: use of the blocking flow paradigm to achieve essentially O(min{m 2/3, n 1/2 }More information
Position-Restricted Substring Searching
Position-Restricted Substring Searching Veli Mäkinen 1 and Gonzalo Navarro 2 1 AG Genominformatik, Technische Fakultät Universität Bielefeld, Germany. email@example.com 2 Center for Web ResearchMore information
Managing large sound databases using Mpeg7
Max Jacob 1 1 Institut de Recherche et Coordination Acoustique/Musique (IRCAM), place Igor Stravinsky 1, 75003, Paris, France Correspondence should be addressed to Max Jacob (firstname.lastname@example.com) ABSTRACTMore information
Graphs without proper subgraphs of minimum degree 3 and short cycles
Graphs without proper subgraphs of minimum degree 3 and short cycles Lothar Narins, Alexey Pokrovskiy, Tibor Szabó Department of Mathematics, Freie Universität, Berlin, Germany. August 22, 2014 AbstractMore 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 email@example.com September 12,More 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
International Journal of Advanced Research in Computer Science and Software Engineering
Volume 3, Issue 7, July 23 ISSN: 2277 28X International Journal of Advanced Research in Computer Science and Software Engineering Research Paper Available online at: www.ijarcsse.com Greedy Algorithm:More information
Rotation Operation for Binary Search Trees Idea:
Rotation Operation for Binary Search Trees Idea: Change a few pointers at a particular place in the tree so that one subtree becomes less deep in exchange for another one becoming deeper. A sequence ofMore information
2. Compressing data to reduce the amount of transmitted data (e.g., to save money).
Presentation Layer The presentation layer is concerned with preserving the meaning of information sent across a network. The presentation layer may represent (encode) the data in various ways (e.g., dataMore information
Lempel-Ziv Factorization: LZ77 without Window
Lempel-Ziv Factorization: LZ77 without Window Enno Ohlebusch May 13, 2016 1 Sux arrays To construct the sux array of a string S boils down to sorting all suxes of S in lexicographic order (also known asMore information
Physical Data Organization
Physical Data Organization Database design using logical model of the database - appropriate level for users to focus on - user independence from implementation details Performance - other major factorMore information
Network (Tree) Topology Inference Based on Prüfer Sequence
Network (Tree) Topology Inference Based on Prüfer Sequence C. Vanniarajan and Kamala Krithivasan Department of Computer Science and Engineering Indian Institute of Technology Madras Chennai 600036 email@example.com,More information
Algorithms and Data Structures
Algorithms and Data Structures Part 2: Data Structures PD Dr. rer. nat. habil. Ralf-Peter Mundani Computation in Engineering (CiE) Summer Term 2016 Overview general linked lists stacks queues trees 2 2More information
Previous Lectures. B-Trees. External storage. Two types of memory. B-trees. Main principles
B-Trees Algorithms and data structures for external memory as opposed to the main memory B-Trees Previous Lectures Height balanced binary search trees: AVL trees, red-black trees. Multiway search trees:More 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
Space-Efficient Finger Search on Degree-Balanced Search Trees
Space-Efficient Finger Search on Degree-Balanced Search Trees Guy E. Blelloch Bruce M. Maggs Shan Leung Maverick Woo Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 113 {guyb,bmm,email@example.com information
From Last Time: Remove (Delete) Operation
CSE 32 Lecture : More on Search Trees Today s Topics: Lazy Operations Run Time Analysis of Binary Search Tree Operations Balanced Search Trees AVL Trees and Rotations Covered in Chapter of the text FromMore information
Structure for String Keys
Burst Tries: A Fast, Efficient Data Structure for String Keys Steen Heinz Justin Zobel Hugh E. Williams School of Computer Science and Information Technology, RMIT University Presented by Margot SchipsMore information
In this paper we consider answering d-queries eciently without limiting ourselves to the construction of a new data structure parametrized by d. The v
Dictionary Look-Up Within Small Edit Distance Abdullah N. Arslan and Omer Egecioglu? Department of Computer Science University of California, Santa Barbara Santa Barbara, CA 936 USA farslan,firstname.lastname@example.com information
S. Muthusundari. Research Scholar, Dept of CSE, Sathyabama University Chennai, India e-mail: email@example.com. Dr. R. M.
A Sorting based Algorithm for the Construction of Balanced Search Tree Automatically for smaller elements and with minimum of one Rotation for Greater Elements from BST S. Muthusundari Research Scholar,More information
A simple algorithm with no simple verication
A simple algorithm with no simple verication Laszlo Csirmaz Central European University Abstract The correctness of a simple sorting algorithm is resented, which algorithm is \evidently wrong" at the rstMore information
D1.1 Service Discovery system: Load balancing mechanisms
D1.1 Service Discovery system: Load balancing mechanisms VERSION 1.0 DATE 2011 EDITORIAL MANAGER Eddy Caron AUTHORS STAFF Eddy Caron, Cédric Tedeschi Copyright ANR SPADES. 08-ANR-SEGI-025. Contents IntroductionMore information
Binary Heaps * * * * * * * / / \ / \ / \ / \ / \ * * * * * * * * * * * / / \ / \ / / \ / \ * * * * * * * * * *
Binary Heaps A binary heap is another data structure. It implements a priority queue. Priority Queue has the following operations: isempty add (with priority) remove (highest priority) peek (at highestMore information
Topology-based network security
Topology-based network security Tiit Pikma Supervised by Vitaly Skachek Research Seminar in Cryptography University of Tartu, Spring 2013 1 Introduction In both wired and wireless networks, there is theMore information
GRAPH THEORY LECTURE 4: TREES Abstract. 3.1 presents some standard characterizations and properties of trees. 3.2 presents several different types of trees. 3.7 develops a counting method based on a bijectionMore information
MLR Institute of Technology
MLR Institute of Technology DUNDIGAL 500 043, HYDERABAD COMPUTER SCIENCE AND ENGINEERING Computer Programming Lab List of Experiments S.No. Program Category List of Programs 1 Operators a) Write a C programMore information
Binary Search Trees > = Binary Search Trees 1. 2004 Goodrich, Tamassia
Binary Search Trees < 6 2 > = 1 4 8 9 Binary Search Trees 1 Binary Search Trees A binary search tree is a binary tree storing keyvalue entries at its internal nodes and satisfying the following property:More information
A binary heap is a complete binary tree, where each node has a higher priority than its children. This is called heap-order property
CmSc 250 Intro to Algorithms Chapter 6. Transform and Conquer Binary Heaps 1. Definition A binary heap is a complete binary tree, where each node has a higher priority than its children. This is calledMore information
Computational Geometry. Lecture 1: Introduction and Convex Hulls
Lecture 1: Introduction and convex hulls 1 Geometry: points, lines,... Plane (two-dimensional), R 2 Space (three-dimensional), R 3 Space (higher-dimensional), R d A point in the plane, 3-dimensional space,More 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
MATHEMATICAL ENGINEERING TECHNICAL REPORTS. The Best-fit Heuristic for the Rectangular Strip Packing Problem: An Efficient Implementation
MATHEMATICAL ENGINEERING TECHNICAL REPORTS The Best-fit Heuristic for the Rectangular Strip Packing Problem: An Efficient Implementation Shinji IMAHORI, Mutsunori YAGIURA METR 2007 53 September 2007 DEPARTMENTMore 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
Lecture 10: Regression Trees
Lecture 10: Regression Trees 36-350: Data Mining October 11, 2006 Reading: Textbook, sections 5.2 and 10.5. The next three lectures are going to be about a particular kind of nonlinear predictive model,More 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
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
Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time
Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time Gerth Stølting Brodal 1, Alexis C. Kaporis 2, Spyros Sioutas 3, Konstantinos Tsakalidis 1, Kostas Tsichlas 4 1 MADALGO, DepartmentMore 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
A Lower Bound for Area{Universal Graphs. K. Mehlhorn { Abstract. We establish a lower bound on the eciency of area{universal circuits.
A Lower Bound for Area{Universal Graphs Gianfranco Bilardi y Shiva Chaudhuri z Devdatt Dubhashi x K. Mehlhorn { Abstract We establish a lower bound on the eciency of area{universal circuits. The area AMore information
Ecient approximation algorithm for minimizing makespan. on uniformly related machines. Chandra Chekuri. November 25, 1997.
Ecient approximation algorithm for minimizing makespan on uniformly related machines Chandra Chekuri November 25, 1997 Abstract We obtain a new ecient approximation algorithm for scheduling precedenceMore information
A binary search tree is a binary tree with a special property called the BST-property, which is given as follows:
Chapter 12: Binary Search Trees A binary search tree is a binary tree with a special property called the BST-property, which is given as follows: For all nodes x and y, if y belongs to the left subtreeMore information
CS 2112 Spring 2014. 0 Instructions. Assignment 3 Data Structures and Web Filtering. 0.1 Grading. 0.2 Partners. 0.3 Restrictions
CS 2112 Spring 2014 Assignment 3 Data Structures and Web Filtering Due: March 4, 2014 11:59 PM Implementing spam blacklists and web filters requires matching candidate domain names and URLs very rapidlyMore 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 email@example.com 2005 2009 Glenn G. ChappellMore information
A Dynamic Programming Approach for Generating N-ary Reflected Gray Code List
A Dynamic Programming Approach for Generating N-ary Reflected Gray Code List Mehmet Kurt 1, Can Atilgan 2, Murat Ersen Berberler 3 1 Izmir University, Department of Mathematics and Computer Science, IzmirMore information
Longest Common Extensions via Fingerprinting
Longest Common Extensions via Fingerprinting Philip Bille, Inge Li Gørtz, and Jesper Kristensen Technical University of Denmark, DTU Informatics, Copenhagen, Denmark Abstract. The longest common extensionMore information
Lecture 2 February 12, 2003
6.897: Advanced Data Structures Spring 003 Prof. Erik Demaine Lecture February, 003 Scribe: Jeff Lindy Overview In the last lecture we considered the successor problem for a bounded universe of size u.More information
Algorithms Chapter 12 Binary Search Trees
Algorithms Chapter 1 Binary Search Trees Outline Assistant Professor: Ching Chi Lin 林 清 池 助 理 教 授 firstname.lastname@example.com Department of Computer Science and Engineering National Taiwan Ocean UniversityMore information
Merkle Hash Trees for Distributed Audit Logs
Merkle Hash Trees for Distributed Audit Logs Subject proposed by Karthikeyan Bhargavan email@example.com April 7, 2015 Modern distributed systems spread their databases across a large numberMore information
Lecture 4 Online and streaming algorithms for clustering
CSE 291: Geometric algorithms Spring 2013 Lecture 4 Online and streaming algorithms for clustering 4.1 On-line k-clustering To the extent that clustering takes place in the brain, it happens in an on-lineMore information
Persistent Data Structures and Planar Point Location
Persistent Data Structures and Planar Point Location Inge Li Gørtz Persistent Data Structures Ephemeral Partial persistence Full persistence Confluent persistence V1 V1 V1 V1 V2 q ue V2 V2 V5 V2 V4 V4More information
Homework Exam 1, Geometric Algorithms, 2016
Homework Exam 1, Geometric Algorithms, 2016 1. (3 points) Let P be a convex polyhedron in 3-dimensional space. The boundary of P is represented as a DCEL, storing the incidence relationships between theMore 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
Data storage Tree indexes
Data storage Tree indexes Rasmus Pagh February 7 lecture 1 Access paths For many database queries and updates, only a small fraction of the data needs to be accessed. Extreme examples are looking or updatingMore information
Chapter 4 Multi-Stage Interconnection Networks The general concept of the multi-stage interconnection network, together with its routing properties, have been used in the preceding chapter to describeMore information
Binary Search Trees 3/20/14
Binary Search Trees 3/0/4 Presentation for use ith the textbook Data Structures and Algorithms in Java, th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldasser, Wiley, 04 Binary Search Trees 4More 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
Offline sorting buffers on Line
Offline sorting buffers on Line Rohit Khandekar 1 and Vinayaka Pandit 2 1 University of Waterloo, ON, Canada. email: firstname.lastname@example.com 2 IBM India Research Lab, New Delhi. email: firstname.lastname@example.com information
Binary Search Trees. Data in each node. Larger than the data in its left child Smaller than the data in its right child
Binary Search Trees Data in each node Larger than the data in its left child Smaller than the data in its right child FIGURE 11-6 Arbitrary binary tree FIGURE 11-7 Binary search tree Data Structures UsingMore information
Efficient Multi-Feature Index Structures for Music Data Retrieval
header for SPIE use Efficient Multi-Feature Index Structures for Music Data Retrieval Wegin Lee and Arbee L.P. Chen 1 Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300,More information
2.3 Scheduling jobs on identical parallel machines
2.3 Scheduling jobs on identical parallel machines There are jobs to be processed, and there are identical machines (running in parallel) to which each job may be assigned Each job = 1,,, must be processedMore information
COUNTING INDEPENDENT SETS IN SOME CLASSES OF (ALMOST) REGULAR GRAPHS Alexander Burstein Department of Mathematics Howard University Washington, DC 259, USA firstname.lastname@example.com Sergey Kitaev MathematicsMore 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
DATA ANALYSIS II. Matrix Algorithms
DATA ANALYSIS II Matrix Algorithms Similarity Matrix Given a dataset D = {x i }, i=1,..,n consisting of n points in R d, let A denote the n n symmetric similarity matrix between the points, given as whereMore information
A Catalogue of the Steiner Triple Systems of Order 19
A Catalogue of the Steiner Triple Systems of Order 19 Petteri Kaski 1, Patric R. J. Östergård 2, Olli Pottonen 2, and Lasse Kiviluoto 3 1 Helsinki Institute for Information Technology HIIT University ofMore information
CSE 326, Data Structures. Sample Final Exam. Problem Max Points Score 1 14 (2x7) 2 18 (3x6) 3 4 4 7 5 9 6 16 7 8 8 4 9 8 10 4 Total 92.
Name: Email ID: CSE 326, Data Structures Section: Sample Final Exam Instructions: The exam is closed book, closed notes. Unless otherwise stated, N denotes the number of elements in the data structureMore information
AS-2261 M.Sc.(First Semester) Examination-2013 Paper -fourth Subject-Data structure with algorithm
AS-2261 M.Sc.(First Semester) Examination-2013 Paper -fourth Subject-Data structure with algorithm Time: Three Hours] [Maximum Marks: 60 Note Attempts all the questions. All carry equal marks Section AMore information
External Memory Geometric Data Structures
External Memory Geometric Data Structures Lars Arge Department of Computer Science University of Aarhus and Duke University Augues 24, 2005 1 Introduction Many modern applications store and process datasetsMore information
CSC2420 Fall 2012: Algorithm Design, Analysis and Theory
CSC2420 Fall 2012: Algorithm Design, Analysis and Theory Allan Borodin November 15, 2012; Lecture 10 1 / 27 Randomized online bipartite matching and the adwords problem. We briefly return to online algorithmsMore information
Lecture 3: Finding integer solutions to systems of linear equations
Lecture 3: Finding integer solutions to systems of linear equations Algorithmic Number Theory (Fall 2014) Rutgers University Swastik Kopparty Scribe: Abhishek Bhrushundi 1 Overview The goal of this lectureMore information
Notes on Factoring. MA 206 Kurt Bryan
The General Approach Notes on Factoring MA 26 Kurt Bryan Suppose I hand you n, a 2 digit integer and tell you that n is composite, with smallest prime factor around 5 digits. Finding a nontrivial factorMore information
8.1 Min Degree Spanning Tree
CS880: Approximations Algorithms Scribe: Siddharth Barman Lecturer: Shuchi Chawla Topic: Min Degree Spanning Tree Date: 02/15/07 In this lecture we give a local search based algorithm for the Min DegreeMore information
Binary Coded Web Access Pattern Tree in Education Domain
Binary Coded Web Access Pattern Tree in Education Domain C. Gomathi P.G. Department of Computer Science Kongu Arts and Science College Erode-638-107, Tamil Nadu, India E-mail: firstname.lastname@example.com M. MoorthiMore information
Information, Entropy, and Coding
Chapter 8 Information, Entropy, and Coding 8. The Need for Data Compression To motivate the material in this chapter, we first consider various data sources and some estimates for the amount of data associatedMore information
B-Trees. Algorithms and data structures for external memory as opposed to the main memory B-Trees. B -trees
B-Trees Algorithms and data structures for external memory as opposed to the main memory B-Trees Previous Lectures Height balanced binary search trees: AVL trees, red-black trees. Multiway search trees:More information


text:
4 acres in Carroll County, New Hampshire
ADJACENT TO SETTLERS GREEN, North Conway's premier retail mall, ideal retail and restaurant site.
Undeveloped parcel bounded by the North-South Road, Common Court and the Old Navy store site.
Tax Data (Show Tax Data)
Loading Tax Data
Contact Seller
Fill out this form to contact Seller about this property
Bayard Kennett
RE/MAX Presidential/North Conway
3280 White Mountain Highway
North Conway, NH 03860
Other Land for Sale in Carroll County
- Properties for Sale in Nearby Counties
- Belknap County Land for Sale
- Coos County Land for Sale
- Grafton County Land for Sale
- Oxford County Land for Sale
- Strafford County Land for Sale
- York County Land for Sale
NOTE: The information contained herein is provided as general information only and has been obtained from sources deemed reliable. It is provided without any guaranty, warranty or representation, expressed or implied, made by Lands of America, or any related entity, as to the accuracy or completeness of the information. The information is presented subject to errors, omissions, change of price or conditions, prior sale or withdrawal without notice. Prospective purchasers should make their own investigations, projections and conclusions concerning the information.

subset: commoncrawl


text:
Fiji Mission President TC winston Appeal
Fiji has just experienced one of the worst cyclones in its history. Right now we are still in shock as we reflect upon what Winston has done to our nation.
Peace I leave with you, my peace I give unto you: not as the world giveth, give I unto you. Let not your heart be troubled, neither let it be afraid. John 14:27″We are as helpless here as were the disciples to quiet the raging storm. But He who spoke peace to the billows of Galilee, has spoken the word of peace for every soul. However fierce the tempest, those who turn to Jesus with the cry, "Lord, save us," will find deliverance."The Signs of the Times, December 27, 1905.ACCOUNT NAME: FIJI MISSION OF SEVENTH-DAY ADVENTISTSACCOUNT NUMBER: 09136900BANK NAME: WESTPACSWIFT CODE: WPACFJFXNARRATION: TC WINSTON AIDCONTACT PERSONS:JOE TALEMAITOGA VIC BONETTICONTACT NUMBERS:+679 3361022 +679 9246000EMAIL:email@example.com firstname.lastname@example.com
Posted by My Mission – Fiji Mission of Seventh-day Adventists on Wednesday, 24 February 2016
Suva, Fiji
A number of Adventist churches and schools have been damaged in Fiji, as news begins to trickle in regarding the devastation wrought by Cyclone Winston.
The video above, released by the Fiji Mission, shows flattened churches and school buildings missing rooves.
The video shows Navesau Adventist Secondary School, Peni Tavodi Memorial church, Naqia Adventist church, Navolau church and Lewa Adventist Primary School—all either destroyed or with extensive water damage.
"Fiji has just experienced one of the worst cyclones in its history," said Pastor Luke Narabe, president of the Adventist Church in Fiji. "Right now we are still in shock as we reflect upon what Winston has done to our nation."
Pastor Narabe asks for members around the world to help in whatever way they can and to pray for the people of Fiji.
He adds that disasters like this are signs of Christ's soon return and that they provide the Church with an opportunity to "unite and share our message of hope."
According to Adventist Media: Vanuatu, the Adventist Church in Vanuatu is asking all its churches to support a special offering on March 26 for Fiji. Vanuatu itself is still recovering from Cyclone Pam, which destroyed 53 churches around 12 months ago.
The Adventist Development and Relief Agency (ADRA) is already on the ground and beginning to assist those hit hardest by the cyclone. "Getting food to families is the most urgent need at the moment," said Iliapi Tuwai, country director for ADRA Fiji. "With gardens and farms destroyed there is little for people to eat. Children are hungry and disease is starting to grow."
The food packs distributed by ADRA in the north of Viti Levu, the main island of Fiji, will contain essential items, including rice, tuna, sugar and high-energy biscuits. The packs are designed to provide enough supplementary nutrition for a family of five for a week.
"These food packs will ensure families can survive until more aid can be provided."
According to Mr Tuwai this is just the beginning of ADRA's response. "We are already planning to provide emergency shelter and access to safe water and hygiene materials. This is not a disaster that people recover from quickly. We've also begun plans for recovery projects that will help people re-establish their homes and livelihoods."
A team of experts from the global ADRA network have been flown to assist in response to the Category 5 storm. The Emergency Response team includes ADRA staff from their office in Fiji plus experts from Australia, New Zealand and Germany.
To contact the Fiji Mission directly, email firstname.lastname@example.com or email@example.com.
For updates from ADRA, visit https://www.adra.org.au/.


text:
DISCREET BILLING & PACKAGING, WORLDWIDE SHIPPING - 100% Satisfaction
Years of research have led to this breakthrough for your bedroom, Masque is a paper-thin, gel strip that dissolves on your tongue and completely disguises the taste of semen during oral sex for up to fifteen amazing minutes. Well work our magic, while you work yours.
Instructions - Allow strip to dissolve completely on your tongue immediately prior to our during the act of fellatio.
Available in Strawberry, Chocolate, Watermelon and Mango.
Need help with size/fitting? We have a beautiful size guide specially designed for you to identify your size and place the most accurate order. For Bra sizing (click here) For Lingerie fitting & style (click here) For all legwear (click here). We are also able to advise if you have questions about size and fitting.
If you are not completely satisfied with this product, simply let us know within 15days of receipt of the product by submitting a return request Request Return. We will issue an RMA# and arrange for our delivery team to get it picked up. Depending on the reason for return (color/size changes or defective product etc) and your instructions, we will process the exchange/return/refund within 48hrs of receipts of the authorized returns. Note: Some products cannot be returned for hygienic reasons, pls (click here) for detailed return policy.
We ship your order from our distribution center in US. It generaly takes about 10-14days for them to arrive after clearing customs. (click here) to see how it works. We take care of customs & duty and all taxes as the price is all inclusive. You just have to pay a very low charge for express air shipping, which is charged by FEDEX/UPS at a heavily discounted rate. Shipping is FREE on orders over Rs10,000.
Click our Pin Code Checker to see if your Pin Code is servicable.


text:
New to Five Star Alliance: Hotel B Lima
Originally built in the style of the Belle Epoque, the mansion that is the Hotel B Lima served as a seaside retreat during the presidency of Augusto Leguia in the 1920's. Its architectural features and flair capture the celebratory spirit of Peru's centennial, which permeated life in the capital city throughout the era of its construction. Famed French architect Claude Sahut, lauded for his work remodeling portions of the Government Palace, along with many of Lima's main avenues, parks, theaters, and other public buildings and spaces, was originally commissioned to design the property as a summer retreat for the Garcia Bedoya family.
View rates, details, and more images of Hotel B Lima >>
Country Club Lima Hotel
Lima, Peru
This architectural treasure in the exclusive neighborhood of San Isidro is acclaimed as one of the finest hotels in Lima, Peru. Built In 1927 And Completely Refurbished In 1998 Its Public Spaces Feature Original Colonial Artwork... more >>
Belmond Miraflores Park Hotel
Lima, Peru
Set in one of Lima's most fashionable areas, the Belmond Miraflores Park takes you straight to the heart of all that's best about this great capital city. Renowned for its beautiful garden location beside the Pacific Ocean, it... more >>
Hotel Paracas
Paracas, Peru
Hotel Paracas is a beachside resort located adjacent to the Paracas Natural Reserve.Set sail to the Ballesta Islands for a close encounter with the Peru's wildlife, or charter a flight over the mysterious and alluring Pre-Incan... more >>
With its stylish contemporary design, cutting-edge technology and ideal location, the flagship Casa Andina Private Collection - Miraflores hotel is the top of its class in every aspect. Once the Miraflores Cesar's, Lima's... more >>
Delfines Hotel And Casino
Lima, Peru
Discover the striking surroundings and legendary service waiting at Delfines Hotel & Casino – an enchanting Lima luxury hotel centrally located in San Isidro. Enjoy fine dining at our gourmet restaurant. Test your luck at the... more >>


text:
— Martian ManHunter in Justice: Apocalypse
"I have failed you all..."
Martian ManHunter is a fictional DC character who came from the planet, Mars, as Jonn J'onzz.
Justice: Apocalypse
After shamefully watching the genocide of so many human lives, Jonn was overwhelmed with guilt and wandered the Earth with the burden upon him. Luckily, when he heard of the time portal, he immediately sprang into action.


text:
No photo has been submitted for the contest. Be the first!
- Upload Clear Picture of Your Kid
- Mention Full Name of Kid in Title
- Age of Kid Must be Between 0-10 years only
- Phone Number must be mentioned to claim prize
- Top 3 pictures with maximum number of votes will be declared as winner.
- Winners will be rewarded with Gift Coupons/Cards.
- By uploading picture you authorize us to use this picture on our website and / or social media and also acknowledge that you have got necessary permissions to upload this picture.


text:
Laura Bailey is an American voice actress who voiced Christie Monteiro in Tekken 6.
Other Roles
- She is also known as the current English voice actor of Chun-Li from the Street Fighter series, and the current English voice of Blaze the Cat in the Sonic the Hedgehog series, whereupon her husband Travis voices Knuckles..
- She voiced Dahlia Mason in Silent Hill: Shattered Memories, Angela Orosco and Claudia Wolf in the Silent Hill HD Collection, and various voices in Silent Hill: Book of Memories.
- She also voiced Christie in Dead or Alive 5/Ultimate.
- Laura began her collegiate studies at the acclaimed Quad C Theatre program at Collin County Community College in Plano, Texas.
- Her favorite anime is Fruits Basket (2001) and it was also her favorite voice acting role.
- Laura married her long-time boyfriend actor Travis Willingham on September 25, 2011.
External Links
- Official website
- Her page on the Silent Hill wiki.
- Her page on the Dead or Alive wiki.


text:
EENI- School of International Business
Sub-subject: Jyoti Group (Nepalese Businessman). Syllabus:
Sample of the Sub-subject: Jyoti Group (Nepal)
Description of the Sub-Subject: The Jyoti Group (Nepal).
"To make elders proud, be respectful, satisfied, grateful and to listen to the words of Dhamma in time that are the highest welfare."
The Jyoti Group belongs to the economic area of the Hindu Civilisation and the Buddhist Civilisation
Religions and International Business


text:
Grimoire of the Apprentice is an Act 1 side quest in Dragon Age II.
Acquisition Edit
The quest is obtained by finding the Grimoire in the Sanctuary during the quest Enemies Among Us. It is located in a sack near the exit, past Keran.
Walkthrough Edit
Take the Grimoire to Bonwald in Lowtown, in the bazaar.
Rewards Edit
- 50


text:
Ike Andy
- Gravitogorsk Mars -Red Wood Poster zazzle.co.uk/z/yz5ni?rf=238… via @zazzle 1 month ago
- Gravitogorsk Mars - The Mad Dogs T-Shirt zazzle.co.uk/z/yz5o5?rf=238… via @zazzle 1 month ago
- Thermostellar _ Dark Star T-Shirt zazzle.co.uk/z/yzsui?rf=238… via @zazzle 1 month ago
- RT @Independent: Tory 'strong and stable' advertising van overturns in the wind ind.pn/2qYMwe4 1 month ago
- warringtonguardian.co.uk/resources/imag… tory ad van attempts u turn on motorway - an omen for thursday 1 month ago
Zazzle Store
Browse other gifts from Zazzle.
Tag Archives: Dark Side of the Moon
Terra Fide
Where does it come from? The inspiration, the design decisions, the choices that we make? All that you touch All that you see All that you taste All you feel. All that you love All that you hate All you … Continue reading
Posted in Creative, Design Tagged Celtic, China, Christianity, Color, Dark Side of the Moon, Design, Floyd, Halloween, marketing, Pink Floyd, Spreadshirt, Syd Barrett, T-shirt 2 Comments


text:
Cupid's Waterfall and Chapel Weddings
A quaint White Wood Chapel with hardwood floors and gothic windows conveniently located in the city of Gatlinburg, TN. We are in the heart of the Smoky Mountains up on the Great Smoky National Park. Cupid's is known for its affordable and fun weddings. You can get all dressed up in a formal gown and Tuxedo, or you can be dressed as casually as you like. It's your day, you decide. Depending on the number of guests you are having, we offer ceremonies in the Chapel's sanctuary or in front of our waterfall. Our Photographers will take your portraits by the small waterfall as well in our white gazebo. There are many places on the grounds that will make beautiful backdrops for your wedding memories. Keep it simple and stress free. Our wedding coordinators can assist you in every detail of the planning. Elopement and Simple Gatlinburg Weddings, Cheap Gatlinburg Wedding Packages, Intimate Gatlinburg Weddings. We do it all at Cupid's Waterfall and Chapel Weddings, even vow renewal ceremonies. Located near the Great Smoky National Park, Dollywood, Pigeon Forge, the Titanic Museum, Ripley's Aquarium and much, much more
Weddings at Cupid's
Cupid's Waterfall and Chapel Weddings:
If you are looking for wonderful memories but also want to stay within a budget, Cupid's Waterfall & Chapel Weddings is the place for your wedding. There are two dressing rooms for the couple to change, A large white Gazebo (perfect for elopement weddings or groups up to 6), Two waterfall areas (one that accommodates up to 6 guests and another with seating for 15-20 guests) , gothic glass windows and padded pews.
We perform wedding ceremonies and vow renewal ceremonies 7 days a week, Monday through Sunday. Based on the availability of our ministers and staff.
Just some thoughts that we have during this time: Every city has its landmarks and places that everyone who visits wants to see. Cupid's Chapel of Love was one of those places in Gatlinburg. With time, the decision to rebuild this iconic little chapel will occur.
In the meanwhile, Cupid's new home is located at 1844 East Parkway, just 4 miles up the road. More photos will be added to our website as soon as we can.
Our new home is located close to the Smoky Mountains National Park. We'll still offer the FUN & AFFORDABLE Packages that have come to be associated with Cupid's. AND, with the new waterfall installation, we'll still have intimate outdoor weddings in a rustic, lovely setting. The Chapel will offer candlelight ceremonies, professional photographers and videographers, this simple chapel offers the amenities of the more expensive chapels at a fraction of the cost. Availability varies by day of the week and season.
Click here for TN MARRIAGE LICENSE information. (www.SevierCountyTN.org)
Packages for Every Couple (and every budget)
Cupid's Waterfall and Chapel Weddings is known for its affordable, fun weddings. With a new large waterfall, you can have your wedding ceremony in front of the waterfall or in the chapel's sanctuary. There is a small waterfall as well, a rustic fence setting, a gazebo and an arbor to ensure there are plenty of portrait backdrops for your wedding memories. You can be dressed in formal wear or 'come as you are'. Wear want you are most comfortable in for your ceremony.
Other Information
To reserve your wedding, we will need to process a deposit to secure your date and time. The Deposit for our 1 hour weddings is 25% of the total wedding cost ($100 minimum) with final payment due 1 month prior to your wedding.
The Deposit for our 30 minute weddings (or less) is 50% of the total wedding cost with final payment due 14 days prior to your wedding. There is a $100 minimum deposit required.
Cupid's Waterfall and Chapel Weddings (formerly Cupid's Chapel of Love)
Gatlinburg Wedding Chapel in the Smoky Mountains
We don't do Cheap Gatlinburg Weddings but Simple, Intimate Gatlinburg Weddings
Chapel Address:1844 Parkway, Gatlinburg TN 37738
Sales Office: 1844 East Parkway, Gatlinburg,TN 37738 (at Chapel at the Park)
Mailing Address: PO Box 211, Gatlinburg, TN 37738
800-693-6479 | 865-430-3372


text:
February 17, 2010 BY John Kim
A few weeks ago, Baron Davis dribbled his way through the busy streets of New York City. If you thought NYC was busy, how about the largest city in the most densely populated country in the world? B-Diddy aka Beardman aka Boom Dizzle dribbles his way through Shanghai, accumulating points for cracking helpless bystanders-turned-defenders and losing whenever he momentary loses his dribble. Check out this great video of the Beardman in a vintage Nintendo-game style format and watch him dribble over benches, through narrow halls, and even on his own head.
Filed under: Basketball Just Released


text:
- About
- For researchers
- For organizations
- Contact us
- Log in or Sign up
Data from: Perspectives on chemotaxonomy: molecular data confirm the existence of two morphologically distinct species within a chemically defined Lepraria caesiella (Stereocaulaceae)
Date Published: September 18, 2012
DOI: http://dx.doi.org/10.5061/dryad.70m919n6
Content in the Dryad Digital Repository is offered "as is." By downloading files, you agree to the Dryad Terms of Service. To the extent possible under law, the authors have waived all copyright and related or neighboring rights to this data.
|53 times
|This is a zipped folder containing: 1) the original alignment prior to analyses, 2) the input file for MP (Paup) analyses with recoded ambiguously aligned regions and step matrices, 3) the input file for ML (Paup) analyses, 4) the input file for ML (RAxML) with ambiguously aligned regions recorded, 5) the input file for BI (MrBayes) analyses.
|caesiella_datasets.zip (13.62 Kb)
|View File Details
When using this data, please cite the original publication:
Additionally, please cite the Dryad data package:
We encourage organizations to:


text:
Already have a VetUK Account?
Don't have an account?
Free delivery on orders with £10 worth of
VetUK own brand products
(click to enlarge)
Manufacturer: Royal Canin
Royal Canin Cocker Spaniel Junior is a complete and nutritious feed for Cocker Spaniel puppies up to 12 months old.
Designed to provide optimum care and support through the first crucial stage of your dog's life, the food has been developed exclusively for the unique physiology of the Cocker Spaniel breed and contains all the high quality ingredients, vitamins and minerals they require.
Main Benefits:
Suitable for English or American Cocker Spaniel puppies up to 12 months.
Feeding Guide:
Ingredients:Dehydrated Poultry Protein, Maize, Animal Fats, Vegetable Protein Isolate*, Wheat, Beet Pulp, Wheat Flour, Rice, Maize Gluten, Hydrolysed Animal Proteins, Maize Flour, Minerals, Fish Oil, Yeasts, Soya Oil, Psyllium Husks And Seeds, Fructo-Oligo-Saccharides, Hydrolysed Yeast (Source Of Manno-Oligo-Saccharides), Borage Oil (0.1%), Hydrolysed Crustaceans (Source Of Glucosamine), Marigold Extract (Source Of Lutein), Hydrolysed Cartilage (Source Of Chondroitin).
Typical Analysis:


text:
Tweak – Revolutionising Print & Design
We've taken our founder Jerry Kennelly's vision and turned it into reality – making great design more accessible, globally. Tweak is a talented, multi-disciplined team who are passionate about design and print. We believe that is a powerful medium that can have a significant impact on the success of large and small businesses. Tweak's solutions are provided on a Software as a Service basis, which means that our clients don't need to maintain servers or software or IT staff for the functions we provide.
Our talented team creates our technologies and content from their locations in Dublin, Lisbon, New York and in our headquarters on the western edge of Europe in Killorglin, County Kerry, Ireland (pictured).
Tweak Cloud
Tweak Cloud brings print and digital design assets online for editing, solving the oldest problem in the history of design. Now anyone in an organisation can have controlled access to edit design and create print or web ready PDFs in minutes, saving significant time and costs. Tweak Cloud has applications for small and large companies as well as for Design and Print firms.
Tweak Print
Tweak Print bringing high quality design for print online and making it available to small and medium enterprises around the world. We work with printers, retailers and publishers on three continents who use our 1.4+ million designs in seven languages to delight their customers with a wide variety of online experiences. By connecting our API solution, their users have access to 140 products in 7 languages with an infrastructure that can be fully integrated into a printing workflow – internally or with partners.


text:
March 11th, 2005
Dr Petra
This week sees the launch of an online men's sexual health referral network – run by Pfizer (makers of Viagra) and an American university medical school. Men who access the site will be able to find their nearest male sexual healthcare professional by typing in their postcode.
Which is great, in theory. In practice, it's not so good.
For a start, it's an online service, so that will rule out many men with no private access to the Internet.
Secondly, although guys will be able to discover a local sexual healthcare advisor, this isn't a free service – so the many men whose health insurance doesn't cover them, will simply be missed out.
Finally, whilst a quick access service is useful, it's not the same as having a thorough check-up by your family physician with a referral to an appropriate treatment service.
Many guys worry about erectile problems. With the current media preoccupation with the condition – encouraged by the pharmaceutical industry – it's not hard to see why.
Pharmaceutical companies have distorted research figures on erectile problems, so men's general sexual dissatisfaction, or occasional sexual problem, is lumped in with chronic sexual difficulties – making erectile problems seem far greater.
True, erectile problems, particularly erectile dysfunction, can be predictors of diabetes, heart disease or similar. But this is why men should always consult with their family physician/ general practitioner – who can identify the cause of the erectile problems – and treat any related problems such as diabetes or cardiac problems.
Encouraging men to self refer to sexual health specialists' muddles up accessing treatment, meaning other serious health problems may not be treated quickly. Men without major sexual problems may be encouraged into medical 'treatments' for occasional dissatisfaction. And those who can't afford healthcare treatment may try and self medicate with herbal products that seem less expensive, but can be deadly.
For men in the UK worried about sexual problems, you can contact the Sexual Dysfunction Association, in confidence on 0870 7743571 and for any men worried about sexual functioning, talking to your GP is your best bet.
Update September 2012
Since writing this blog a comprehensive overview of medicalising erectile dysfunction has been published in a special edition of PLOS Medicine on Disease Mongering. While a report on men's use of an advice service for psychosexual problems reveals the scope of men's concerns and difficulties.
Comments are closed.


text:
Question about Acer Aspire 3690-2196 Notebook
Without looking at my laptop's max memory limitations I ordered two 2GB matched memory sticks off eBay. Before installing I realized that 2GB is the limit. What do recommend I do? What is the effect of adding more than limit? Should I just install one stick? Do I remove old 512 stick also? I'm a little confused at this point.
Note: Memory sticks were advertised as a 4GB upgrade for the 3690. I purchased from Krex Computers in IL. They are manufactured by Golden Mars (NB-DDR2-2GX2).
Posted by gcmiel on
Don't try to load both sticks, your computer will not recognise anything more than the maximum allowed. And could cause problems on your laptop. Take out your 512mb stick and install the 2gb stick on its own.
I hopet his helps
Posted on Nov 16, 2008
Your laptop may just not recognize and not even boot up if you exceed the memory limit. It will not harm the laptop if you give it a try with the 4gb. However, sometimes caution is a good thing. It all depends on what you are trying to do on your acer. If you haven't already, remove the old memory sticks and replace it with the 1 2gb memory stick. Work with it for a little while (this should not give you a problem). If you feel the laptop is still too slow....let me know...I will look up the compatibility with the memory and your laptop.
Posted on Nov 16, 2008
SOURCE: I have freestanding Series 8 dishwasher. Lately during the filling cycle water hammer is occurring. How can this be resolved
a 6ya expert can help you resolve that issue over the phone in a minute or two.
best thing about this new service is that you are never placed on hold and get to talk to real repairmen in the US.
the service is completely free and covers almost anything you can think of (from cars to computers, handyman, and even drones).
click here to download the app (for users in the US for now) and get all the help you need.
Posted on Jan 02, 2017
Tips for a great answer:
Jun 17, 2011 | Acer Aspire 5315 Notebook
Nov 30, 2010 | Acer Aspire One PC Notebook
Aug 14, 2010 | Acer Aspire 5500 5570-2609 Laptop
Jul 10, 2010 | Acer Computers & Internet
Apr 03, 2010 | Acer Aspire 4315 Notebook
Aug 22, 2009 | Acer Computers & Internet
Nov 03, 2008 | Acer Aspire 3690-2196 Notebook
Jul 20, 2008 | Acer Aspire 5610-4648 Notebook
Jan 05, 2008 | Acer Aspire 5610-4648 Notebook
Nov 23, 2007 | Acer Aspire 5100 Notebook
420 people viewed this question
Usually answered in minutes!
Level 3 Expert
18386 Answers
Level 3 Expert
586 Answers
Level 3 Expert
1144 Answers
Step 2: Please assign your manual to a product:


text:
Just a friendly reminder that this Wednesday, August 7th at 6:30pm, you are invited to join us to provide feedback on the first Arts and Humanities Festival event and to learn about upcoming events. The planning meeting will be held at the Petey Green Community Service Center, 2907 Martin Luther King Ave., SE, Washington, DC 20032.
See you on Wednesday!
Dear Community Friends and Advocates:
We hope that this correspondence finds you well and that you were able to join us last Saturday for our Kick-Off Event. It was a great time had by all! The spirit of the day was captured in the attached Washington Informer article from Wednesday, July 31st . Your support in helping tomake first festival a success is greatly appreciated! You will find that much of key feedback provided by the work plan group to date will be reflected in upcoming festival themes, programs and or activities. As we move forward with the remaining dates, we look forward to your continuedinput and participation.
The next Festival Work Plan Group Meeting is scheduled for Wednesday, August 7th at 6:30pm. During this time, a recap of the kick–off event will be provided and we will share the exciting plans for the Summer Weekend Celebration, Saturday, August 17th – Sunday August 18th. Also, additional areas of help will be identified in hopes that we can count on you for volunteering on site, helping to spread the word or providing service in kind.
Look forward to seeing you next week!


text:
fresh air by KariLiimatainenWatch
©2011-2017 KariLiimatainen
This is so cool! Amazing shot!
Great photo!
Images you capture...always are...Extra Ordinary.....
Love the Light work in this Image!!
Love the Light work in this Image!!
stunning shot! very well done! stay well!
Very beautiful)
Nice photo!
Hoarfrost!! ^_^
IHANA kuva!! Rakastan suomea
Amazing photo. I like the colours mostly. This is just like a snowy fairytale!
Keep up the good work!
Keep up the good work!
Where is it taken? It's beautiful.
Very beautiful, great shot
Fantastic work
love it!
love it!
omg amazing wow.
i really like this picture!
walking in a winter wonderland!!
gorgeous! looks very refreshing too... albeit a bit nippy
This is absolutely gorgeous. Makes me believe I am there.
Awesome photo ^^ I really feel like walking down there
I love all the snow and ice, it's a wonderful photo!
wow, this picture is really amazing. great shot
This is absolutely beautiful! Great shot!
great pic!!!!
Beautiful picture!
I always smile when I see the river crossing my city smoking during the winter...
So expressive I can almost feel the crisp air
I love this.
Magnificent snow is always beautiful.
i love it
Absolutely gorgeous... anyone have a mint?
looks exactly like we have here in Siberia. don't you ever wish you lived, say, in California? :]
Yes, sometimes ..
when and where was it taken, if you don't mind my asking? and how cold was it?
Middle of Finland and weather was - 32 degree celsius ..
ouch, that's cold. like *freeze your balls off* cold. well, it's hardly news for us, and for you Finns too, i believe XD
wow white
Wow . cool shot.
Fresh )Prince Of Bel-) Air.
Amazing !
Hidden by Owner


text:
Join us for our Sip & Paint Night this Friday, February 10th, 2017 at 7:00pm in the Auditorium.
To order your ticket go to http://paintnite.com/pages/events/view/longisland/1161482
Come out and enjoy a night of fun, painting & laughs!
For more details contact Miss Arpino.
"The arts are an essential element of education, just like reading, writing, and arithmetic…music, dance, painting,and theater are all keys that unlock profound human understanding and accomplishment."
–William Bennett, Former US Secretary of Education
Theatre and the Performing Arts are an essential part of a K-12 education for all students, developing abilities needed for the 21st century such as:
Students will learn teamwork and discipline while fostering artistic growth. The Students round out these skills with unique performance opportunities as well.
The activities and performances are aligned with the standards set forth in the National Core Arts Standards in which students create, perform, respond, and connect.
If you love performing and are looking for more,
you can be a part of all the excitement!
Consider joining our Performing Arts Club, Stage Crew or
Early Childhood Dance Program!
There is something for everyone!


text:
Please enter the location name or STD code
Having a Bradford phone can help you obtain more customers in your local area. Being able to get a foothold in neighbouring towns and citys is a great way to drive your business forward. Get a Bradford phone number now.
Buy a 01274 number and have it pointed to your existing landline or mobile phone.
01274 number online by clicking
Have a question? Call us or view our Frequently asked questions here
Please remember that it can take up to 5 days to setup a 01274 number. However it is in the likely hood that it will be much sooner.
Interesting Bradford phone numbers:
Telegraph & Argus - 01274 729511
Bradford Cathedral - 01274 777720
Pence Per Minute: If to a landline: 3p
Pence Per Minute: If to a mobile: 9p
Set up Fee: FROM £15.00
Monthly Rental: £5.00
The minimum contract term is just 30 days
International Routing - Charges
Order your Number Below
* - Monthly rental
All prices exclude VAT.
loading ...
Back to Top


text:
Multifunctional and stylish office chair was created to simplify your home office or based workstation. This contemporary chair is perfect for any office environment. Made from the stainless steel and covered with red-colored leather, it can give an ultimate comfort.
- Conference Office Chair
- Mid Back
- Confreto Collection
- Stainless Steel frame
- 5 star base with casters
- Tilt Lock
- Leather seat and back
- Tilt Tension
- Removable Arms
- Red Finish
- 38"H x 25"W x 24"D
- Seat 18"-21"H
Bring a timeless style to your indoor and outdoor spaces with modern, Big City styled furniture from Fine Mod Imports. The pieces feature renowned designs that will be the best way to decorate your home and make it more attractive and memorable. The assortment at ModernManhattan.com includes accent chairs, coffee tables, furniture for office, dining room and living room.
Write a reviewYour Name:
Your Review: Note: HTML is not translated!
Rating: Bad Good
Enter the code in the box below:
Desk Chairs
Bring maximum comfort while sitting and working with our office and desk chairs. They feature ergonomic seats and back adjustments, gas lift, head rests, metal or plastic frames and bases. From computer and task chairs to executive office chairs and leather chairs, we have desk chairs from leading and trustworthy office furniture manufacturers. All of our ergonomic office chairs are available in various sizes, shapes, finishes, all at affordable prices.
ModernManhattan.com offers a vast assortment of chairs to provide even the exacting customers with various options for home/office.


text:
April 26th, 2009 at 1pm
163rd Street Mall @Â 1205 NW 163rd Street, North Miami, Florida
Jasmina Anema's search to find a bone marrow donor is striking a chord among Florida-based entertainers and athletes, who have united to help the six-year-old leukemia patient.
Rappers Rick Ross, Trick Daddy, Pitbull and Flo-Rida are among the celebrities lending their support and assistance to a special event in honor of Anema.
The event is scheduled to take place from 1p.m. to 8 p.m. April 26 at the 163rd Street Mall, 1205 NW 163rd Street, North Miami.
Organized by original Fat Boys member Prince Markie Dee's Labor of Love Foundation, 103.5 The Beat, the Community Blood Centers of South Florida and AllHipHop.com, the event hopes to draw find those who stand a chance of being a match for Jasmina.
In addition to Ross, Trick Daddy and Flo-Rida, the event will include appearances from R&B/pop crooner Sean Kingston and Uncle Louie, as well as Ricky Williams of the Miami Dolphins and Ricky Davis of the Miami Heat.
Fans will be able to donate blood to the Centers at mobile blood banks as well as visit a tent set up at the Mall to see if they are a match for Jasmina.
Those attending the April 26 event will be treated to free drinks, snacks and pizza as well as a goody bag filled with a free T-shirt and free tickets to the Improv Comedy Club.
Autograph signings, celebrity photo sessions and a raffle for two free five-day/four- night Orlando vacations are also slated to take place with more giveaways to be announced in the days leading up to the event.
For more information on the Labor of Love event and to view the flyer, visit www.OriginalFatBoys.com/laboroflove
Soruce: Allhiphop