|
Sorting Number
In mathematics and computer science, the sorting numbers are a sequence of numbers introduced in 1950 by Hugo Steinhaus for the analysis of comparison sort algorithms. These numbers give the worst-case number of comparisons used by both binary insertion sort and merge sort. However there are other algorithms that use fewer comparisons. Formula and examples The nth sorting number is given by the formula :n\,S(n)-2^+1 where :S(n)=\lfloor 1 + \log_2 n \rfloor. The sequence of numbers given by this formula (starting with n=1) is :0, 1, 3, 5, 8, 11, 14, 17, 21, 25, 29, 33, 37, 41, ... . The same sequence of numbers can also be obtained from the recurrence relation :A(n) = A\bigl(\lfloor n/2\rfloor\bigr)+A\bigl(\lceil n/2\rceil\bigr)+n-1. It is an example of a 2-regular sequence. Asymptotically, the value of the nth sorting number fluctuates between approximately n\log_2 n-n and n\log_2 n-0.915n depending on the ratio between n and the nearest power of two. Application to sorting In ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hugo Steinhaus
Hugo Dyonizy Steinhaus ( ; ; January 14, 1887 – February 25, 1972) was a Polish mathematician and educator. Steinhaus obtained his PhD under David Hilbert at Göttingen University in 1911 and later became a professor at the Jan Kazimierz University in Lwów (now Lviv, Ukraine), where he helped establish what later became known as the Lwów School of Mathematics. He is credited with "discovering" mathematician Stefan Banach, with whom he gave a notable contribution to functional analysis through the Banach–Steinhaus theorem. After World War II Steinhaus played an important part in the establishment of the mathematics department at Wrocław University and in the revival of Polish mathematics from the destruction of the war. Author of around 170 scientific articles and books, Steinhaus has left his legacy and contribution in many branches of mathematics, such as functional analysis, geometry, mathematical logic, and trigonometry. Notably he is regarded as one of the early found ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Merge-insert Sort
In computer science, merge-insertion sort or the Ford–Johnson algorithm is a comparison sorting algorithm published in 1959 by L. R. Ford Jr. and Selmer M. Johnson. It uses fewer comparisons in the worst case than the best previously known algorithms, binary insertion sort and merge sort, and for 20 years it was the sorting algorithm with the fewest known comparisons. Although not of practical significance, it remains of theoretical interest in connection with the problem of sorting with a minimum number of comparisons. The same algorithm may have also been independently discovered by Stanisław Trybuła and Czen Ping. Algorithm Merge-insertion sort performs the following steps, on an input X of n elements: #Group the elements of X into \lfloor n/2\rfloor pairs of elements, arbitrarily, leaving one element unpaired if there is an odd number of elements. #Perform \lfloor n/2\rfloor comparisons, one per pair, to determine the larger of the two elements in each pair. #Recursively s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
American Mathematical Monthly
''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an expository journal intended for a wide audience of mathematicians, from undergraduate students to research professionals. Articles are chosen on the basis of their broad interest and reviewed and edited for quality of exposition as well as content. In this the ''American Mathematical Monthly'' fulfills a different role from that of typical mathematical research journals. The ''American Mathematical Monthly'' is the most widely read mathematics journal in the world according to records on JSTOR. Tables of contents with article abstracts from 1997–2010 are availablonline The MAA gives the Lester R. Ford Awards annually to "authors of articles of expository excellence" published in the ''American Mathematical Monthly''. Editors *2022– ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science (journal)
''Theoretical Computer Science'' (TCS) is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index. According to the Journal Citation Reports, its 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citations of articles published in the last two years in a given journal, as i ... is 0.827. References Computer science journals Elsevier academic journals Publications established in 1975 {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electronic Journal Of Combinatorics
The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Georgia Institute of Technology). The Electronic Journal of Combinatorics is a founding member of the Free Journal Network. According to the ''Journal Citation Reports'', the journal had a 2017 impact factor of 0.762. Editors-in-chief Current The current editors-in-chief are: * Maria Axenovich, Karlsruhe Institute of Technology, Germany * Miklós Bóna, University of Florida, United States * Julia Böttcher, London School of Economics, United Kingdom * Richard A. Brualdi, University of Wisconsin, Madison, United States * Eric Fusy, CNRS/LIX, École Polytechnique, France * Catherine Greenhill, UNSW Sydney, Australia * Brendan McKay, Australian National University, Australia * Bojan Mohar, Simon Fraser University, Canada * Marc Noy, Universitat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Layered Permutation
In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations. One of the earlier works establishing the significance of layered permutations was , which established the Stanley–Wilf conjecture for classes of permutations forbidding a layered permutation, before the conjecture was proven more generally. Example For instance, the layered permutations of length four, with the reversed blocks separated by spaces, are the eight permutations :1 2 3 4 :1 2 43 :1 32 4 :1 432 :21 3 4 :21 43 :321 4 :4321 Characterization by forbidden patterns The layered permutations can also be equivalently described as the permutations that do not contain the permutation patterns 231 or 312. That is, no three elements in the permutation (regardless of whether they are consecutive) have the same ordering as either of these forbidden triples. Enumeration A layered permutation on the nu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Superpattern
In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a ''k''-superpattern contains all possible patterns of length ''k''. Definitions and example If π is a permutation of length ''n'', represented as a sequence of the numbers from 1 to ''n'' in some order, and ''s'' = ''s''1, ''s''2, ..., ''s''''k'' is a subsequence of π of length ''k'', then ''s'' corresponds to a unique ''pattern'', a permutation of length ''k'' whose elements are in the same order as ''s''. That is, for each pair ''i'' and ''j'' of indexes, the ''i''th element of the pattern for ''s'' should be less than the ''j''the element if and only if the ''i''th element of ''s'' is less than the ''j''th element. Equivalently, the pattern is order-isomorphic to the subsequence. For instance, if π is the permutation 25314, then it has ten subsequences of length three, for ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Worst-case Analysis
The worst-case analysis regulation40 CFR 1502.22 was promulgated in 1979 by the US Council on Environmental Quality (CEQ). The regulation is one of many implementing the National Environmental Policy Act of 1969 and it sets out the formal procedure a US government agency must follow when confronted with gaps in relevant information or scientific uncertainty about significant adverse effects on the environment from a major federal action Major (commandant in certain jurisdictions) is a military rank of commissioned officer status, with corresponding ranks existing in many military forces throughout the world. When used unhyphenated and in conjunction with no other indicator .... Synopsis The regulation requires an agency to make known when it is confronted with gaps in relevant information or scientific uncertainty. The agency then must determine if the missing information is essential to a reasoned choice among the alternatives. When the missing information is material to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Selmer M
Selmer may refer to: * Selmer (surname) * Selmer (given name) * Selmer, Tennessee, United States, a town * Selmer group, a group constructed from an isogeny of abelian varieties See also * Conn-Selmer, a manufacturer and distributor of musical instruments * Henri Selmer Paris Henri Selmer Paris is a French enterprise, manufacturer of musical instruments based at Mantes-la-Ville near Paris. Founded in 1885, it is known as a producer of professional-grade woodwind and brass instruments, especially saxophones, clarinet ..., a musical instrument manufacturer, associated with Conn-Selmer * Semler, a surname {{disambiguation ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Comparison Sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list. The only requirement is that the operator forms a total preorder over the data, with: # if ''a'' ≤ ''b'' and ''b'' ≤ ''c'' then ''a'' ≤ ''c'' (transitivity) # for all ''a'' and ''b'', ''a'' ≤ ''b'' or ''b'' ≤ ''a'' ( connexity). It is possible that both ''a'' ≤ ''b'' and ''b'' ≤ ''a''; in this case either may come first in the sorted list. In a stable sort, the input order determines the sorted order in this case. A metaphor for thinking about comparison sorts is that someone has a set of unlabelled weights and a balance scale. Their goal is to line up the weights in order by their weight without any information except that obtained by placing two weights on the scale and seeing which one i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Power Of Two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent. In a context where only integers are considered, is restricted to non-negative values, so there are 1, 2, and 2 multiplied by itself a certain number of times. The first ten powers of 2 for non-negative values of are: : 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, ... Because two is the base of the binary numeral system, powers of two are common in computer science. Written in binary, a power of two always has the form 100...000 or 0.00...001, just like a power of 10 in the decimal system. Computer science Two to the exponent of , written as , is the number of ways the bits in a binary word of length can be arranged. A word, interpreted as an unsigned integer, can represent values from 0 () to () inclusively. Corresponding signed integer values can be positive, negative and zero; see signed n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Asymptotic Analysis
In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as becomes very large, the term becomes insignificant compared to . The function is said to be "''asymptotically equivalent'' to , as ". This is often written symbolically as , which is read as " is asymptotic to ". An example of an important asymptotic result is the prime number theorem. Let denote the prime-counting function (which is not directly related to the constant pi), i.e. is the number of prime numbers that are less than or equal to . Then the theorem states that \pi(x)\sim\frac. Asymptotic analysis is commonly used in computer science as part of the analysis of algorithms and is often expressed there in terms of big O notation. Definition Formally, given functions and , we define a binary relation f(x) \sim g(x) \qu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
