36
For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.
An excellent reference is Analytic Combinatorics by the late Philipe ...
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}...
21
Short answer.
If we formulate an appropriate decision problem version of the Discrete Logarithm problem, we can show that it belongs to the intersection of the complexity classes NP, coNP, and BQP.
A decision problem version of Discrete Log.
The discrete logarithm problem is most often formulated as a function problem, mapping tuples of integers to another ...
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$.
...
17
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 ...
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
Insert real-world predicates and read aloud, for instance:
It can not be both winter and summer (at any point in time).
and
(At any point in time) It is not winter or it is not summer.
Clearly, the two statements are equivalent.
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
If you like to visualize it, use the venn diagrams. See this, for instance.
I find it more simple just to memorize the basic 2 laws: everytime you "break" a negation line, you replace the AND to OR (or vice versa). Adding two negation lines changes nothing (but gives you more "lines" to break). It just works.
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
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:
...
10
There is a whole course being offered by Udacity*, Logic and Discrete Mathematics, which has interactive quizzes and homework assignments.
The course description is as follows:
This course presents key concepts in discrete mathematics, specifically, elementary propositional logic and elements of enumerative combinatorics, elementary number theory, and ...
10
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 ...
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$.
...
9
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 ...
8
In a partially ordered set, there may be members which are not comparable. A partial order where all elements are comparable is called a total order.
We say $a$ and $b$ are comparable when at least one of the following holds:
$a\leq b$,
$b \leq a$.
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
In a partially ordered set (poset for short), you can have $a \le b$ and $a \le c$ without $b$ and $c$ being comparable (i.e. neither $b \le c$ nor $c \le b$ holds). That's what makes it a partial order and not a total order. Mathematicians often mean a total order when say “order”, because the primary example of an ordered set is the real numbers (or ...
answered Mar 25 '12 at 16:58
Gilles 'SO- stop being evil'
37.6k7 gold badges101 silver badges166 bronze badges
7
Generating functions are a very powerful and very useful magic wand. The following solution to the first question (why are there $C_n$ trees) is somewhat less magical. Hence, cute.
Example. To produce a tree of $5$ nodes we start with a sequence in which $+1$ occurs $5+1$ times, and $-1$ occurs $5$ times. For example, $+-++-+--++-$. Among those prefixes ...
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'
37.6k7 gold badges101 silver badges166 bronze badges
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
