The induction tag has no wiki summary.
0
votes
0answers
44 views
How i can use Mathematical induction to prove CFG production? [duplicate]
If I have production $G_n$
$S \rightarrow A_i b_i \quad$ for $1 \le i \le n$
$A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$
Prove $G_n$ is sub-productions from $2n^2 ...
-2
votes
3answers
114 views
Defining an “arbitrarily large graph” [closed]
Assume that we want to talk about arbitrarily large graphs, which are however finite. Let $G=(V,E)$ be such a graph.
What restrictions can we impose on the graph and still be in the spirit of the ...
5
votes
2answers
188 views
Finding nested intervals efficiently
The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique.
If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$
How do I find out which ...
5
votes
1answer
105 views
How to “prove my algorithm correct”
I'm in a first year discrete math course and we started algorithms. I had to create an algorithm to multiply two numbers together recursively, which resulted in this:
...
7
votes
3answers
231 views
Do “inductively” and “recursively” have very similar meanings?
Do "inductively" and "recursively" mean very similar?
For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
6
votes
1answer
387 views
How do I write a proof using induction on the length of the input string?
In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
3
votes
1answer
132 views
How to prove that the pre-order tree traversal algorithm terminates?
I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that ...
5
votes
1answer
290 views
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$
Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$.
The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing
$\qquad ...
