# Tag Info

18

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory. An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with ...

16

Here is an array: A[0] = Alice A[1] = Bob A[2] = Charlie Here 0,1,2 are indices. Now suppose that we want to know which index contains a given word. Then we use a dictionary: D[Alice] = 0 D[Bob] = 1 D[Charlie] = 2 This is an inverted index (according to your Wikipedia quote). The word index has different meaning in different contexts: Technical books ...

13

Group theory is indeed useful in algorithm design. For example, matrix multiplication is a fundamental problem for which such approaches have been used (see e.g., Cohn et al. [1] or these lecture notes). There are also algebraic algorithms for other problems in e.g., graph theory (Hamiltonian path/cycle, graph motif, and various other path problems) based on ...

9

The reason why we use the term "inverted index" is that the term "index" came to computer science first. In fact, it has several common meanings in computer science, but in this case it refers to the more general concept of an efficient lookup data structure for a database. What we call an "inverted index" is, strictly speaking, ...

8

The theory of continuous groups underlies a lot of modern computer graphics and computer vision, because Lie group theory is one of the more natural representations of a space of transformations. Also, Galois theory is one of the workhorses of modern computer algebra systems.

6

Symmetry in combinatorial optimization. An important group-theoretic algorithm often applied in theoretical computer science is Buchberger's algorithm.

5

Category Theory If you accept Category Theory as a kind of generalization of groups, then we can conclude that modern type theory as related to the design of programming languages absolutely depends on it. For instance, take a look at this Q & A. Also, structures within programming languages, such as monads, are also categories.

5

For the first fact, consider the array $1,\ldots,n,n+1,\ldots,2n$. Sorting its two halves doesn't alter the array. When the two halves are merged, the element $n+1$ would be compared against all elements in the left half. The second fact is true for every $O(n\log n)$ sorting algorithm: such an algorithm performs $O(n\log n)$ comparisons overall, and so $O(\... 5 I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children. To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know ... 4 Suppose that$f(n) = O(n^{\log_b a - \epsilon})$. According to the definition, there exist constants$N,C>0$such that$f(n) \leq Cn^{\log_b a - \epsilon}$for all$n \geq N$. Let$M$be the maximum value of$f(n)/n^{\log_b a - \epsilon}$over all positive integers$n < N$. The maximum exists since there are only finitely many such$n$. Then$f(n) \leq ...

3

GCC C++ case study Let's also get some insight from one of the most important implementations in the world. As we will see, it actually matches out theory perfectly! As shown at https://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c/51944661#51944661, in GCC 6.4: std::map uses BST std::unordered_map uses hashmap ...

3

To give a yet another example, constraint satisfaction problems can be solved with a semiring formalism, using pretty much schoolbook algebra and lattices. Also, any machine integers are a special case of a residue arithmetic, which is basically, $Z/nZ$. That's not mentioning all the computer algebra. And formal "muscle" from undergrad algebra ...

3

Dijkstra shortest path algorithm relies heavily on algebraic properties of the way you compare/combine paths (we call it the algebra in this case). Network routing algorithms often use veresions of Dijkstra'a algorithm which are based on a different algebra, and their correctness is guaranteed by the algebraic properties of the compare/combine laws. You can ...

3

Method 1 You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$. When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over ...

3

I suggest the longest increasing subsequence problem: Given an input sequence of length $n$, find the length of the longest increasing subsequence in the input sequence. A naive dynamic programming-based formulation will lead to an $O(n^2)$ running time. The Wikipedia link provided above uses a binary search-based formulation to speed it up to $O(n \log n)$-...

3

It sounds like you found the answer yourself, you are describing Vertex Cover, which in many ways are very similar to Independent Set, both problems are NP-complete. The relation to Independent Set is that in a graph $G = (V,E)$, a set $S$ is a minimal vertex cover if and only if $V \setminus S$ is a maximal independent set. If you know that Independent Set ...

3

3

In terms of notation: Isn't XSD exactly what you are looking for? (barring all the "severe criticism" ...). Also not sure if you are looking for a notation convenient to hand-write, that's certainly NOT XML :-). Typedefs and preserves seem to have more of a mathematical basis, perhaps closer to what you are looking for. A related HN thread. I ...

3

It's Relative The distinction is between "keys" and "values". However, what counts as a "key" vs. a "value" depends on the maintainer. Consider a phone book. Most people would keep a phone book around because they know the name of someone they wish to call, but don't know their phone number. Thus, the book is ...

3

I think you can handle single-word modifications in $O(d \log n)$ time, where $d$ (density) is the maximal number of words in a line, which is hopefully small for any reasonable $A$ and fixed $W$. Let's take one of your sentences as an example. We want it to be wrapped with $W = 30$ characters like this: I'm looking for an algorithm and datastructure that ...

3

The convex hull of 10 collinear points is the line segment between the two extreme points. No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a line, a convex polygon, a circular sector, a half plane, a cubic, etc. . A definition in math, such as the definition of convex hull, is the strictest kind of ...

3

$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k<n/3$ or $\ge2k+1>2n/3$. A version suitable for all $n$ can be proved as follows. Let $\... 3 Let$s_i$,$e_i$,$x_i$, be the shift start time, shift end time, and experience of the$i$-th worker. For each worker define the following two events: A shift-start event is a triple$(s_i, 0, i)$. A shift-end event is a triple$(e_i, 1, i)$. Collect all events in an array$E$and sort it in increasing order (lexicographically). This requires$O(w \log w)$... 3 State machines and databases are quite different entities, and their usage (or functionality) is very different. In this answer, I'll just try to separate them with respect to the similarity you mention. This is by no means a comprehensive description of neither state machines nor databases. The states of a state machine can indeed be thought of as ... 3 Show by induction on the height$h$of the tree that a tree of height$h$has at least$2^{\frac{h}{2}}$nodes. The base case$h=0$is easy since a tree of height$0$has$1$vertex and$1 \ge 2^\frac{0}{2}$. Suppose that the claim holds up to some$h \ge 0$. Consider a tree$T$with height$h+1$rooted in$r$. Let$u$and$v$be the children of$r$. Let$n(...

3

Your random number generator might not be able to produce all numbers. Without looking at Math.Random, if it returned an integer then it would never match 0.123456. If it returned a double precision floating point number 0 <= rnd < 1, it might produce a 53 bit integer from 0 to 2^53-1, and multiply by 2^-53. In this case it is quite possible that 0....

3

You can use a disjoint sets data structure to quickly solve your problem (exercise). This can be further improved by exploiting the particular nature of your problem. We maintain a list of intervals $[a_1,b_1],[a_2,b_2],\ldots$ which succinctly represent the integers seen so far. In addition, we store $a_i,b_i$ in a hash table. Given a new integer $c$, we ...

3

For any pair of adjacent strings, you can find a constraint of the form $\sigma < \tau$ on the order of the symbols which is necessary in order for this pair of strings to be lexicographically ordered. This doesn't require any fancy data structure. Putting all of these constraints together in a directed graph, you can determine whether such an order ...

2

Depending on your intended use, it might not be practical to use counters, e.g. integers instead of bits, but by doing so, you can increment each integer in the array instead of setting a bit when inserting. When removing an element, you can then decrement all of its related integers.

2

I would say it depends on the application and target architecture. Usually the x86 is the main target, but practices used there might not transfer well into a embedded domain. Other architectures (usually RISC) have large amount of registers, AVR has 32 registers 8-bits each and it's possible use finer granularity as some instructions have bit wise ...

Only top voted, non community-wiki answers of a minimum length are eligible