27
The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity).
By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid).
By using Rings, we can do ...
25
The issue comes down to ambiguous terminology.
$(a^b)^c = a^{bc}$, but $a^{(b^c)} \neq a^{bc}$. In other words, exponents aren't associative.
Conventionally, nested exponentials without parentheses are grouped in this second way, because it's more useful. So $2^{2^n} = 2^{(2^n)} \neq 2^{2n}$. If we wanted to talk about $(2^2)^n$, we could just write $2^{2n}...
19
I'm assuming that by $n$, you mean the total number of nodes in the binary tree. The height (or depth) of a binary tree is the length of the path from the root node (the node without parents) to the deepest leaf node. To make this height minimum, the tree most be fully saturated (except for the last tier) i.e. if a specific tier has nodes with children, then ...
18
Ok, A bit more detailed answer than in the comments.
Choosing $k$ out of $n$ is done by ${n \choose k} = \frac{n!}{k!(n-k)!}$. So for things like the size of the pizza, where you have 4 options (and you need to choose one, coz pizza cannot be both medium and extra-large at the same times) you have only $4$ options. Indeed, ${4 \choose 1}=\frac{4!}{3!}=4$.
...
16
$a^{(b^c)}$ is not the same as $(a^b)^c$. When people write $2^{2^k}$, they usually mean $2^{(2^k)}$, not $(2^2)^k$.
14
Here are several ways to solve your recurrence relation.
Guessing
Anyone with enough experience in computer science might recognize your recurrence as the one satisfied by $T(n) = 2^n$. Given this guess, you can verify it by summing the appropriate geometric series: if $T(m) = 2^m$ for $m < n$ then
$$
T(n) = 1 + \sum_{m=0}^{n-1} T(m) = 1 + \sum_{m=0}^{...
12
Since I created this I probably can explain it best ;-):
the first step is to calculate an image segmentation which will combine small areas of similar colors into bigger chunks. The tolerance values of that segmentation will influence how big the biggest circles can become (higher tolerance => bigger areas => bigger circles)
You proceed by processing each ...
12
Let me first answer your subquestion: Does the literature on semiautomata ever look at "group-automata"?. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite ...
12
You have mistake in $(2.1)^n \cdot n^2<2^n \cdot n^3$, because it is equivalent $\left(\frac{2.1}{2}\right)^n<n$
11
Monoids are ubiquitous in programming, just that most programmers don't know about them.
Number operations like addition and multiplication.
Matrix multiplication.
Basically all collection-like data structures form monoids, where the monoidal operation is concatenation or union. This includes lists, sets, maps of keys to values, various kinds of trees etc.
...
11
A binary tree has 1 or 2 children at non-leaf nodes and 0 nodes at leaf nodes. Let there be $n$ nodes in a tree and we have to arrange them in such a way that they still form a valid binary tree.
Without proving, I am stating that to maximize the height, given nodes should be arranged linearly, i.e. each non-leaf node should have only one child:
...
11
Barrington's famous theorem reduces computation in NC$^1$ to computing iterated products in the group $S_5$ (or $A_5$, or indeed any non-solvable group). There is also a connection to leakage-resistant computation, in Shielding Circuits with Groups by Miles and Viola (2012).
Regarding the classification of the finite simple groups, as far as I remember it ...
10
For the field of A.I. and machine learning, I would recommend you to explore and learn more about these topics:
Statistics
Probability
Stochastic processes
Bayesian Data Analysis
Convex Optimization
Graph Theory
With your math background, you could easily pick any good machine learning book and learn the required math that you don't have as you go. Kevin ...
10
A famous area of study in the theory of group presentations is the word problem for groups. A group presentation is given by a bunch of generators $g_1, ..., g_m$ and a bunch of equations $a_1 = b_1, ..., a_n = b_n$ that the generated group needs to satisfy. Now given two words $x, y \in \{g_1, ..., g_m\}^*$, i.e. two strings over the alphabet $\{g_1, ..., ...
10
This is known as a one-way permutation. The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements. There are various candidate constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.
9
If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular.
Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$.
For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$.
Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$.
...
8
A course on data structures will not be about "creating data structures". You can expect to analyse data structures, prove various properties of them, and create your own to solve some highly nontrivial problems.
Every single data structure you intend to build must be rigorously defined. Each method on a data structure must be proven rigorously to be ...
8
The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably ...
7
Finite fields come up in many places. Here are just a few examples:
The Razborov-Smolensky polynomial method.
Fourier analysis, as used for example in the proof of the PCP theorem, or fast integer multiplication.
List decoding - codes like Reed-Muller are algebraic codes.
Algebraization, the method used to prove IP=PSPACE.
Elliptic curves over finite fields ...
7
The short answer is no. No quick algorithm for this problem is known.
A big open problem (for at least 50 years) in algebraic graph theory asks about the existence a regular graph of degree 57 order 3250 girth 5 and diameter 2. This is known as a Moore graph.
However, it is known that if such a graph exists its characteristic polynomial has to be $p(x) = ...
7
One important problem in distributed file systems (DFS) is to generate files from distributed blocks. The area of Erasure code from information theory and Algebra (groups, rings, linear algebra,...) is used extensively in distributed fault tolerant file systems for example in HDFS RAID (Hadoop Based File System). Social network and Cloud companies are ...
7
Universities are not in the business of cramming useless info. If what they were teaching wasn't useful, they wouldn't bother. I recommend taking a more accepting attitude to life. If you go to college expecting to learn nothing, this is a self-fulfilling prophecy: you will learn nothing, so college will be wasted and you might as well start flipping burgers ...
answered Sep 20 '13 at 1:03
Gilles 'SO- stop being evil'
39k7 gold badges103 silver badges167 bronze badges
7
Randomized algorithms
If you'll accept a randomized algorithm, yes, it can be done in linear time. There's a randomized algorithm whose expected running time is $O(n)$, and where the probability that it takes longer than $c \cdot n$ time is exponentially small in $c$.
Here's the idea. Randomly permute the entries of $S$, then split it into three equal-...
6
It can be exponential in $n/2$. The following graph has $2^{(n/2) - 1}$ shortest paths between the endpoints:
This graph has $2^{(14/2)-1} = 2^6 = 64$ different shortest path, each corresponding to a selection of "ups" and "downs".
6
The most common definition of xor is $a\oplus b=(a+b)\bmod 2$, on vertices applied to every coordinate seperately of course. In base-10 case, you have to introduce two operations: $a\oplus b=(a+b)\bmod 10$ and $a\ominus b=(a-b)\bmod 10$. (Notice that in base-2 case they coincide). Now you have
$$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\...
6
If your question is
What are examples of groups, monoids, and rings in computation?
then one example I can think of off-hand is for path-finding algorithms in graph-theory. If we define a semiring with $+$ as $\min$ and $\cdot$ as $+$, then we can use matrix multiplication with the adjacency matrix to find all-pairs-shortest-path. This method is ...
6
Solve a linear homogeneous recurrence to obtain the identity $$\sum_{K=0}^n\frac1{a^K}=\begin{cases}\frac{1-1/a^{n+1}}{1-1/a}&\text{if }a\neq1\pmod m\\n+1&\text{if }a=1\pmod m\end{cases}$$ and use efficient algorithms for multiplicative inversion and exponentiation mod $m$.
6
AI is 99% statistics these days. Learn about probability, and how it intersects with graph theory (bayes nets, etc.).
As for cryptography, if you've got number theory, the only real thing I can think of to extend this is group/field theory. In particular, learn about eliptic curves, but I doubt you'd find a math class that taught that that wasn't ...
6
Let $R(s,t)$ be the least integer $k$ such that every graph on $k$ or more vertices contains either a $s$-clique or independent set of size $t.$
It turns out that this number is well defined (called Ramsey number) and the statement in your question merely amount to saying that $$R(t,t) \leq 2^{2t}.$$
A well known upper bound for Ramsey number states $$R(s,...
6
The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$:
$$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$
In your case, $f(i)$ is in fact non-increasing, and in that case we have
$$ \int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx. $$
For example, we ...
Only top voted, non community-wiki answers of a minimum length are eligible
