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$.
15
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
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
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.
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
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-...
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 ...
8
Discrete mathematics, linear algebra, calculus, and probability are all used pretty much everywhere in computer science. Basically, discrete maths is the basis of everything, while linear algebra and calculus are used in specific areas of computer science, and there are various places you will see probability.
Probability is usually used to describe ...
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'
40.9k7 gold badges108 silver badges172 bronze badges
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 ...
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
...
6
See for example Sophie Germain.
Sophie Germain proved that every prime number p with certain properties could be used as an expoonent in Fermat's Last Theorem. She used her theorem to prove that all primes up to 100 would work. Apparently checking her theorem was quite a lot of work because later her theorem was used to check first the primes up to 187 and ...
6
In addition to the basic math knowledge, a solid grounding in Logic is necessary for tackling topics such as
Automata theory and Formal Languages
Computability Theory
Complexity Theory
While one could argue that Logic isn't math per se, the overall approach and formalism are almost the same. You may hear relatively less about these topics on the Internet, ...
5
Discrete Mathematics is pretty important for almost anything.
Direct applications of Discrete Math in DS:
The Foundations of Logic and Proofs - Without being able to write good proofs, we can never claim a data structure/algorithm to be correct.
Graph Theory: without the fundamental knowledge of Graph Theory, tree data structures cannot be understood. ...
5
There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.
5
Here is a simpler situation highlighting the difference. The set of finite binary strings is countable. The set of infinite binary strings is uncountable.
Another example: the set of numbers with finite decimal expansion is countable. The set of numbers with infinite decimal expansion is uncountable.
The reason that the number of languages is uncountable ...
5
If you consider the last term in general, $\sum_{[1\leq i \leq \log n -1]} \frac{1}{i} $ as
$$ \sum_{[1\leq i\leq k]} \frac{1}{i} $$
In this way, you can establish a bound using a integral generalization for this sum:
$$ \sum_{[1\leq i\leq k]} \frac{1}{i} \leq \int_{0}^{k} \frac{1}{x} dx = \ln (x)|_{0}^{k}= \ln(k) - \ln(1) = \ln(k)$$
But, in your problem, ...
answered Sep 15 '14 at 23:38
Jonathan Prieto-Cubides
2,1413 gold badges15 silver badges26 bronze badges
5
Idea: Count explicitly how many factors $2$ the numbers in $[1..n]$ contribute to $n!$.
Observe that every other number adds one (the even numbers), every fourth adds another (those divisible by four), every eighth another, and so on.
Hence, the number $\#_2(n!)$ of factors $2$ in $n!$ fulfills
$\qquad\displaystyle\begin{align*}
\#_2(n!) &\leq \sum_{...
Only top voted, non community-wiki answers of a minimum length are eligible