text:
Algorithms/Randomization

As deterministic algorithms are driven to their limits when one tries to solve hard problems with them, a useful technique to speed up the computation is randomization. In randomized algorithms, the algorithm has access to a random source, which can be imagined as tossing coins during the computation. Depending on the outcome of the toss, the algorithm may split up its computation path.

There are two main types of randomized algorithms: Las Vegas algorithms and Monte-Carlo algorithms. In Las Vegas algorithms, the algorithm may use the randomness to speed up the computation, but the algorithm must always return the correct answer to the input. Monte-Carlo algorithms do not have the latter restriction, that is, they are allowed to give wrong return values. However, returning a wrong return value must have a small probability, otherwise that Monte-Carlo algorithm would not be of any use.

Many approximation algorithms use randomization.

Ordered Statistics
Before covering randomized techniques, we'll start with a deterministic problem that leads to a problem that utilizes randomization. Suppose you have an unsorted array of values and you want to find

 * the maximum value,
 * the minimum value, and
 * the median value.

In the immortal words of one of our former computer science professors, "How can you do?"

find-max
First, it's relatively straightforward to find the largest element:

// find-max -- returns the maximum element function find-max(array vals[1..n]): element let result := vals[1] for i from 2 to n: result := max(result, vals[i]) repeat return result end

An initial assignment of $$-\infty$$ to result would work as well, but this is a useless call to the max function since the first element compared gets set to result. By initializing result as such the function only requires n-1 comparisons. (Moreover, in languages capable of metaprogramming, the data type may not be strictly numerical and there might be no good way of assigning $$-\infty$$; using vals[1] is type-safe.)

A similar routine to find the minimum element can be done by calling the min function instead of the max function.

find-min-max
But now suppose you want to find the min and the max at the same time; here's one solution:

// find-min-max -- returns the minimum and maximum element of the given array function find-min-max(array vals): pair return pair {find-min(vals), find-max(vals)} end

Because find-max and find-min both make n-1 calls to the max or min functions (when vals has n elements), the total number of comparisons made in find-min-max is $$2n-2$$.

However, some redundant comparisons are being made. These redundancies can be removed by "weaving" together the min and max functions:

// find-min-max -- returns the minimum and maximum element of the given array function find-min-max(array vals[1..n]): pair let min := $$\infty$$ let max := $$-\infty$$ if n is odd: min := max := vals[1] vals := vals[2,..,n]         // we can now assume n is even n := n - 1 fi  for i:=1 to n by 2:             // consider pairs of values in vals if vals[i] < vals[i + 1]: let a := vals[i] let b := vals[i + 1] else: let a := vals[i + 1] let b := vals[i]           // invariant: a <= b fi    if a < min: min := a fi     if b > max: max := b fi   repeat return pair {min, max} end

Here, we only loop $$n/2$$ times instead of n times, but for each iteration we make three comparisons. Thus, the number of comparisons made is $$(3/2)n = 1.5n$$, resulting in a $$3/4$$ speed up over the original algorithm.

Only three comparisons need to be made instead of four because, by construction, it's always the case that $$a\le b$$. (In the first part of the "if", we actually know more specifically that $$a < b$$, but under the else part, we can only conclude that $$a\le b$$.) This property is utilized by noting that a doesn't need to be compared with the current maximum, because b is already greater than or equal to a, and similarly, b doesn't need to be compared with the current minimum, because a is already less than or equal to b.

In software engineering, there is a struggle between using libraries versus writing customized algorithms. In this case, the min and max functions weren't used in order to get a faster find-min-max routine. Such an operation would probably not be the bottleneck in a real-life program: however, if testing reveals the routine should be faster, such an approach should be taken. Typically, the solution that reuses libraries is better overall than writing customized solutions. Techniques such as open implementation and aspect-oriented programming may help manage this contention to get the best of both worlds, but regardless it's a useful distinction to recognize.

find-median
Finally, we need to consider how to find the median value. One approach is to sort the array then extract the median from the position vals[n/2]:

// find-median -- returns the median element of vals function find-median(array vals[1..n]): element assert (n > 0) sort(vals) return vals[n / 2] end

If our values are not numbers close enough in value (or otherwise cannot be sorted by a radix sort) the sort above is going to require $$O(n\log n)$$ steps.

However, it is possible to extract the nth-ordered statistic in $$O(n)$$ time. The key is eliminating the sort: we don't actually require the entire array to be sorted in order to find the median, so there is some waste in sorting the entire array first. One technique we'll use to accomplish this is randomness.

Before presenting a non-sorting find-median function, we introduce a divide and conquer-style operation known as partitioning. What we want is a routine that finds a random element in the array and then partitions the array into three parts:

 * 1) elements that are less than or equal to the random element;
 * 2) elements that are equal to the random element; and
 * 3) elements that are greater than or equal to the random element.

These three sections are denoted by two integers: j and i. The partitioning is performed "in place" in the array:

// partition -- break the array three partitions based on a randomly picked element function partition(array vals): pair{j, i}

Note that when the random element picked is actually represented three or more times in the array it's possible for entries in all three partitions to have the same value as the random element. While this operation may not sound very useful, it has a powerful property that can be exploited: When the partition operation completes, the randomly picked element will be in the same position in the array as it would be if the array were fully sorted!

This property might not sound so powerful, but recall the optimization for the find-min-max function: we noticed that by picking elements from the array in pairs and comparing them to each other first we could reduce the total number of comparisons needed (because the current min and max values need to be compared with only one value each, and not two). A similar concept is used here.

While the code for partition is not magical, it has some tricky boundary cases:

// partition -- break the array into three ordered partitions from a random element function partition(array vals): pair{j, i} let m := 0 let n := vals.length - 2  //  for an array vals, vals[vals.length-1] is the last element, which holds the partition, // so the last sort element is vals[vals.length-2] let irand := random(m, n)  // returns any value from m to n let x := vals[irand] swap( irand,n+ 1 ) // n+1 = vals.length-1, which is the right most element, and acts as store for partition element and sentinel for m  // values in vals[n..] are greater than x // values in vals[0..m] are less than x while (m <= n ) // see explanation in quick sort why should be m <= n instead of m < n in the 2 element case, // vals.length -2 = 0 = n = m, but if the 2-element case is out-of-order vs. in-order, there must be a different action. // by implication, the different action occurs within this loop, so must process the m = n case before exiting. while vals[m] <= x // in the 2-element case, second element is partition, first element at m. If in-order, m will increment m++ endwhile while x < vals[n] && n > 0   // stops if vals[n] belongs in left partition or hits start of array n—endwhile if ( m >= n) break; swap(m,n)               // exchange vals[n] and vals[m] m++  // don't rescan swapped elements n—endwhile // partition: [0..m-1]  []   [n+1..]   note that m=n+1 // if you need non empty sub-arrays: swap(m,vals.length - 1) // put the partition element in the between left and right partitions // in 2-element out-of-order case, m=0 (not incremented in loop), and the first and last(second) element will swap. // partition: [0..n-1]  [n..n]   [n+1..] end

We can use partition as a subroutine for a general find operation:

// find -- moves elements in vals such that location k holds the value it would when sorted function find(array vals, integer k) assert (0 <= k < vals.length)       // k it must be a valid index if vals.length <= 1: return fi  let pair (j, i) := partition(vals) if k <= i: find(a[0,..,i], k) else-if j <= k: find(a[j,..,n], k - j) fi  TODO: debug this! end

Which leads us to the punch-line:

// find-median -- returns the median element of vals function find-median(array vals): element assert (vals.length > 0) let median_index := vals.length / 2; find(vals, median_index) return vals[median_index] end

One consideration that might cross your mind is "is the random call really necessary?" For example, instead of picking a random pivot, we could always pick the middle element instead. Given that our algorithm works with all possible arrays, we could conclude that the running time on average for all of the possible inputs is the same as our analysis that used the random function. The reasoning here is that under the set of all possible arrays, the middle element is going to be just as "random" as picking anything else. But there's a pitfall in this reasoning: Typically, the input to an algorithm in a program isn't random at all. For example, the input has a higher probability of being sorted than just by chance alone. Likewise, because it is real data from real programs, the data might have other patterns in it that could lead to suboptimal results.

To put this another way: for the randomized median finding algorithm, there is a very small probability it will run suboptimally, independent of what the input is; while for a deterministic algorithm that just picks the middle element, there is a greater chance it will run poorly on some of the most frequent input types it will receive. This leads us to the following guideline:

Note that there are "derandomization" techniques that can take an average-case fast algorithm and turn it into a fully deterministic algorithm. Sometimes the overhead of derandomization is so much that it requires very large datasets to get any gains. Nevertheless, derandomization in itself has theoretical value.

The randomized find algorithm was invented by C. A. R. "Tony" Hoare. While Hoare is an important figure in computer science, he may be best known in general circles for his quicksort algorithm, which we discuss in the next section.

Quicksort
The median-finding partitioning algorithm in the previous section is actually very close to the implementation of a full blown sorting algorithm. Building a Quicksort Algorithm is left as an exercise for the reader, and is recommended first, before reading the next section ( Quick sort is diabolical compared to Merge sort, which is a sort not improved by a randomization step ).

A key part of quick sort is choosing the right median. But to get it up and running quickly, start with the assumption that the array is unsorted, and the rightmost element of each array is as likely to be the median as any other element, and that we are entirely optimistic that the rightmost doesn't happen to be the largest key, which would mean we would be removing one element only ( the partition element) at each step, and having no right array to sort, and a n-1 left array to sort.

This is where randomization is important for quick sort, i.e. choosing the more optimal partition key, which is pretty important for quick sort to work efficiently.

Compare the number of comparisions that are required for quick sort vs. insertion sort.

With insertion sort, the average number of comparisons for finding the lowest first element in an ascending sort of a randomized array is n /2.

The second element's average number of comparisons is (n-1)/2;

the third element ( n- 2) / 2.

The total number of comparisons is  [ n  + (n - 1) + (n - 2) + (n - 3) .. + (n - [n-1]) ] divided by 2,   which is  [ n x n - (n-1)! ] /2 or about O(n squared).

In Quicksort, the number of comparisons will halve at each partition step if the true median is chosen, since the left half partition doesn't need to be compared with the right half partition, but at each step, the number elements of all partitions created by the previously level of partitioning will still be n.

The number of levels of comparing n elements is the number of steps of dividing n by two, until n = 1. Or in reverse, 2 ^ m ~ n, so m = log2 n.

So the total number of comparisons is n (elements) x m (levels of scanning)  or  n x log2n  ,

So the number of comparison is O(n x log 2(n) ), which is smaller than insertion sort's  O(n^2) or O( n x n ).

(Comparing O(n x log 2(n) ) with O( n x n ), the common factor n can be eliminated , and the comparison is log2(n) vs n , which is exponentially different as n becomes larger. e.g. compare  n = 2^16  , or 16 vs 32768, or 32 vs 4 gig ).

To implement the partitioning in-place on a part of the array determined by a previous recursive call, what is needed a scan from each end of the part, swapping whenever the value of the left scan's current location is greater than the partition value, and the value of the right scan's current location is less than the partition value. So the initial step is :- Assign the partition value to the right most element, swapping if necessary.

So the partitioning step is :- increment the left scan pointer while the current value is less than the partition value. decrement the right scan pointer while the current value is more than the partition value , or the location is equal to or more than the left most location. exit if the pointers have crossed ( l >= r), OTHERWISE perform a swap where the left and right pointers have stopped , on values where the left pointer's value is greater than the partition, and the right pointer's value is less than the partition. Finally, after exiting the loop because the left and right pointers have crossed,  swap the rightmost partition value,   with the last location of the left forward scan pointer ,    and hence ends up between the left and right partitions.

Make sure at this point, that after the final swap, the cases of a 2 element in-order array, and a 2 element out-of-order array , are handled correctly, which should mean all cases are handled correctly. This is a good debugging step for getting quick-sort to work.

For the in-order two-element case, the left pointer stops on the partition or second element, as the partition value is found. The right pointer, scanning backwards, starts on the first element before the partition, and stops because it is in the leftmost position.

The pointers cross, and the loop exits before doing a loop swap. Outside the loop, the contents of the left pointer at the rightmost position and the partition, also at the right most position , are swapped, achieving no change to the in-order two-element case.

For the out-of-order two-element case, The left pointer scans and stops at the first element, because it is greater than the partition (left scan value stops to swap values greater than the partition value).

The right pointer starts and stops at the first element because it has reached the leftmost element.

The loop exits because left pointer and right pointer are equal at the first position, and the contents of the left pointer at the first position and the partition at the rightmost (other) position, are swapped , putting previously out-of-order elements ,  into order.

Another implementation issue, is to how to move the pointers during scanning. Moving them at the end of the outer loop seems logical.

partition(a,l,r) { v = a[r]; i = l;  j = r -1; while ( i <= j ) { // need to also scan when i = j as well as i < j , // in the 2 in-order case, // so that i is incremented to the partition // and nothing happens in the final swap with the partition at r.    while ( a[i] < v) ++i; while ( v <= a[j] && j > 0 ) --j; if ( i >= j) break; swap(a,i,j); ++i; --j; } swap(a, i, r); return i;

With the pre-increment/decrement unary operators, scanning can be done just before testing within the test condition of the while loops, but this means the pointers should be offset -1 and +1 respectively at the start : so the algorithm then looks like:-

partition (a, l, r ) { v=a[r]; // v is partition value, at a[r] i=l-1; j=r; while(true) { while( a[++i] < v ); while( v <= a[--j] && j > l ); if (i >= j) break; swap ( a, i, j); } swap (a,i,r); return i; }

And the qsort algorithm is qsort( a, l, r) { if (l >= r) return ; p = partition(a, l, r)  qsort(a, l, p-1) qsort( a, p+1, r) }

Finally, randomization of the partition element.

random_partition (a,l,r) { p = random_int( r-l) + l; // median of a[l], a[p], a[r] if (a[p] < a[l]) p =l; if ( a[r]< a[p]) p = r; swap(a, p, r); }

this can be called just before calling partition in qsort.

Shuffling an Array
This keeps data in during shuffle temporaryArray = { } This records if an item has been shuffled usedItemArray = { } Number of item in array itemNum = 0 while ( itemNum != lengthOf( inputArray) ){ usedItemArray[ itemNum ] = false None of the items have been shuffled itemNum = itemNum + 1 }  itemNum = 0 we'll use this again itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 )) while( itemNum != lengthOf( inputArray ) ){ while( usedItemArray[ itemPosition ] != false ){ itemPosition = randdomNumber( 0 --- (lengthOf(inputArray) - 1 )) }      temporaryArray[ itemPosition ] = inputArray[ itemNum ] itemNum = itemNum + 1 }  inputArray = temporaryArray

Equal Multivariate Polynomials
[TODO: as of now, there is no known deterministic polynomial time solution, but there is a randomized polytime solution. The canonical example used to be IsPrime, but a deterministic, polytime solution has been found.]

Hash tables
Hashing relies on a hashcode function to randomly distribute keys to available slots evenly. In java, this is done in a fairly straight forward method of adding a moderate sized prime number (31 * 17 ) to a integer key , and then modulus by the size of the hash table. For string keys, the initial hash number is obtained by adding the products of each character's ordinal value multiplied by 31.

The wikibook Data Structures/Hash Tables chapter covers the topic well.

Skip Lists
[TODO: Talk about skips lists. The point is to show how randomization can sometimes make a structure easier to understand, compared to the complexity of balanced trees.]

Dictionary or Map, is a general concept where a value is inserted under some key, and retrieved by the key. For instance, in some languages, the dictionary concept is built-in (Python), in others , it is in core libraries ( C++ S.T.L. , and Java standard collections library ). The library providing languages usually lets the programmer choose between a hash algorithm, or a balanced binary tree implementation (red-black trees). Recently, skip lists have been offered, because they offer advantages of being implemented to be highly concurrent for multiple threaded applications.

Hashing is a technique that depends on the randomness of keys when passed through a hash function, to find a hash value that corresponds to an index into a linear table. Hashing works as fast as the hash function, but works well only if the inserted keys spread out evenly in the array, as any keys that hash to the same index, have to be deal with as a hash collision problem e.g. by keeping a linked list for collisions for each slot in the table, and iterating through the list to compare the full key of each key-value pair vs the search key.

The disadvantage of hashing is that in-order traversal is not possible with this data structure.

Binary trees can be used to represent dictionaries, and in-order traversal of binary trees is possible by visiting of nodes ( visit left child, visit current node, visit right child, recursively ). Binary trees can suffer from poor search when they are "unbalanced" e.g. the keys of key-value pairs that are inserted were inserted in ascending or descending order, so they effectively look like linked lists with no left child, and all right children. self-balancing binary trees can be done probabilistically (using randomness) or deterministically ( using child link coloring as red or black ), through local 3-node tree rotation operations. A rotation is simply swapping a parent with a child node, but preserving order e.g. for a left child rotation, the left child's right child becomes the parent's left child, and the parent becomes the left child's right child.

Red-black trees can be understood more easily if corresponding 2-3-4 trees are examined. A 2-3-4 tree is a tree where nodes can have 2 children, 3 children, or 4 children, with 3 children nodes having 2 keys between the 3 children, and 4 children-nodes having 3 keys between the 4 children. 4-nodes are actively split into 3 single key 2 -nodes, and the middle 2-node passed up to be merged with the parent node, which , if a one-key 2-node, becomes a two key 3-node; or if a two key 3-node, becomes a 4-node, which will be later split (on the way up). The act of splitting a three key 4-node is actually a re-balancing operation, that prevents a string of 3 nodes of grandparent, parent, child occurring , without a balancing rotation happening. 2-3-4 trees are a limited example of B-trees, which usually have enough nodes as to fit a physical disk block, to facilitate caching of very large indexes that can't fit in physical RAM ( which is much less common nowadays).

A red-black tree is a binary tree representation of a 2-3-4 tree, where 3-nodes are modeled by a parent with one red child, and 4 -nodes modeled by a parent with two red children. Splitting of a 4-node is represented by the parent with 2 red children, flipping the red children to black, and itself into red. There is never a case where the parent is already red, because there also occurs balancing operations where if there is a grandparent with a red parent with a red child, the grandparent is rotated to be a child of the parent, and parent is made black and the grandparent is made red; this unifies with the previous flipping scenario, of a 4-node represented by 2 red children. Actually, it may be this standardization of 4-nodes with mandatory rotation of skewed or zigzag 4-nodes that results in re-balancing of the binary tree.

A newer optimization is to left rotate any single right red child to a single left red child, so that only right rotation of left-skewed inline 4-nodes (3 red nodes inline ) would ever occur, simplifying the re-balancing code.

Skip lists are modeled after single linked lists, except nodes are multilevel. Tall nodes are rarer, but the insert operation ensures nodes are connected at each level.

Implementation of skip lists requires creating randomly high multilevel nodes, and then inserting them.

Nodes are created using iteration of a random function where high level node occurs later in an iteration, and are rarer, because the iteration has survived a number of random thresholds (e.g. 0.5, if the random is between 0 and 1).

Insertion requires a temporary previous node array with the height of the generated inserting node. It is used to store the last pointer for a given level, which has a key less than the insertion key.

The scanning begins at the head of the skip list, at highest level of the head node, and proceeds across until a node is found with a key higher than the insertion key, and the previous pointer stored in the temporary previous node array. Then the next lower level is scanned from that node, and so on, walking zig-zag down, until the lowest level is reached.

Then a list insertion is done at each level of the temporary previous node array, so that the previous node's next node at each level is made the next node for that level for the inserting node, and the inserting node is made the previous node's next node.

Search involves iterating from the highest level of the head node to the lowest level, and scanning along the next pointer for each level until a node greater than the search key is found, moving down to the next level, and proceeding with the scan, until the higher keyed node at the lowest level has been found, or the search key found.

The creation of less frequent-when-taller, randomized height nodes, and the process of linking in all nodes at every level, is what gives skip lists their advantageous overall structure.

a method of skip list implementation : implement lookahead single-linked linked list, then test, then transform to skip list implementation, then same test, then performance comparison
What follows is a implementation of skip lists in python. A single linked list looking at next node as always the current node, is implemented first, then the skip list implementation follows, attempting minimal modification of the former, and comparison helps clarify implementation.

Role of Randomness
The idea of making higher nodes geometrically randomly less common, means there are less keys to compare with the higher the level of comparison, and since these are randomly selected, this should get rid of problems of degenerate input that makes it necessary to do tree balancing in tree algorithms. Since the higher level list have more widely separated elements, but the search algorithm moves down a level after each search terminates at a level, the higher levels help "skip" over the need to search earlier elements on lower lists. Because there are multiple levels of skipping, it becomes less likely that a meagre skip at a higher level won't be compensated by better skips at lower levels, and Pugh claims O(logN) performance overall.

Conceptually, is it easier to understand than balancing trees and hence easier to implement ? The development of ideas from binary trees, balanced binary trees, 2-3 trees, red-black trees, and B-trees make a stronger conceptual network but is progressive in development, so arguably, once red-black trees are understood, they have more conceptual context to aid memory, or refresh of memory.

concurrent access application
Apart from using randomization to enhance a basic memory structure of linked lists, skip lists can also be extended as a global data structure used in a multiprocessor application. See supplementary topic at the end of the chapter.

Idea for an exercise
Replace the Linux completely fair scheduler red-black tree implementation with a skip list, and see how your brand of Linux runs after recompiling.

Treaps
A treap is a two keyed binary tree, that uses a second randomly generated key and the previously discussed tree operation of parent-child rotation to randomly rotate the tree so that overall, a balanced tree is produced. Recall that binary trees work by having all nodes in the left subtree small than a given node, and all nodes in a right subtree greater. Also recall that node rotation does not break this order ( some people call it an invariant), but changes the relationship of parent and child, so that if the parent was smaller than a right child, then the parent becomes the left child of the formerly right child. The idea of a tree-heap or treap, is that a binary heap relationship is maintained between parents and child, and that is a parent node has higher priority than its children, which is not the same as the left, right order of keys in a binary tree, and hence a recently inserted leaf node in a binary tree which happens to have a high random priority, can be rotated so it is relatively higher in the tree, having no parent with a lower priority.

A treap is an alternative to both red-black trees, and skip lists, as a self-balancing sorted storage structure.

Treaps compared and contrasted to Splay trees
Splay trees are similar to treaps in that rotation is used to bring a higher priority node to the top without changing the main key order, except instead of using a random key for priority, the last accessed node is rotated to the root of the tree, so that more frequently accessed nodes will be near the top. This means that in treaps, inserted nodes will only rotate upto the priority given by their random priority key, whereas in splay trees, the inserted node is rotated to the root, and every search in a splay tree will result in a re-balancing, but not so in a treap.

Derandomization
[TODO: Deterministic algorithms for Quicksort exist that perform as well as quicksort in the average case and are guaranteed to perform at least that well in all cases. Best of all, no randomization is needed. Also in the discussion should be some perspective on using randomization: some randomized algorithms give you better confidence probabilities than the actual hardware itself! (e.g. sunspots can randomly flip bits in hardware, causing failure, which is a risk we take quite often)]

[Main idea: Look at all blocks of 5 elements, and pick the median (O(1) to pick), put all medians into an array (O(n)), recursively pick the medians of that array, repeat until you have < 5 elements in the array. This recursive median constructing of every five elements takes time T(n)=T(n/5) + O(n), which by the master theorem is O(n). Thus, in O(n) we can find the right pivot. Need to show that this pivot is sufficiently good so that we're still O(n log n) no matter what the input is. This version of quicksort doesn't need rand, and it never performs poorly. Still need to show that element picked out is sufficiently good for a pivot.]

Exercises

 * 1) Write a find-min function and run it on several different inputs to demonstrate its correctness.

Supplementary Topic: skip lists and multiprocessor algorithms
Multiprocessor hardware provides CAS ( compare-and-set) or CMPEXCHG( compare-and-exchange)(intel manual 253666.pdf, p 3-188) atomic operations,  where an expected value is loaded into the accumulator register, which is compared to a target memory location's contents, and if the same, a source memory location's contents is loaded into the target memories contents, and the zero flag set, otherwise, if different, the target memory's contents is returned in the accumulator, and the zero flag is unset, signifying, for instance, a lock contention. In the intel architecture, a LOCK instruction is issued before CMPEXCHG, which either locks the cache from concurrent access if the memory location is being cached, or locks a shared memory location if not in the cache , for the next instruction.

The CMPEXCHG can be used to implement locking, where spinlocks, e.g. retrying until the zero flag is set, are simplest in design.

Lockless design increases efficiency by avoiding spinning waiting for a lock.

The java standard library has an implementation of non-blocking concurrent skiplists, based on a paper titled "a pragmatic implementation of non-blocking single-linked lists".

The skip list implementation is an extension of the lock-free single-linked list, of which a description follows :-

The insert operation is : X -> Y  insert N,  N -> Y,  X -> N ; expected result is X -> N -> Y.

A race condition is if M is inserting between X and Y and M completes first, then N completes, so the situation is X -> N -> Y <- M

M is not in the list. The CAS operation avoids this, because a copy of -> Y is checked before updating X ->, against the current value of X ->.

If N gets to update X -> first, then when M tries to update X -> , its copy of X -> Y , which it got before doing M -> Y , does not match X -> N , so CAS returns non-zero flag set (recall that CAS requires the user to load the accumulator with the expected value, the target location's current value, and then atomically updates the target location with a source location if the target location still contains the accumulator's value). The process that tried to insert M then can retry the insertion after X, but now the CAS checks ->N is X's next pointer, so after retry, X->M->N->Y, and neither insertions are lost.

If M updates X-> first, N 's copy of X->Y does not match X -> M, so the CAS will fail here too, and the above retry of the process inserting N, would have the serialized result of X ->N -> M -> Y.

The delete operation depends on a separate 'logical' deletion step, before 'physical' deletion.

'Logical' deletion involves a CAS change of the next pointer into a 'marked' pointer. The java implementation substitutes with an atomic insertion of a proxy marker node to the next node.

This prevents future insertions from inserting after a node which has a next pointer 'marked', making the latter node 'logically' deleted.

The insert operation relies on another function, search , returning 2 unmarked , at the time of the invocation, node pointers : the first pointing to a node , whose next pointer is equal to the second.

The first node is the node before the insertion point.

The insert CAS operation checks that the current next pointer of the first node, corresponds to the unmarked reference of the second, so will fail 'logically' if the first node's next pointer has become marked after the call to the search function above, because the first node has been concurrently logically deleted. This meets the aim to prevent a insertion occurring concurrently after a node has been deleted.

If the insert operation fails the CAS of the previous node's next pointer, the search for the insertion point starts from the start of the entire list again, since a new unmarked previous node needs to be found, and there are no previous node pointers as the list nodes are singly-linked.

The delete operation outlined above, also relies on the search operation returning two unmarked nodes, and the two CAS operations in delete, one for logical deletion or marking of the second pointer's next pointer, and the other for physical deletion by making the first node's next pointer point to the second node's unmarked next pointer.

The first CAS of delete happens only after a check that the copy of the original second nodes' next pointer is unmarked, and ensures that only one concurrent delete succeeds which reads the second node's current next pointer as being unmarked as well.

The second CAS checks that the previous node hasn't been logically deleted because its next pointer is not the same as the unmarked pointer to the current second node returned by the search function, so only an active previous node's next pointer is 'physically' updated to a copy of the original unmarked next pointer of the node being deleted ( whose next pointer is already marked by the first CAS).

If the second CAS fails, then the previous node is logically deleted and its next pointer is marked, and so is the current node's next pointer. A call to search function again, tidies things up, because in endeavouring to find the key of the current node and return adjacent unmarked previous and current pointers, and while doing so, it truncates strings of logically deleted nodes.

Lock-free programming issues
Starvation could be possible, as failed inserts have to restart from the front of the list. Wait-freedom is a concept where the algorithm has all threads safe from starvation.

The ABA problem exists, where a garbage collector recycles the pointer A, but the address is loaded differently, and the pointer is re-added at a point where a check is done for A by another thread that read A and is doing a CAS to check A has not changed ; the address is the same and is unmarked, but the contents of A has changed.

title: Algorithms/Randomization


text:
User:Gindungo

Gindungo, or jindungo is the Portuguese name for a small hot pepper found in areas of Africa. It is an ingredient in piri-piri sauce. I am from Angola where these hot peppers are a favorite condiment and used to marinate chicken along with garlic and lemon juice prior to grilling over charcoal.

source: wikimedia

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: User:Gindungo


text:
Matt Doorey

Matthew Doorey (born 27 June 2000) is a professional rugby league footballer who plays as a forward for the Parramatta Eels in the National Rugby League (NRL). He previously played for the Canterbury-Bankstown Bulldogs.

2020
Doorey made his first grade debut in round 14 of the 2020 NRL season for Canterbury-Bankstown against the Wests Tigers, scoring a try on debut in a 29–28 loss at Bankwest Stadium.

2021
Doorey made a total of 13 appearances for Canterbury in the 2021 NRL season as the club finished last and claimed the wooden spoon.

2022
Doorey made no appearances for Canterbury in the 2022 NRL season. On 25 September, Doorey played for Canterbury's NSW Cup team in their grand final loss to Penrith. On 11 November, Doorey signed a two-year deal to join Canterbury's arch-rivals Parramatta starting in 2023.

2023
Doorey made his club debut for Parramatta in round 1 of the 2023 NRL season against Melbourne. Parramatta would lose 16-12 in golden point extra-time. In round 3 against Manly, Doorey scored his first try for the club in Parramatta's 34-30 loss at Brookvale Oval. Doorey played a total of eleven matches for Parramatta in the 2023 NRL season as the club finished 10th on the table.

2024
Doorey started the 2024 season for Parramatta's reserve grade team, in good form. On 4 April, it was announced that Doorey would miss at least five weeks with a facial fracture, he returned in Round 7.

title: Matt Doorey


text:
Wikipedia:Help desk/Archives/2015 February 5

= February 5 =

Help:Cite errors/Cite error included ref
Hi, Under the animal Pangolin I attempted to add it was the most trafficked animal in the world ) I made a mistake in my editing if someone can please fix what I did it would be appreciated
 * malformed . ― Mandruss  ☎  02:12, 5 February 2015 (UTC)

Michael Cole
Hello I have compiled a page on Michael Cole (writer) and it has been accepted. However, there was a request to add more citations and change it from list to prose form. This I did but the warnings still appear at the top of the page. It also said that the writer has a close connection to the subject, this is true but everything is factual and backed up by external references and links to pages on Wikipedia that talk about TV programmes created by Michael Cole. Please could you let me know what further things can I do ? Also is it possible to change the title to Michael Cole (writer/TV producer) or is it too late? Thank you for your help. Sam — Preceding unsigned comment added by Scole88 (talk • contribs) 11:20, 5 February 2015 (UTC)
 * I've removed the references required tag. I've left the conflict of interest one for now as I haven't thoroughly read through the article, but a brief scan makes me think it will be OK. - X201 (talk) 11:53, 5 February 2015 (UTC)

Cant get wikidata to save
I am trying to add a new language entry to the English article Metapopulation. This is a new article in the Welsh Language which I am working on on that wikipedia. I speak both languages fluently, https://cy.wikipedia.org/wiki/Metaboblogaeth but after adding cy and putting the word Metaboblogaeth into the table clicking on the word save fails to do anything. What am I doing wrong? — Preceding unsigned comment added by Neilj (talk • contribs) 12:32, 5 February 2015 (UTC)

 * If you look at the existing Wikidata items, and at the instructions at the head of the edit page, it doesn't want "cy" but instead wants "cywiki". I have done that. --David Biddulph (talk) 12:40, 5 February 2015 (UTC)

Korean influence on Japanese culture
Not sure if this is the place for this, but is it possible to dispute an AFD close several months after the fact? Articles for deletion/Korean influence on Japanese culture had almost no support for keeping the page: after one week there was a 6-2 majority in favour of deletion, but the AFD was allowed stay open just long enough for the waters to be muddied; after just under 9 days it was 7-3; then in the last 30 hours or so before closing the numbers changed just enough that it could be possibly closed as "no consensus" despite an 8-5 majority for deletion. Within that period of barely a day, User:Nishidani, User:Imaginatorium and I replied to the latecomers (who had obviously not read the discussion before carelessly casting !votes), but it would seem they didn't have time to read our responses and put more consideration into it.

I initially didn't dispute the result, since the general consensus was that in theory the article could be good, but that some high explosives were called for first, and at first I encountered only limited resistance in doing so. But recently the page has turned back into a massive fustercluck, to the point where even when User:Nishidani and I actually make a serious effort to painstakingly check all the sources and rewrite each sentence of the article to accurately represent what is in said sources, we are being opposed EVERY SINGLE STEP OF THE WAY (just look at the page's recent edit history -- 100% of Jagello's edits are blank reverts).

I'm not asking for the page to be deleted (I've put way too much work into it at this stage). But I'm wondering if there's any way to alter the result to better reflect the actual consensus of "The article MIGHT be appropriate at some time in the future, but in the mean time every single sentence is suspect and can be removed pending verification", or some such.

Hijiri 88 ( 聖やや ) 12:41, 5 February 2015 (UTC)

 * The deletion discussion took place four months ago. As Hijiri88 says, the result was No Consensus.  I am not aware of a way to tag an article as "This is a crappy article that we are keeping for future use", which seems to be what the OP is proposing; and, if there were, I think it would be a bad idea.  However, the issue at this point isn't an old deletion discussion.  The real issue at this point is that the article is being subject to edit-warring (by editors trying to improve or change the article and by editors who are reverting changes to the article), tendentious editing, and tendentious discussion on the talk page.  I am sure that some of the editors have read the dispute resolution policy.  The remaining editors should read the dispute resolution policy.  It says that the first step is discussion on the article talk page.  That has been tried.  I suggest that they try one of the dispute resolution procedures, such as the dispute resolution noticeboard or a formal Request for Mediation.  The current content dispute, and not an old deletion discussion, is the current issue.  Follow dispute resolution.  Robert McClenon (talk) 23:02, 5 February 2015 (UTC)
 * I posted a statement to that effect on the talk page. Robert McClenon (talk) 23:11, 5 February 2015 (UTC)
 * You could request Deletion Review, or could file a new Articles for Deletion request, but that doesn't seem to be what you are asking, because you say that you don't want the article deleted but improved. Robert McClenon (talk) 23:22, 5 February 2015 (UTC)

Does it violate WP:CANVAS to...
...invite all previous contributors to a poorly-formatted noticeboard discussion to comment on a more concrete proposal that was made? Everyone else agreed with me. If some of the other users had disagreed with me I would almost certainly be forgiven for contacting all previous commenters, but since they all agreed with me it would look suspicious. And sorry for posting logged out. I'm trying to be discrete so that THIS post doesn't come across as canvassing. Examining this IP's edit history should make my account obvious, though, so those who want to can still check. <IP_ADDRESS> (talk) 12:56, 5 February 2015 (UTC)
 * This isn't the easiest question to dig apart... If I understand you correctly, you're suggesting that you might invite all participants from your AfD discussion of 4 October 2014 to comment at ANI, right? If that's the case then I don't think that would be construed as canvassing. Several of the commenters at AfD disagreed with you on the proposed deletion even though they agreed with you regarding the state of the article. As long as you invited them all to discuss the proposal I don't see any harm in it. -Thibbs (talk) 14:11, 7 February 2015 (UTC)
 * You may wish to use Wikipedia's IRC or email a neutral admin related to the matter if you are concerned. -Thibbs (talk) 14:12, 7 February 2015 (UTC)

Watchlist
Has something changed? Or did I change my preferences without knowing? Before, when I would edit a random article, it would automatically go on my watchlist. I noticed that over the past few days that has not happened. . Buster Seven   Talk  12:56, 5 February 2015 (UTC)

 * Probably the latter. This is controlled by an option in the Watchlist tab in Special:Preferences.  There's some (fairly terse) documentation at Help:Watchlist. —Cryptic 13:05, 5 February 2015 (UTC)
 * Thank you. . Buster Seven   Talk  13:31, 5 February 2015 (UTC)

ENTRY Name Change, Language Change and Content Change All Change!
The Entry for Teofilo Alvarez is out of date, incorrect and incompelte I want to re-submit this article under his known name of "Teofilo Alvarez Alvarez"and to change the language from Spanish to English in the first instance. How can I acheive this? — Preceding unsigned comment added by Tofiglenn (talk • contribs) 15:40, 5 February 2015 (UTC)

 * This is the help desk for English-language Wikipedia, which has no article for Teofilo Alvarez. You may be able to create one. If there are errors in an article on Spanish-language Wikipedia, you can go there and correct them. Maproom (talk) 16:09, 5 February 2015 (UTC)

First Women IPS officer INDIA is Late. Surjit Kaur NOT Kiran Bedi.
http://en.wikipedia.org/wiki/Kiran_Bedi As you described KIRAN BEDI as first woman IPS officer but the truth is that the first women IPS officer of INDIA was Late. Mrs. SURJIT KAUR as described in Newspaper as Shown below:- — Preceding unsigned comment added by <IP_ADDRESS> (talk) 16:35, 5 February 2015 (UTC)
 * Edit requests go on the talk page of the article, in this case Talk:Kiran Bedi. As this concerns a biography of a living person, please discuss it on the talk page before making any changes. It seems unlikely to change though; the "newspaper" appears to be a hoax.-- Joshua Say "hi" to me!What I've done? 16:56, 5 February 2015 (UTC)

hi I cant login after Wikipedia went down and then came back up
--<IP_ADDRESS> 17:59, 5 February 2015 (UTC) — Preceding unsigned comment added by <IP_ADDRESS> (talk)
 * same here <IP_ADDRESS> (talk) 18:02, 5 February 2015 (UTC)
 * Working for me, although Twinkle seems to be down. What error messages are you getting, if any? What happens when you try to log on? Tried clearing your cache?  Я ehevkor ✉  18:04, 5 February 2015 (UTC)
 * There was a power outage moments ago and this is a fallout from it. Should be coming back to normal now. --Glaisher (talk) 18:07, 5 February 2015 (UTC)
 * I did experience some problems at about this time also. If there was a power loss, it would cause various sorts of problems.  Robert McClenon (talk) 22:50, 5 February 2015 (UTC)

Access to account
Hi is there any means to find out who looged in or tried to log into my acount within the last few hours? Ip adresses etc?--Catflap08 (talk) 19:10, 5 February 2015 (UTC)

 * Read the information here on contacting a CheckUser. RegistryKey(RegEdit) 14:17, 6 February 2015 (UTC)

Help:Cite errors/Cite error ref no input
Re article http://en.wikipedia.org/wiki/Palmer's_College This article requires the latest OFSTED inspection results I have created them but there's a CITE error "ref no input" The section to be added is "2013 OFSTED report. The PDF for the 2013 OFSTED report is file:///C:/Documents%20and%20Settings/les%20bailey/My%20Documents/Downloads/130682__2%20(1).PDF

I lack the skill to format the ref and I've tried to copy/paste the 2007 report ref and merely change the inspection number to 423382 but that clearly hasn't worked. — Preceding unsigned comment added by Mr AntiSpin (talk • contribs) 19:10, 5 February 2015 (UTC)

 * As noted on the linked help page, you have  with no content. --  Gadget850talk 19:21, 5 February 2015 (UTC)

request for correction of errors and defamation
For some time you have been disseminating false and defamatory information about myself Alen J Salerian M.D.. Your many  intelligent high-tech methods  have stonewalled my efforts to correct the errors. I'm a human being with limited technical and financial resources. You MUST ensure that this misinformation will not continue to harm myself and my family. Following are some of the errors. I worked for the FBI for five years not one. I did not leak any confidential information about Mr. Robert Hansen. I did not violate his confidence. The comments I've made in public were authorized by Mr. Hansen verbally. Mr. Hansen himself had broadcasted his sexual adventures through Internet for many years. Mr. Cacheris never hired me as a psychiatric consultant. I volunteered my services directly for Mr. Henson and his family and did not get paid a penny. It is not true that I was suspended by Washington psychiatric Society or American psychiatric Association. After lengthy hearings I was fully exonerated and I remain to be a life member of APA. I had to file for bankruptcy because DC Department of Health without due process shutdown my office and the administrative judge, Judge Dean never ruled on the lawfulness of the office closure. It is also true that the DC of medicine based upon false information and proven evidence of no wrongdoing on my part in the death of Mr. Patrick Kennedy made a dumb mistake by revoking my license. Their dumbness does not reflect on my competence. Please make all the necessary corrections.

Respectfully Alen J Salerian MD

Cc: Prof. Jim Fetzer Justin Salerian MD Judith Salerian Gregory Salerian LCSW Ara Salerian Chloe Salerian Glen Donath David Sanford Jennifer Loeb Nick Thomas Aubrey Smith Sen. Ron Paul

Sen. Mikulski — Preceding unsigned comment added by Alensalerian (talk • contribs) 19:45, 5 February 2015 (UTC)

 * Convenience link:  Dismas |(talk) 20:30, 5 February 2015 (UTC)
 * Two editors have already responded on the article's talkpage. Please keep content disputes to the article talkpage, or appropriate WP:dispute resolution venues if a talkpage discussion can't resolve your concerns. See also WP:BLP for the additional restrictive policy, when information about living persons is affected. GermanJoe (talk) 20:47, 5 February 2015 (UTC)

 * The noticeboard for biographies of living persons issues is an appropriate forum for the subjects of biographies to raise issues about articles about them. Robert McClenon (talk) 22:48, 5 February 2015 (UTC)

Obituary or Profile on model April Joyce Paulin
I would like to provide you with the profile of an historic American fashion model. How do I do this? — Preceding unsigned comment added by <IP_ADDRESS> (talk) 21:41, 5 February 2015 (UTC)

 * You can do this through the Articles for Creation process. Dismas |(talk) 22:42, 5 February 2015 (UTC)
 * That said, a quick Google search for variations of "April Joyce Paulin" followed by the word "model" don't return enough hits to even verify that she existed, much less leading me to believe she was/is historic. Are you sure you have the right name?  Dismas |(talk) 22:53, 5 February 2015 (UTC)

Dr. April Joyce Paulin, a.k.a. April Paul
Dr. April Joyce Paulin was born, April Joyce Lapland, March 31, 1933 in Grand Rapids, Michigan.

On November 22, 2014, April Paulin succumbed to a staff infection sustained at Saint Luke's Hospital in Newburgh New York.

April Lapland moved from Michigan to Manhattan in the late 50's where she immediately began working as a model for artists at: The Art Student's League, The Society of Illustrators, and The School of Visual Arts. It was through these institutional bookings that she was referred to working artists, soon becoming the Nation's top model to the world of Fashion Illustration earning $80,000-plus a year.

Paul Wagner, founder of ZOLI MODEL MANAGEMENT in Manhattan told April to change her last name, and so she became known professionally as April Landis.

April Landis was booked full time, seven days a week by artists such as: Tod Draz, Kenneth Paul Block, Richard Ely, Ed Kurtzman, Jane Bixby, Joe Eula, Frank Paulin, Steven Stipelman, Fred Greenhill, Dorothy Hood, Jim Howard, Morton Kaish, Esther Larsen, Jack Potter, Antonio Lopez, and Dora Mathiew to name a few.

While modeling for a National car show, April met Garrison Sheldon Paul, of Afton, Minnesota. They were married June 30, 1962 in Stillwater Minnesota. He followed her to Manhattan where he went to work for the Chrysler Corporation. Garrison Sheldon Paul died at age 53 on Saturday March 13, 1988 in Merced, California.

April Paul continued to model through the 1990's. By this time she was a legend for her ability to hold her famous "walking poses" for long periods of time. SEE: the monograph, "DRAWING FASHION, The Art of Kenneth Paul Block", designed by Shahid & Company, Pointed Leaf Press.com. Kenneth used April almost exclusively for his entire body of work, as did fine artist Richard Ely. Ely and Kenneth lived three blocks apart on Manhattan's upper West Side.

October 2002, April Paul received her Masters from The City University of New York, becoming a Dr. of Philosophy and Art History. She wrote her dissertation on the painter Byron Brown.

While working as a professor of Art History at The City University of New York, April was hired by Mrs. Chaim Gross to become the Director of The Renee and Chaim Gross Foundation on Laguardia Place.

November 1, 2005, Dr. Paul retired from teaching and as Director of The Renee and Chaim Gross Foundation.

April 6, 2006, April Paul married the illustrator and Fine Art Photographer Frank Paulin, whom she had known and worked for since 1964. Following their honeymoon in Paris, the Paulin's searched for a home outside Manhattan and eventually moved to New Windsor, New York. — Preceding unsigned comment added by <IP_ADDRESS> (talk) 23:00, 5 February 2015 (UTC)

 * As it stands, the text above would not be acceptable for a Wikipedia article, because it is not referenced. Every single piece of information in a Wikipedia article should be individually referenced to a reliable source. --ColinFine (talk) 23:32, 5 February 2015 (UTC)


text:
Emergency medical responder (EMR)/Critical interventions/Pulseless electrical activity (PEA)

A condition in which an electrical rhythm remains in the heart but the heart fails to pump. Pulseless eletrical activity (PEA) is also known by its older term electromechanical dissociation. PEA generally occurs secondary to several cardiopulmonary emergencies, such as pulmonary emboli with subsequent hypoxia, acute myocardial infarction (AMI), Congestive heart failure (CHF) exaperation, or trauma to the heart and/ or pleural space resulting in rupture of the heart or fluid build up around the heart (cardiac tamponade).


text:
Alþingishúsið

Etymology
From, the genitive singular of + , the definite nominative singular of. Literally meaning "the house of Althing" or "the house hosting the Icelandic parliament".

Noun

 * 1) the Icelandic parliament house

title: Alþingishúsið


text:
Thomas of Hvar

Tommaso Tommasini (Toma Tomasini; died in early 1463), better known as Thomas of Hvar (Toma Hvarski/Тома Хварски), was Bishop of Lesina (Hvar) from 23 December 1429 until his death, as well as permanent papal legate to the Kingdom of Bosnia from 1439 until 1461.

Thomas was Venetian by birth, but he "must have known Slavic" both through his episcopate on the Croat-inhabited island and through his prolonged contact with Bosnians. He significantly influenced the relations between the Holy See and Bosnia, as well as papal views on the indigenous Bosnian Church. Still, little is known about his personality, politics, activity in the kingdom or relations with Bosnian Franciscans. John Van Antwerp Fine, Jr. argues that Thomas deliberately misinformed the Papacy about the Bosnian Church, fabricating claims of dualism.

Bishop Thomas of Hvar probably approached his namesake, King Thomas of Bosnia, in 1443, when Pope Eugene IV hoped to draw Bosnia into the Crusade of Varna. He probably discussed the Catholic Church's issue with heresy in Bosnia at that time. In 1446, he converted the King himself from Bosnian Christianity to Catholicism.

title: Thomas of Hvar


text:
Wikipedia:WikiProject Spam/Local/adorablesilkroute.com

Links

 * adorablesilkroute.com resolves to [//<IP_ADDRESS> <IP_ADDRESS>]
 * Link is not on the blacklist.
 * Link is not on the domainredlist.
 * Link is not on the Monitorlist.
 * None of the mentioned users is on the blacklist.
 * Link is not on the whitelist.
 * Link is not on the monitor list.
 * Link is not on the whitelist.
 * Link is not on the monitor list.

Selected additions

 * Displayed 2 additions out of 2 total.	 For more info see WikiProject_Spam/LinkReports/adorablesilkroute.com

Entry
Log entry for the MediaWiki:Spam-blacklist:

\badorablesilkroute\.com\b  # ADMINNAME # see  [[Wikipedia:WikiProject_Spam/Local/adorablesilkroute.com ]]

Discussion
See COIBot report for more details.

New data reported. --COIBot (talk) 09:28, 18 August 2020 (UTC) Autostale: very old local report (>7 days). No links left in here mentioned edits. Marked stale. . --COIBot (talk) 11:34, 18 August 2020 (UTC)


text:
assolo

Etymology 1
.

Noun

 * 1) solo, :
 * 2)  a piece of music for one performer
 * 3)  a job or performance done by one person alone

Etymology
From.

Verb

 * 1)  to level to the ground, destroy, raze

title: assolo


text:
Muriel Wright

Muriel Wright may refer to:

 * Muriel Hazel Wright (1889–1975), American educator and historian
 * Muriel Wright, mistress of British author Ian Fleming

title: Muriel Wright


text:
2022–23 UEFA Europa League

The 2022–23 UEFA Europa League was the 52nd season of Europe's secondary club football tournament organised by UEFA, and the 14th season since it was renamed from the UEFA Cup to the UEFA Europa League.

Sevilla defeated Roma in the final played at the Puskás Aréna in Budapest, Hungary, 4–1 on penalties following a 1–1 draw after extra time, winning the competition for a record-extending seventh time. Budapest was originally scheduled to host the final match for the 2021–22 UEFA Europa League, but several hosts were shifted because of the delay and ultimate relocation of the 2020 final due to the COVID-19 pandemic.

As winners of the tournament, Sevilla automatically qualified for the 2023–24 UEFA Champions League group stage and also earned the right to play against the winners of the 2022–23 UEFA Champions League, Manchester City, in the 2023 UEFA Super Cup.

As the title holders, Eintracht Frankfurt qualified for the 2022–23 UEFA Champions League. They were unable to defend their title after advancing to the knockout phase, and were eliminated by Napoli in the first knockout round.

Association team allocation
A total of 57 teams from 33 of the 55 UEFA member associations participated in the 2022–23 UEFA Europa League. Among them, 15 associations had teams directly qualifying for the Europa League, while for the other 40 associations that did not have any teams directly qualifying, 18 of them had teams playing after being transferred from the Champions League (the only member associations which could not have a participant were Russia and Liechtenstein, which did not organise a domestic league, and could only enter their cup winner into the UEFA Europa Conference League given their association ranking). The association ranking based on the UEFA country coefficients was used to determine the number of participating teams for each association:
 * The title holders of the UEFA Europa Conference League were given an entry in the Europa League (as they did not qualify for the Champions League group stage).
 * Associations 1–5 each had two teams qualify.
 * Associations 6–7 and 9–15 each had one team qualify.
 * 36 teams eliminated from the 2022–23 UEFA Champions League were transferred to the Europa League.

Association ranking
For the 2022–23 UEFA Europa League, the associations were allocated places according to their 2021 UEFA country coefficients, which took into account their performance in European competitions from 2016–17 to 2020–21.

Apart from the allocation based on the country coefficients, associations may have had additional teams participating in the Europa League, as noted below:
 * (UCL) – Additional teams transferred from the UEFA Champions League
 * (UECL) – Additional berth for UEFA Europa Conference League title holders

Distribution
The following is the access list for this season.

Due to the suspension of Russia for the 2022–23 European season, the following changes to the access list were made:

 * The cup winners of associations 13 (Turkey) and 14 (Denmark) enter the play-off round instead of the third qualifying round.
 * The cup winners of association 16 (Serbia) enter the third qualifying round instead of the Europa Conference League second qualifying round.

Since the Europa Conference League title holders (Roma) qualified through their league position, the following changes to the access list were made:

 * The cup winners of association 7 (Netherlands) enter the group stage instead of the play-off round.
 * The cup winners of association 15 (Cyprus) enter the play-off round instead of the third qualifying round.
 * The cup winners of association 17 (Czech Republic) enter the third qualifying round instead of the Europa Conference League second qualifying round.

Redistribution rules
A Europa League place was vacated when a team qualified for both the Champions League and the Europa League, or qualified for the Europa League by more than one method. When a place was vacated, it was redistributed within the national association by the following rules:
 * When the domestic cup winners (considered as the "highest-placed" qualifier within the national association with the latest starting round) also qualified for the Champions League, their Europa League place was vacated. As a result, the highest-placed team in the league which had not yet qualified for European competitions qualified for the Europa League, with the Europa League qualifiers which finished above them in the league moved up one "place".
 * When the domestic cup winners also qualified for the Europa League through league position, their place through the league position was vacated. As a result, the highest-placed team in the league which had not yet qualified for European competitions qualified for the Europa League, with the Europa League qualifiers which finished above them in the league moved up one "place" if possible.
 * For associations where a Europa League place was reserved for either the League Cup or end-of-season European competition play-offs winners, they always qualified for the Europa League as the "lowest-placed" qualifier. If the League Cup winners had already qualified for European competitions through other methods, this reserved Europa League place was taken by the highest-placed team in the league which had not yet qualified for European competitions.

Teams
The labels in the parentheses show how each team qualified for the place of its starting round:
 * ECL: Europa Conference League title holders
 * CW: Cup winners
 * 4th, 5th, etc.: League position of the previous season
 * Abd-: League positions of abandoned season as determined by the national association; all teams were subject to approval by UEFA
 * UCL: Transferred from the Champions League
 * GS: Third-placed teams from the group stage
 * CH/LP PO: Losers from the play-off round (Champions/League Path)
 * CH/LP Q3: Losers from the third qualifying round (Champions/League Path)
 * CH/LP Q2: Losers from the second qualifying round (Champions/League Path)

The third qualifying round was divided into Champions Path (CH) and Main Path (MP).

CC: 2022 UEFA club coefficients.

Notes

Schedule
The schedule of the competition was as follows. Matches were scheduled for Thursdays apart from the final, which took place on a Wednesday, though exceptionally could take place on Tuesdays or Wednesdays due to scheduling conflicts. Scheduled kick-off times starting from the group stage were 18:45 and 21:00 CEST/CET, though exceptionally could take place at 16:30 due to geographical reasons.

As the 2022 FIFA World Cup took place in Qatar between 20 November and 18 December 2022, the group stage commenced in the first week of September 2022 and concluded in the first week of November 2022 to make way for the World Cup.

The draws for the qualifying round were held at the UEFA headquarters in Nyon, Switzerland. The group stage draw took place in Istanbul, Turkey.

Group stage
The draw for the group stage was held on 26 August 2022. The 32 teams were drawn into eight groups of four. For the draw, the teams were seeded into four pots, each of eight teams, based on their 2022 UEFA club coefficients (CC). Teams from the same association could not be drawn into the same group.

Bodø/Glimt, Nantes, Union Berlin and Union Saint-Gilloise made their debut appearances in the group stage. Union Saint-Gilloise made their debut appearance in a UEFA competition group stage.

A total of 23 national associations were represented in the group stage.

Knockout phase
In the knockout phase, teams played against each other over two legs on a home-and-away basis, except for the one-match final.

Statistics
Statistics exclude qualifying round and play-off round.

Team of the season
The UEFA technical study group selected the following players as the team of the tournament.

Player of the Season

 * 🇪🇸 Jesús Navas ( Sevilla)

Young Player of the Season

 * 🇩🇪 Florian Wirtz ( Bayer Leverkusen)

title: 2022–23 UEFA Europa League


text:
riisuminen

Noun

 * 1) taking off
 * 2) undressing, stripping the act of undressing someone or taking someone's clothes off
 * 1) undressing, stripping the act of undressing someone or taking someone's clothes off
 * 1) undressing, stripping the act of undressing someone or taking someone's clothes off

title: riisuminen


text:
File:ASL-model-apllicationserviceslibrary.jpg

I've compiled this model myself, based on the information from the ASL site, see also the Application Services Library page Sybren 14:37, 11 August 2006 (UTC)