The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
3answers
142 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
0
votes
2answers
43 views

Rule induction principles in Harper's PFPL

I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19). (1) In the rule induction principles for ...
0
votes
1answer
41 views

Mathematical Induction Problem from Concrete Abstractions

This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem: Exercise 2.16 Consider the following procedure foo: ...
-1
votes
2answers
59 views

Induction proof, base case not working but induction step works? [closed]

$1+3+5+...+(2n+3)=n^2+4n$ For this series using induction proof. Base case 1,2,3,.. not working. But induction step works well. Base case is not given in question.
2
votes
2answers
106 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
1
vote
2answers
299 views

Language of balanced parentheses; Biconditional proof about parentheses

Let L be language of balanced parentheses. (a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L. (b) Prove If w is in L, then ...
0
votes
2answers
1k views

Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction. Here is my ...
1
vote
0answers
122 views

How to prove the asymptotic upper bound for $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$? [duplicate]

I met the problem Show that the solution to $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$ while reading Introduction to Algorithm. It's a question about the substitution method for ...
1
vote
0answers
48 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
1
vote
0answers
361 views

Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
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 ...
5
votes
2answers
499 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
632 views

Prove correctness of recursive multiplication algorithm

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together: ...
9
votes
3answers
330 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 ...
8
votes
1answer
1k 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
220 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
457 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 ...