[algogeeks] Ternary Huffman Algorithm
Hi all, Pls help me with the following problem.. Generalize Huffman s algorithm to ternary codewords(i.e codewords using the symbols 0,1,2) and prove tht it yeilds optimal ternary codes Thanks in advance -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Fact1 spoj
Use array of integers or strings Naveen -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: first k digits of n^n.
use log properties (mantissa) to calculate the first k digit of n^n.
i am giving u working code, which gives answer in answer variable,
double dummy =0;
f= (double)pow(10,modf((double)n*log10((double)n),dummy)+k-1);
answer=(int)f;
On Oct 4, 9:03 pm, navin navin.myhr...@gmail.com wrote:
http://www.codechef.com/problems/MARCHA4/
for this problem i took idea from topcoder
forumshttp://forums.topcoder.com/?module=ThreadthreadID=672262start=0mc=...
and from
algogeekshttp://www.mail-archive.com/algogeeks@googlegroups.com/msg06159.html
sorry that it was already discussed.
my problem is it gives me precision error.
input:
11
4 2
9 3
999 5
457474575 9
10 9
9 9
19 9
28 8
27 1
19423474 8
19423474 9
output:
25 56
387 489
36806 98999
278661176 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307491 26110976
163074912 826110976
myouput
25 56
387 489
36806 98999
278660870 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307490 26110976
163074908 826110976
test cases taken from comments.
see for the last 2 test case two digits are varying.
I dont know how to correct the precision error while taking log10.
can you help me.
here follows my code.
#includeiostream
#includevector
#includecmath
#includecstring
using namespace std;
long long modular_exponential(long long a, long long k, long long mod)
{
if ( k == 1 )
return a;
else
{
if ( k%2 == 1 )
{
return a * modular_exponential( a , k-1 , mod ) %
mod ;
}
else
{
long long val = modular_exponential( a , k/2 , mod ) %
mod ;
return (val*val) % mod;
}
}}
main()
{
int t;
cin t;
while ( t-- )
{
long long n;
int k;
cin n k;
double v = n*log10(n);
double dummy;
//cout v = v endl ;
double ff = modf(v,dummy);
//cout ff = ff endl ;
double val = pow(10.0,ff);
long long mod = 1;
for(int i = 0 ; i k-1 ; i ++ )
{
val = val*10;
mod = mod*10;
}
mod = mod*10;
cout (int) val ;
long long vv = modular_exponential( n , n , mod ) ;
if ( vv == 0 )
{
for(int i = 0 ; i k ; i ++ )
{
cout 0;
}
}
else
{
char str[100];
sprintf(str,%lld,vv);
int l = strlen(str);
if ( l == k )
cout vv;
else
{
int diff = k-l;
for(int i = 0 ; i diff ; i ++ )
cout 0 ;
cout vv ;
}
}
cout endl ;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Ternary Huffman Algorithm
its same. instead of taking min 2, select mnimum 3. but since the no.of symbols may not form complete 3-ary tree, so add some dummy variable with value=0 (highest priority). extend this logic for n symbols. On Oct 5, 12:21 pm, pre lak pre.la...@gmail.com wrote: Hi all, Pls help me with the following problem.. Generalize Huffman s algorithm to ternary codewords(i.e codewords using the symbols 0,1,2) and prove tht it yeilds optimal ternary codes Thanks in advance -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Ternary Huffman Algorithm
A huffman-tree is looking like this: #root # | # 30 # /\ # / \ # /\ #/ \ # 10 20 # || # A | #| # 20 # / \ # / \ # B C # extend the tree with a third child and encode the message using this ternary-tree. On Oct 5, 12:30 pm, Mridul Malpani malpanimri...@gmail.com wrote: its same. instead of taking min 2, select mnimum 3. but since the no.of symbols may not form complete 3-ary tree, so add some dummy variable with value=0 (highest priority). extend this logic for n symbols. On Oct 5, 12:21 pm, pre lak pre.la...@gmail.com wrote: Hi all, Pls help me with the following problem.. Generalize Huffman s algorithm to ternary codewords(i.e codewords using the symbols 0,1,2) and prove tht it yeilds optimal ternary codes Thanks in advance -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: All numbers in Array repeat twice except two
@Dave @Mukesh
yaa got it... so simple... i was needlessly making it complex
thankyou guys .
On Tue, Oct 5, 2010 at 2:09 AM, Dave dave_and_da...@juno.com wrote:
@Coolfrog$: It sounds like you think there are n items in each list,
but the problem statement says that the total number of items in the
lists is n. In your example, n = 12.
Dave
On Oct 4, 2:16 pm, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
@Dave
yes it help very much...i thank you for these...
but still one doubt
1.from first element of each sequence we have made a heap
2. now only n-1 element remains in all k seqences. total (=
k*(n-1))
elememts
3.*loop is executed once for each output element = once for each
element in the input sequences but there are k sequence...
so the loop must run for *k*(n-1) and each iteration of for loop
running
cost to O(log k).
overall complexity can be
O(k(n-1)log k)..
plz do correct me Dave
thanks..
On Mon, Oct 4, 2010 at 11:20 PM, Dave dave_and_da...@juno.com wrote:
@Coolfrog$: There must have been a communication gap.
The initial heap consists of the first element of each sequence: 2,
17, 6.
Looping, we output 2, then replace it in the heap with 3 and restore
the heap condition: 3, 17, 6.
Output 3, replace it with 4: 4, 17, 6.
Output 4, replace it with 5: 5, 17, 6.
Output 5. There is nothing left in sequence 1, so the heap now has 2
elements: 17, 6. Restore the heap condition: 6, 17. Output 6, replace
it with 9: 9, 17.
Etc. Etc.
Finally, after outputting 15, list 3 is exhausted, and the heap
consists of 1 element. At this point, the effect of the loop is that
list 2 is output.
The loop is executed once for each output element = once for each
element in the input sequences; i.e., n times.
Does that help?
Dave
On Oct 4, 12:09 pm, coolfrog$ dixit.coolfrog.div...@gmail.com
wrote:
@Dave
1. if three sequence given are 2,3,4,5
17,20,31,50
6,9,10,15
while running we will get 2,3,4,5 as sequence no.1 vanishes form
where to
choose next element. for heap . (algo.??)
2.
Loop until the heap is empty:
output the top of the heap,
replace it with the next element from the list it came from (if
non-empty, of course),
re-establishing the heap condition.* O(log k).
**loop is executed n times** .. i am not getting because we have
already
executed loop n-1 times in arranging 3,4,5. **what about rest of
elements...
Correct me plz
Regards...**
*
On Mon, Oct 4, 2010 at 7:35 PM, Dave dave_and_da...@juno.com
wrote:
@saurabh:
For the base conversion problem, simulate long division in base B1
of
dividing the number by B2. The remainder is the rightmost digit of
the
conversion. To get the next digit, divide the quotient from the
first
long division by B2 to get the remainder. Repeat for successive
digits
until the quotient is zero.
For the merge problem, assuming ascending order:
form a min-heap from the first items from each list.
Loop until the heap is empty:
output the top of the heap,
replace it with the next element from the list it came from (if
non-empty, of course),
re-establishing the heap condition.
The loop is executed n times, and each involves O(k) operations.
Dave
On Oct 4, 7:16 am, saurabh agrawal saurabh...@gmail.com wrote:
hi mukesh...gr8 solutioncan u pls help me with some other
questions:
--Given an array of n integers find all the inversion pairs in
O(n)
Inversion pair is one where a[i]a[j], ij
--Convert a number given in base B1 to a number in base B2
without
using
any
intermediate base
--You are given k sorted lists with total n inputs in all the
lists
devise a
algorithm to merge them into one single sorted list in O(n logk)
On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta
mukeshgupta.2...@gmail.com
wrote:
The problem could be solved using xor logic. First take xor of
all
the
elements .Doing that we get a value which is xor of the two non
repeating
elements(as xor of similar values is 0). Now xor of two non
repeating
numbers contains bits set at those places where the two numbers
differ.
Now
if we take any set bit of our result and again xor all those
values
of
set
where that bit is set we get first non-repeating value. Taking
xor
of
all
those values where that bit is not set gives the another
non-repeating
number..
For ex
let a[]={2,3,4,3,2,6}
xor of all values=0010
Now we need to get any set bit. We can extract the rightmost
set
bit of
[algogeeks] Re: first k digits of n^n.
On Oct 5, 5:09 am, Mridul Malpani malpanimri...@gmail.com wrote:
use log properties (mantissa) to calculate the first k digit of n^n.
i am giving u working code, which gives answer in answer variable,
double dummy =0;
f= (double)pow(10,modf((double)n*log10((double)n),dummy)+k-1);
answer=(int)f;
On Oct 4, 9:03 pm, navin navin.myhr...@gmail.com wrote:
http://www.codechef.com/problems/MARCHA4/
for this problem i took idea from topcoder
forumshttp://forums.topcoder.com/?module=ThreadthreadID=672262start=0mc=...
and from
algogeekshttp://www.mail-archive.com/algogeeks@googlegroups.com/msg06159.html
sorry that it was already discussed.
my problem is it gives me precision error.
input:
11
4 2
9 3
999 5
457474575 9
10 9
9 9
19 9
28 8
27 1
19423474 8
19423474 9
output:
25 56
387 489
36806 98999
278661176 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307491 26110976
163074912 826110976
myouput
25 56
387 489
36806 98999
278660870 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307490 26110976
163074908 826110976
test cases taken from comments.
see for the last 2 test case two digits are varying.
I dont know how to correct the precision error while taking log10.
can you help me.
here follows my code.
#includeiostream
#includevector
#includecmath
#includecstring
using namespace std;
long long modular_exponential(long long a, long long k, long long mod)
{
if ( k == 1 )
return a;
else
{
if ( k%2 == 1 )
{
return a * modular_exponential( a , k-1 , mod ) %
mod ;
}
else
{
long long val = modular_exponential( a , k/2 , mod ) %
mod ;
return (val*val) % mod;
}
}}
main()
{
int t;
cin t;
while ( t-- )
{
long long n;
int k;
cin n k;
double v = n*log10(n);
double dummy;
//cout v = v endl ;
double ff = modf(v,dummy);
//cout ff = ff endl ;
double val = pow(10.0,ff);
long long mod = 1;
for(int i = 0 ; i k-1 ; i ++ )
{
val = val*10;
mod = mod*10;
}
mod = mod*10;
cout (int) val ;
long long vv = modular_exponential( n , n , mod ) ;
if ( vv == 0 )
{
for(int i = 0 ; i k ; i ++ )
{
cout 0;
}
}
else
{
char str[100];
sprintf(str,%lld,vv);
int l = strlen(str);
if ( l == k )
cout vv;
else
{
int diff = k-l;
for(int i = 0 ; i diff ; i ++ )
cout 0 ;
cout vv ;
}
}
cout endl ;
}
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: first k digits of n^n.
@Mridul: Does it work for k = 50?
On Oct 5, 5:09 am, Mridul Malpani malpanimri...@gmail.com wrote:
use log properties (mantissa) to calculate the first k digit of n^n.
i am giving u working code, which gives answer in answer variable,
double dummy =0;
f= (double)pow(10,modf((double)n*log10((double)n),dummy)+k-1);
answer=(int)f;
On Oct 4, 9:03 pm, navin navin.myhr...@gmail.com wrote:
http://www.codechef.com/problems/MARCHA4/
for this problem i took idea from topcoder
forumshttp://forums.topcoder.com/?module=ThreadthreadID=672262start=0mc=...
and from
algogeekshttp://www.mail-archive.com/algogeeks@googlegroups.com/msg06159.html
sorry that it was already discussed.
my problem is it gives me precision error.
input:
11
4 2
9 3
999 5
457474575 9
10 9
9 9
19 9
28 8
27 1
19423474 8
19423474 9
output:
25 56
387 489
36806 98999
278661176 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307491 26110976
163074912 826110976
myouput
25 56
387 489
36806 98999
278660870 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307490 26110976
163074908 826110976
test cases taken from comments.
see for the last 2 test case two digits are varying.
I dont know how to correct the precision error while taking log10.
can you help me.
here follows my code.
#includeiostream
#includevector
#includecmath
#includecstring
using namespace std;
long long modular_exponential(long long a, long long k, long long mod)
{
if ( k == 1 )
return a;
else
{
if ( k%2 == 1 )
{
return a * modular_exponential( a , k-1 , mod ) %
mod ;
}
else
{
long long val = modular_exponential( a , k/2 , mod ) %
mod ;
return (val*val) % mod;
}
}}
main()
{
int t;
cin t;
while ( t-- )
{
long long n;
int k;
cin n k;
double v = n*log10(n);
double dummy;
//cout v = v endl ;
double ff = modf(v,dummy);
//cout ff = ff endl ;
double val = pow(10.0,ff);
long long mod = 1;
for(int i = 0 ; i k-1 ; i ++ )
{
val = val*10;
mod = mod*10;
}
mod = mod*10;
cout (int) val ;
long long vv = modular_exponential( n , n , mod ) ;
if ( vv == 0 )
{
for(int i = 0 ; i k ; i ++ )
{
cout 0;
}
}
else
{
char str[100];
sprintf(str,%lld,vv);
int l = strlen(str);
if ( l == k )
cout vv;
else
{
int diff = k-l;
for(int i = 0 ; i diff ; i ++ )
cout 0 ;
cout vv ;
}
}
cout endl ;
}
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Very immediate need for a Linux Engineer (Opsware Engineer with Redhat and Kickstart) - GA - Longterm
Dear Partner, Hope you are doing well, *Very immediate need for a Linux Engineer (Opsware Engineer with Redhat and Kickstart)* *Job Title : Linux Engineer (Opsware Engineer) Location : Atlanta, GA Duration : Longterm contract* *Rate : $50/Hr on C2C * *Desired: *Opsware experience 2+ years as Opsware Engineer Experience as a lead Scripting (perl/python/php python preferred) *Minimum requirements:* 5 years+ linux engineer experience Packaging experience (linux kickstart rpms) Good communication skills Good presentation skills Thanks Regards Adil Technical Recruiter Direct: 203 987 8944 Email: a...@panzersolutions.com Panzer Solutions LLC -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Bitwise operator - Adobe
here for the next multiple of 8
i have 3 different solutions ...
1)...
nextmultiple = (n/8+1)*8
2)...
nextmultiple= n+(8-n%8)
3)...
suppose i have 32-bit compiler
for(i=32; i1; i--)
{
if((pow(2,i)n==0)(pow(2,i-1)n!=0))
{
nextmultiple = pow(2,i);
break;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Very immediate need for a UX / UI Designer - MN - 1-2 months contract
Dear Partner, Hope you are doing well, *Very immediate need for a UX / UI Designer*. *Job Title : UX / UI Designer Location : Golden Valley, MN Duration : 1-2 months contract* ** The UI designer will sit with customer resources assigned and drive design sessions for each of use cases and pages highlighted. They need strong customer and communication skills. They also need to have done UI design work on MOSS sites in the past because there are things which need to be account for in MOSS specifically. They need to deliver wireframes as HTML and the page layouts needed for each feature set. If they can build user controls that would be even better. __ Thanks Regards Adil Technical Recruiter Direct: 203 987 8944 Email: a...@panzersolutions.com Panzer Solutions LLC -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] coin changing problem
Hi all, Pls help me with the solution to the following problem related to the coin changing problem. suppose that the available coins a ein the denominations c^0, c^1 , c^2... c^k for some intgers c1 and k=1. show tht the greedy algorithm always yeilds an optimal solution thanks in advance Preethi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: first k digits of n^n.
@Dave k=9 only for this problem.
@Mridul:
for input
2
19423474 8
19423474 9
output:
16307490 26110976
163074908 826110976
but actual ouptut is
16307491 26110976
163074912 826110976
two digits changing
for this only i posted my solution here.
it is taken from comments section of the problem statement.
i cant find where am going wrong.
On Oct 5, 6:17 pm, Dave dave_and_da...@juno.com wrote:
@Mridul: Does it work for k = 50?
On Oct 5, 5:09 am, Mridul Malpani malpanimri...@gmail.com wrote:
use log properties (mantissa) to calculate the first k digit of n^n.
i am giving u working code, which gives answer in answer variable,
double dummy =0;
f= (double)pow(10,modf((double)n*log10((double)n),dummy)+k-1);
answer=(int)f;
On Oct 4, 9:03 pm, navin navin.myhr...@gmail.com wrote:
http://www.codechef.com/problems/MARCHA4/
for this problem i took idea from topcoder
forumshttp://forums.topcoder.com/?module=ThreadthreadID=672262start=0mc=...
and from
algogeekshttp://www.mail-archive.com/algogeeks@googlegroups.com/msg06159.html
sorry that it was already discussed.
my problem is it gives me precision error.
input:
11
4 2
9 3
999 5
457474575 9
10 9
9 9
19 9
28 8
27 1
19423474 8
19423474 9
output:
25 56
387 489
36806 98999
278661176 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307491 26110976
163074912 826110976
myouput
25 56
387 489
36806 98999
278660870 380859375
1 0
367880063 9
197841965 589123979
33145523 05812736
4 3
16307490 26110976
163074908 826110976
test cases taken from comments.
see for the last 2 test case two digits are varying.
I dont know how to correct the precision error while taking log10.
can you help me.
here follows my code.
#includeiostream
#includevector
#includecmath
#includecstring
using namespace std;
long long modular_exponential(long long a, long long k, long long mod)
{
if ( k == 1 )
return a;
else
{
if ( k%2 == 1 )
{
return a * modular_exponential( a , k-1 , mod ) %
mod ;
}
else
{
long long val = modular_exponential( a , k/2 , mod ) %
mod ;
return (val*val) % mod;
}
}}
main()
{
int t;
cin t;
while ( t-- )
{
long long n;
int k;
cin n k;
double v = n*log10(n);
double dummy;
//cout v = v endl ;
double ff = modf(v,dummy);
//cout ff = ff endl ;
double val = pow(10.0,ff);
long long mod = 1;
for(int i = 0 ; i k-1 ; i ++ )
{
val = val*10;
mod = mod*10;
}
mod = mod*10;
cout (int) val ;
long long vv = modular_exponential( n , n , mod ) ;
if ( vv == 0 )
{
for(int i = 0 ; i k ; i ++ )
{
cout 0;
}
}
else
{
char str[100];
sprintf(str,%lld,vv);
int l = strlen(str);
if ( l == k )
cout vv;
else
{
int diff = k-l;
for(int i = 0 ; i diff ; i ++ )
cout 0 ;
cout vv ;
}
}
cout endl ;
}
}- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: binary matrix
For square matrix , link suggested by Amit would work. Finding a sub- rectangle is tougher. I would go this way; First scan from bottom right till top left and for every Non-zero member in matrix create this pair ( width , depth ). Width is how many continuous 1's ( including itself ) are there to its right, Depth is how many continuous 1's ( including itself ) are there down wards now select a point P(i,j) , which has value Pair ( W , D ) it means W-1 columns to right and D-1 rows below are '1' , Note: it doesn't give any info about diagonal entries to P , and we will see , we actually don't need them. Now think about all possible rectangles which could be made when P is left top corner so go columnwise from i to i + 1 , i +2 , i + (W-1) points ( call it P' point ) , at every step, see the minimum depth for all points between P and P' and keep calculating area by width X minDepth e.g. P has width = 3, depth = 4 and co-ordinates (i,j ) then go like this Area for A[i,j] and P'[i, j+1 ] = 2 X MinDepth( P, P') //A1 Area for A[i,j] and P[i, j+2 ] = 3 X MinDepth( P, P', P) //A2 : Note MinDepth is Minimum Depth of all three points so far Take Max of A1,A2 and you would have max rectangle which could be created by having P as top left corner. Now , keep traveling P throughout this Matrix. There are few optimisation. A point with width W and depth D can AT MAX has a rectangle with AREA MAX = W * D so next time consider points only whose W * D Max Area calcuated so far.E.g if you have already got a point which has sub rectangle with area = 12 no need to look for points which has such (W,D) pairs = ( 2,3) , (4,2) , (3,3) etc . Time complextiy : First time reverse traversal O(m * n ) /// m Rows , n Columns Second time , MAX AREA calculation for each points , worse case o(n) as we need to travel only column wise as explained above Above action to be done for m*n points so total O( mn * n ) = O(mn^2) So total Time = O ( m * n^2 ) Time complexity :O ( 2 * m * n ) as W and D pair for each entry has to be maintained Suggestions, Clarifications, Modifications ? -Manish -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Duplicate in an array
You are given an array of positive numbers in which one number is repeated. Rest all are present only once. Find the duplicate number in linear or sub linear time. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] coin changing problem
int denom(int Coin[],int n,int amount)
{
for(i=0;in;++i)
{
c=Coin[i];
for(j=c;j=amount;++j)
{
den[j]+=d[j-c];
}
}
return den[amount];
}
On Wed, Oct 6, 2010 at 4:43 AM, pre lak pre.la...@gmail.com wrote:
Hi all,
Pls help me with the solution to the following problem related to the coin
changing problem.
suppose that the available coins a ein the denominations c^0, c^1 , c^2...
c^k for some intgers c1 and k=1. show tht the greedy algorithm always
yeilds an optimal solution
thanks in advance
Preethi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] coin changing problem
show tht the greedy algorithm always yeilds an optimal solution??/
On Tue, Oct 5, 2010 at 7:47 PM, sharad kumar aryansmit3...@gmail.comwrote:
int denom(int Coin[],int n,int amount)
{
for(i=0;in;++i)
{
c=Coin[i];
for(j=c;j=amount;++j)
{
den[j]+=d[j-c];
}
}
return den[amount];
}
On Wed, Oct 6, 2010 at 4:43 AM, pre lak pre.la...@gmail.com wrote:
Hi all,
Pls help me with the solution to the following problem related to the coin
changing problem.
suppose that the available coins a ein the denominations c^0, c^1 , c^2...
c^k for some intgers c1 and k=1. show tht the greedy algorithm always
yeilds an optimal solution
thanks in advance
Preethi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
