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}...
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}^{...
13
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$
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 ...
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
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
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'
39.8k7 gold badges105 silver badges170 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
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
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
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
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 ...
6
As a practical matter, how you treat data structures mathematically largely depends what you're trying to do.
For example, suppose that you're trying to reason about the correctness of programs that use stacks and/or queues. In that situation, you'd want to treat the stack/queue as an abstract object, and axiomatise its properties. So you develop (say) a ...
6
I find it surprising and unfortunate that you didn't get to study algorithms and discrete math more in your university studies. As you seem to have realized, a person can know how to code, but without math, won't be able to solve really interesting problems.
Unfortunately there is no "Learn all algorithms you'll ever need in 21 days for dummies" book. There ...
6
Let $f(n)=\sqrt{T(n)}$, $f$ satisfies the linear recurrence relation $f(n)=f(n-1)+2f(n-2)$. The characteristic polynomial is $x^2-x-2$ and it's roots are $-1,2$, so $f(n)$ is a linear combination of $(-1)^n,2^n$. After substituting the initial conditions you get $f(n)=\frac{1}{3}(-1)^n+\frac{2}{3}2^n$.
6
It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".
For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language ...
6
First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a single problem as any single problem can be solved in $O(1)$!
That said, there is a notable class of ILP's that is known to be polynomial time solvable. This ...
6
You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a longest path that does not contain $v$.
Easy to see the length of the longest path is 10. For convenience, let's encode the vertices as follows.
1
2
...
Only top voted, non community-wiki answers of a minimum length are eligible
