All Questions
Tagged with recursive-algorithms computer-science
75
questions
-2
votes
2
answers
102
views
i need help with this recursive problem: $T(n) = nT(n-1) + 1$, $T(0) = 0$. [closed]
Now here I solved everything but I’m now stuck at the general form how am I gonna write the general form with the (pi) product summation ?
Hint there’s something related also with combination and ...
- 11
0
votes
0
answers
61
views
Mathematical Induction to Prove Binary Search for First Occurrence of an Element in a Sorted Array
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\cardinal}[1]{\abs{#1}}$
$\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}$
$\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}$
$\...
- 1,840
0
votes
1
answer
76
views
my function is skipping
I wrote a function in C code that calculates a polynomial value from a given array arr[] of arrsize size, where the elements are ...
- 25
1
vote
0
answers
39
views
why is this iterative algorithm for calculating the Chebyshev polynomials stable?
It is known that $\cos n \theta $ is a polynomial of $\cos \theta $. This polynomial is the so called Chebyshev polynomial of order $n$, often denoted as $T_n(x)$.
We have the recursion relation
$$T_{...
- 1,015
2
votes
1
answer
608
views
Can't understand a recursive definition of reverse
reverse (x): get the reverse of a string x.
For instance; reverse (aaabc) = cbaaa
Ok, so I made this.
$W_1 ∈ Σ$* and $W_2 ∈ Σ$* and $x ∈ Σ$
I guessed that $W_1$.$(W_2x)$ is a concatenation then $(W_2x)...
- 82
0
votes
1
answer
78
views
Is there an Algorithm to calculate the sequence of π and e using only integer, addition, subtraction, array, and loop?(changed question) [closed]
Someone made a computer program calculate the sequence of π and e sequentially.
The program only uses integer, addition, subtraction, array and loops.
The program is slow, but it doesn't stop and ...
- 13
1
vote
1
answer
46
views
Why can $T(x,c)=\theta(x),T(c,y)=\theta(y),T(x,y)=\theta(x+y)+T(x/2,y/2)$ be rewritten as $T(x,y)=c(x+y)+T(x/2,y/2)$
I'm doing a self study on MIT Opencourseware Algorithms course and the first problem set can be found here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-...
0
votes
1
answer
291
views
Minimum cost in a 2D matrix
In my last interview, I was asked a question for which optimal approach I am still not able to figure out.
Given a 2D matrix, with n rows and ...
- 1
2
votes
0
answers
220
views
Proving the number of steps in Merge Sort algorithm based on a recurrence
This is for a sorting algorithm (Merge Sort), where $T$ represents the maximum number of steps executed by the algorithm. $n$ represents the length of the input array (to be sorted) and $k$ represents ...
- 35
1
vote
2
answers
167
views
How to prove correctness of recursive programs?
We consider the Russian farmer multiplication for calculating a product x · k with x ∈ R and k ∈ N.
...
- 11
0
votes
0
answers
17
views
Time spent multiplying with expoDC and D&C
Let
$T(m,n) \leq that$
$0$ if n = 1
$T(m,n/2) + M(mn/2,mn/2)$ if n is even
$T(m, n-1) + M(m, (n-1)m)$ otherwise
The time to do $a^n$ where m is the size of a (the number of figures).
If $M(q,s) \...
0
votes
1
answer
64
views
Algorithm telling if a word is good
Consider the alphabet $\{0,1\}$. A word is a finite sequence of letters. A word is called basic if it's of one of the following forms: $1^k0, 1^k00, 1^k000,1^k0000,1^k00000$; where $1^k=11\dots11$ ($k$...
- 12k
0
votes
1
answer
418
views
Time Complexity of CLRS Optimal Parenthesis Algorithm
I am reading the Introduction to Algorithms CLRS book, and I am unsure about the time complexity of one of the algorithms that is a recursive algorithm that calls itself twice. This chain matrix ...
- 553
0
votes
0
answers
22
views
Is there a specific search paradigm for finding pairs in a set?
I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
- 21
2
votes
1
answer
50
views
Generation of a constant term is observed
Here's a question from a past contest conducted by CMI (Chennai
Mathematical Institute).
First of all, the conditions of the question can be broken down into (my interpretation, check if ...
- 3,334