"Coding is just like talking to a unknown girl. Once you talked to her with guts, the next time you'll never afraid",Really? Yes , try it Now !!! Everything here is for education and learning purpose only , individual holds rights on outer posts/links etc. Team Cracking The Code
Bob is playing with his ball destroyer robot. Initially, Bob has r
red balls, g green balls and b blue balls. The robot
will repeat the following 3-step program until there are no balls
left:
Source : Commented by a user named bob , later i found property of TopCoder , so i have am just sharing it to learning purpose , TopCoder Inc. holds all right on the problem statement .
|
possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be 
.
by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].
.![S[k]](http://s0.wp.com/latex.php?latex=S%5Bk%5D&bg=f0f0f0&fg=555555&s=0 "S[k]")
denote the sum of a maximum sum contiguous subsequence ending exactly at index 
.![S[k+1] = max \{S[k] + A[k+1], A[k+1] \}](http://s0.wp.com/latex.php?latex=S%5Bk%2B1%5D+%3D+max+%5C%7BS%5Bk%5D+%2B+A%5Bk%2B1%5D%2C+A%5Bk%2B1%5D+%5C%7D&bg=f0f0f0&fg=555555&s=0 "S[k+1] = max \{S[k] + A[k+1], A[k+1] \}")
(for all 
)![S[i]](http://s0.wp.com/latex.php?latex=S%5Bi%5D&bg=f0f0f0&fg=555555&s=0 "S[i]")
for 
.
where ![T[i]](http://s0.wp.com/latex.php?latex=T%5Bi%5D&bg=f0f0f0&fg=555555&s=0 "T[i]")
would store the starting index for a maximum sum contiguous subsequence ending at index i. time and space.
. The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all 
values of the S and T arrays. time and space.
The concept: Recurrence relations are recursive definitions of
mathematical functions or sequences. For example, the recurrence
relation
g(n) = g(n-1) + 2n -1
g(0) = 0
defines the function f(n) = n^2, and the recurrence relation
f(n) = f(n-1) + f(n-2)
f(1) = 1
f(0) = 1
defines the famous Fibanocci sequence 1,1,2,3,5,8,13,....
Solving a recurrence relation: Given a function defined by a recurrence
relation, we want to find a "closed form" of the function. In other words,
we would like to eliminate recursion from the function definition.
There are several techniques for solving recurrence relations.
The main techniques for us are the iteration method (also called expansion,
or unfolding methods) and the Master Theorem method. Here is an example
of solving the above recurrence relation for g(n) using the iteration
method:
g(n) = g(n-1) + 2n - 1
= [g(n-2) + 2(n-1) - 1] + 2n - 1
// because g(n-1) = g(n-2) + 2(n-1) -1 //
= g(n-2) + 2(n-1) + 2n - 2
= [g(n-3) + 2(n-2) -1] + 2(n-1) + 2n - 2
// because g(n-2) = g(n-3) + 2(n-2) -1 //
= g(n-3) + 2(n-2) + 2(n-1) + 2n - 3
...
= g(n-i) + 2(n-i+1) +...+ 2n - i
...
= g(n-n) + 2(n-n+1) +...+ 2n - n
= 0 + 2 + 4 +...+ 2n - n
// because g(0) = 0 //
= 2 + 4 +...+ 2n - n
= 2*n*(n+1)/2 - n
// using arithmetic progression formula 1+...+n = n(n+1)/2 //
= n^2
Applications: Recurrence relations are a fundamental mathematical
tool since they can be used to represent mathematical functions/sequences
that cannot be easily represented non-recursively. An example
is the Fibanocci sequence. Another one is the famous Ackermann's
function that you may (or may not :-) have heard about in Math112 or
CS14 [see CLR, pp. 451-453]. Here we are mainly interested in applications
of recurrence relations in the design and analysis of algorithms.
Recurrence relations with more than one variable: In some applications
we may consider recurrence relations with two or more variables. The
famous Ackermann's function is one such example. Here is another example
recurrence relation with two variables.
T(m,n) = 2*T(m/2,n/2) + m*n, m > 1, n > 1
T(m,n) = n, if m = 1
T(m,n) = m, if n = 1
We can solve this recurrence using the iteration method as follows.
Assume m <= n. Then
T(m,n) = 2*T(m/2,n/2) + m*n
= 2^2*T(m/2^2,n/2^2) + 2*(m*n/4) + m*n
= 2^2*T(m/2^2,n/2^2) + m*n/2 + m*n
= 2^3*T(m/2^3,n/2^3) + m*n/2^2 + m*n/2 + m*n
...
= 2^i*T(m/2^i,n/2^i) + m*n/2^(i-1) +...+ m*n/2^2 + m*n/2 + m*n
Let k = log_2 m. Then we have
T(m,n) = 2^k*T(m/2^k,n/2^k) + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n
= m*T(m/m,n/2^k) + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n
= m*T(1,n/2^k) + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n
= m*n/2^k + m*n/2^(k-1) +...+ m*n/2^2 + m*n/2 + m*n
= m*n*(2-1/2^k)
= Theta(m*n)
Analyzing (recursive) algorithms using recurrence relations: For recursive
algorithms, it is convinient to use recurrence relations to describe
the time complexity functions of the algorithms. Then we can obtain
the time complexity estimates by solving the recurrence relations. You
may find several examples of this nature in the lecture notes and the books,
such as Towers of Hanoi, Mergesort (the recursive version), and Majority.
These are excellent examples of divide-and-conquer algorithms whose
analyses involve recurrence relations.
Here is another example. Given algorithm
Algorithm Test(A[1..n], B[1..n], C[1..n]);
if n= 0 then return;
For i := 1 to n do
C[1] := A[1] * B[i];
call Test(A[2..n], B[2..n], C[2..n]);
If the denote the time complexity of Test as T(n), then we can express T(n)
recursively as an recurrence relation:
T(n) = T(n-1) + O(n)
T(1) = 1
(You may also write simply T(n) = T(n-1) + n if you think of T(n)
as the the number of multiplications)
By a straighforward expansion method, we can solve T(n) as:
T(n) = T(n-1) + O(n)
= (T(n-2) + O(n-1)) + O(n)
= T(n-2) + O(n-1) + O(n)
= T(n-3) + O(n-2) + O(n-1) + O(n)
...
= T(1) + O(2) + ... + O(n-1) + O(n)
= O(1 + 2 + ... + n-1 + n)
= O(n^2)
Yet another example:
Algorithm Parallel-Product(A[1..n]);
if n = 1 then return;
for i := 1 to n/2 do
A[i] := A[i]*A[i+n/2];
call Parallel-Product(A[1..n/2]);
The time complexity of the above algorithm can be expressed as
T(n) = T(n/2) + O(n/2)
T(1) = 1
We can solve it as:
T(n) = T(n/2) + O(n/2)
= (T(n/2^2) + O(n/2^2)) + O(n/2)
= T(n/2^2) + O(n/2^2) + O(n/2)
= T(n/2^3) + O(n/2^3) + O(n/2^2) + O(n/2)
...
= T(n/2^i) + O(n/2^i) +...+ O(n/2^2) + O(n/2)
= T(n/2^log n) + O(n/2^log n) +...+ O(n/2^2) + O(n/2)
// We stop the expansion at i = log n because
2^log n = n //
= T(1) + O(n/2^log n) +...+ O(n/2^2) + O(n/2)
= 1 + O(n/2^log n +...+ n/2^2 + n/2)
= 1 + O(n*(1/2^log n +...+ 1/2^2 + 1/2)
= O(n)
// because 1/2^log n +...+ 1/2^2 + 1/2 <= 1 //
Using recurrence relations to develop algorithms: Recurrence relations are
useful in the design of algorithms, as in the dynamic programming paradigm.
For this course, you only need to know how to derive an iterative (dynamic
programming) algorithm when you are given a recurrence relation.
For example, given the recurrence relation for the Fibonacci function f(n)
above, we can convert it into DP algorithm as follows:
Algorithm Fib(n);
var f[0..n]: array of integers;
f[0] := f[1] := 1;
for i := 2 to n do
f[i] := f[i-1] + f[i-2];
// following the recurrence relation //
return f[n];
The time complexity of this algorithm is easily seen as O(n). Of course
you may also easily derive a recursive algorithm from the recurrence relation:
Algorithm Fib-Rec(n);
if n = 0 or 1 then return 1;
else
return Fib-Rec(n-1) + Fib-Rec(n-2);
but the time complexity of this algorithm will be exponential, since
we can write its time complexity function recursively as:
T(n) = T(n-1) + T(n-2)
T(1) = T(0) = 1
In other words, T(n) is exactly the n-th Fibonacci nummber. To solve this
recurrence relation, we would have to use a more sophisticated technique
for linear homogeneous recurrence relations, which is discussed in the
text book for Math112. But for us, here it suffices to know that
T(n) = f(n) = theta(c^n), where c is a constant close to 1.5.
Source : http://www.cs.ucr.edu/~jiang/cs141/recur-tut.txt
#include<iostream> #include <string.h> using namespace std; void removeDoubleZeros(char* src) { int len = strlen(src); int idxSrc = 0; int idxDest = 0; while (idxSrc + 1 < len) { if(src[idxSrc]=='0'&& src[idxSrc+1]== '0') { if( ((idxSrc - 1 >= 0 && src[idxSrc - 1]!= '0')|| idxSrc - 1 < 0) && ((idxSrc + 2 < len && src[idxSrc + 2]!= '0')|| idxSrc + 2 >= len) ){ idxSrc += 2; } else src[idxDest++] = src[idxSrc++]; } else { src[idxDest++] = src[idxSrc++]; } } src[idxDest++] = src[idxSrc]; src[idxDest] = 0; }; int main() { char src[] = "a3409jd00dk000d"; removeDoubleZeros(src); printf("%s", src); return 0; }Time Complexity O(N) where N is lengthof stringSpace Complexity O(1)Run Here http://ideone.com/1p3Sb
#include<iostream>
#include <string.h>
using namespace std;
int ifPermutation(const char* a, const char* b)
{
if (strlen(a) != strlen(b))
return 0;
char arr[256];
memset(arr, 0, sizeof(arr));
for (int i = 0; i < strlen(a); i++)
{
arr[a[i]]++;
arr[b[i]]--;
}
for (int i = 0; i < 256; i++)
{
if (arr[i] != 0)
return 0;
}
return 1;
};
int main()
{
char* a = "abca";
char* b = "cbaa";
int res = ifPermutation(a, b);
printf("%d",res);
}
#include<iostream> #include<stdlib.h> using namespace std; typedef struct tree{ int val; struct tree *left; struct tree *right; }tree; tree* insert(tree* root, int val) { if(root == NULL) { tree* temp = (tree*) malloc(sizeof(tree)); temp->val = val; temp->left = NULL; temp->right = NULL; return temp; } tree* node = (tree*) malloc(sizeof(tree)); if(root->val < val) root->right = insert(root->right, val); else root->left = insert(root->left, val); return root; } tree* buildBST(int preOrder[], int length) { tree* root; if(length != 0) { root = (tree*) malloc(sizeof(tree)); root->val = preOrder[0]; root->left = NULL; root->right = NULL; } else return NULL; for(int i = 1; i < length; i++) { root = insert(root, preOrder[i]); } return root; } void printInOrder(tree* BST) { if(BST == NULL) return; printInOrder(BST->left); cout << BST->val << " "; printInOrder(BST->right); } void printPreOrder(tree* BST) { if(BST == NULL) return; cout << BST->val << " "; printPreOrder(BST->left); printPreOrder(BST->right); } int main(void) { int preOrder[] = {10, 5, 3, 4, 6, 11, 13, 12}; tree* BST = buildBST(preOrder, sizeof(preOrder) / sizeof(int)); printInOrder(BST); cout << endl; printPreOrder(BST); cout << endl; }
