Re: [algogeeks] Pthread and Semaphore
You can use mutex instead of semaphores if you need to execute only one
case at a time.
FROM,
V.VIGNESH.
M.Sc Theoretical Computer Science.
PSG College of Technology
On 25 November 2012 22:37, jagannath jpdasi...@gmail.com wrote:
Folks, I have one pthread question.I know that its not the right place but
i thought this is the right place to post this. Code snippet:
#include stdlib.h
#include stdio.h
#include unistd.h /* defines _POSIX_THREADS if pthreads are available */
#ifdef _POSIX_THREADS
# include pthread.h
#endif
#include semaphore.h
void *text(void *arg);
int code[] = { 4, 6, 3, 1, 5, 0, 2 };
int main()
{
int i;
pthread_t tid[7];
for (i = 0; i 7; i++)
{
pthread_create(tid[i], NULL, text, (void*)code[i]);
pthread_join(tid[i],NULL);
}
return 0;
}
void *text(void *arg)
{
int n = *(int*)arg;
switch (n)
{
case 0:
printf(A semaphore S is an integer-valued variable which can take only
non-negative\n);
printf(values. Exactly two operations are defined on a semaphore:\n\n);
break;
case 1:
printf(Signal(S): If there are processes that have been suspended on this
semaphore,\n);
printf( wake one of them, else S := S+1.\n\n);
break;
case 2:
printf(Wait(S): If S0 then S:=S-1, else suspend the execution of this
process.\n);
printf( The process is said to be suspended on the semaphore S.\n\n);
break;
case 3:
printf(The semaphore has the following properties:\n\n);
break;
case 4:
printf(1. Signal(S) and Wait(S) are atomic instructions. In particular,
no\n);
printf( instructions can be interleaved between the test that S0 and
the\n);
printf( decrement of S or the suspension of the calling process.\n\n);
break;
case 5:
printf(2. A semaphore must be given an non-negative initial value.\n\n);
break;
case 6:
printf(3. The Signal(S) operation must waken one of the suspended
processes. The\n);
printf( definition does not specify which process will be
awakened.\n\n);
break;
}
pthread_exit(0);
}
The threads are not synchronized and therefore the text output is garbled.
How to add semaphores of POSIX to this program to synchronize the threads.?
primitives to rejig your memory:
sem_init(), sem_wait(),sem_post(),sem_destroy().
--
--
Re: [algogeeks] problem with increment operator
Hai i tried the same in TC compiler. i got the output as 17. I guess the
output should be 17 as explained by Prateek Jain
On 30 May 2012 02:26, rahul ranjan rahul.ranjan...@gmail.com wrote:
it first calculates from right to left and then performs addition
so after a++ its still 4(with a promise to increment in next
statement). then ++a makes it 5. then further ++a makes it 6
now the addition phase comes into play value of a is 6 now so total
18 if it wud hav been a++ + a++ + a++ sum wud hav been 12
and for next statement 'a' wud hav been 7
On Wed, May 30, 2012 at 1:32 AM, Hassan Monfared hmonfa...@gmail.comwrote:
I implemented ++ for a simple class and got 17.
class A
{
public :
int val;
A(int v):val(v){}
int operator++()
{
cout empty arg called\n;
return ++val;
}
int operator++(int x)
{
cout x:arged arg called\n;
return val++;
}
};
--
A b(4);
cout ++a + ++a +a++endl;
17
but story is different for your sample.
let me tell the fact with a simpler problem :
int b=4;
cout ++b + ++b ;
will print 12 instead of 11!
amazing huh ?
what happens from right to left is :
in the right statement : b becomes 5:
in the left statement : b becomes 6 ( now be is 6 in both sides !)
so right_b + left_b = 6+6 = 12
Regards
On Tue, May 29, 2012 at 11:43 PM, Prateek Jain prateek10011...@gmail.com
wrote:
how is it 6?
++a(5) + ++a(6) + a++(6) it shud be 17
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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] Check if one tree is sub tree of other
FROM, V.VIGNESH. On 20 March 2012 17:58, Dheeraj Sharma dheerajsharma1...@gmail.com wrote: How to check if one binary tree is a sub tree of other? Any Solution other then bruteforce? Prototype bool check(node *t1,node *subtree) -- Sent from my mobile device *Dheeraj Sharma* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. Hai, i got an idea using any of tree traversal methods(say inorder). Perform inorder traversal of mail tree and sub tree. store the results separately compare the elements of sub tree elements with main tree elements. it takes a for loop to compare the results. Also i am a newbie to this. Any mistakes please pardon me. Thank you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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]
Dude plz post them here... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] DeShaw Question....tough One
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
On 6 September 2010 14:01, bittu shashank7andr...@gmail.com wrote:
u are given an array and u have to print the longest increasing
scattered subsequence...eg..{11,9,8,2,10,7,3,4,5}.
Solve it O(n);
--
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.
--
Vignesh Radhakrishnan
--
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] String Problems
@Marcio, I get your algo now. So a substring match is also a match. I get your approach. Thank you. Any ideas for the second problem? On 20 May 2010 10:45, vignesh radhakrishnan rvignesh1...@gmail.com wrote: @Mario Your estimate of no. of strings, I guess doesn't consider strings of length less than length H or W. it would order(4H^2+4W^2) approximately. I guess I 've understood it right. correct me if I'm wrong On 20 May 2010 07:23, Mario Ynocente Castro ycma...@gmail.com wrote: I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- 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. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- 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. -- There are two kinds of people. Those who care for others and The others -- There are two kinds of people. Those who care for others and The others -- 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] String Problems
@Mario Your estimate of no. of strings, I guess doesn't consider strings of length less than length H or W. it would order(4H^2+4W^2) approximately. I guess I 've understood it right. correct me if I'm wrong On 20 May 2010 07:23, Mario Ynocente Castro ycma...@gmail.com wrote: I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- 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. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] String Problems
I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- 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: another google telephone interview question
@aarthi, Its seems like ur worried only about frequency, not the sorting. If its a count sort you're trying to explain,then it requires huge space.. And i guess there is no O(n) sort except count sort, which won't be a gr8 soln. for the original problem Regards, Vignesh On May 19, 4:09 pm, Aarthi Thangamani aarthi.thangam...@gmail.com wrote: If you are using an extra space to count, why need a heap? An array of size k can be used to first count the occurances. Then run through the original array of size N and fill it according to the count our occirances using the constant k size array. Space O(k) and time O(N) is the best thing I think of. :( On Tue, May 18, 2010 at 7:11 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: Here u r using extra space to store count values.. CHERUVU JAANU REDDY M.Tech in CSIS On Tue, May 18, 2010 at 7:01 PM, Jagadish M jagadis...@gmail.com wrote: On May 18, 8:29 am, Terence technic@gmail.com wrote: How do you maintain the heap? Could you explain in detail for the following example: 1 2 3 3 2 1 1 1 2 3 (n=10, k=3) Basically, in each node we maintain the key and its count. Initially, heap has the first element. 1:1 Search for 2 and insert( since its not found) 1:1 / 2:1 Search for 3 and insert ( since its not found). 1:1 / \ 2:1 3:1 Search for 3; since 3 is already there increment its count by 1. 1:1 / \ 2:1 3:2 Search for 2; since 2 is already there increment its count by 1. 1:1 / \ 2:2 3:2 and so on... Since, there are only k distinct keys the heap size will at most be k; so each search/insert/increment operation takes O(log k) time. Jagadish http://www.cse.iitb.ac.in/~jagadish On 2010-5-17 22:38, Jagadish M wrote: The best algorithm I can think of is to maintain a heap of k elements. Takes O(n log k) time. Is anything told about the values of the keys? If the keys have values less than N, then it is possible to do what you say, i.e sort them in place. -Jagadish http://www.cse.iitb.ac.in/~jagadish On May 13, 7:06 pm, divyasweetdivya@gmail.com wrote: This problem was asked in google phone interview. We have N element array with k distinct keys(No relation between k N given so assume kN) What is the best method to sort this array without using any extra memory? Please elaborate. -- 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 athttp:// 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group athttp:// 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.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.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 athttp://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.
Re: [algogeeks] Convert a Binary tree into spike.
do bfs. On 13 May 2010 09:18, vinayan c vinayan1...@gmail.com wrote: Something like this 1 2 3 4 5 67 1 | 2-3 | 4-5-6-7 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] compute kth smallest element from union of two lists
This is for kth largest. Change it for kth smallest In fact, this problem is amenable to something very similar to binary search. Suppose my arrays are A and B. The idea is to keep track of two indices, a (for A) and b (for B), such that a + b = k - 1 (it's very important to maintain this invariant). It's easy to check whether A[a] or B[b] is the answer: A[a] is the answer if and only if B[b-1] = A[a] = B[b], and B[b] is the answer if and only if A[a-1] = B[b] = A[a], where we use the convention that A[-1] = B[-1] = negative infinity. (This can be determined in constant time.) Moreover, if neither of these is the case, you can divide the problem in half: if A[a] B[b-1], you restrict your attention to the portion of A above index a and the portion of B below index b, and otherwise (it must be the case that B[b] A[a-1]), you restrict your attention to the portion of A below index a and the portion of B above index b. (If you start with a and b in the middle of the arrays and always make the new indices be in the middle of the subarrays you're considering at that point, this step will always divide the problem in half.) Thanks to Lux Perpetua http://forums.devshed.com/member.php?u=74699 source: http://forums.devshed.com/software-design-43/finding-kth-largest-element-in-a-union-of-two-arrays-137322.html On 13 May 2010 19:34, divya sweetdivya@gmail.com wrote: You are given two sorted lists of size m and n. Give an O(log m+log n) time algorithm for computing the kth smallest element in the union of the two lists -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] 400!
@siddharth and prasoon either design a very long integer library yourself, or use gmp library in cpp or BigInteger Class in java. Regards, vignesh On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote: But is there any way to accomplish this without an array ? Even for 100!. On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote: I think challenge here is not the Execution time, but the storage. 300 ! or 400! should generally go beyond the storage capabilities of long long ints in cpp. @ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately be able to store the output. I think Rajesh Patidar's answer fits the bill well, in terms of storage. On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: I agree with abhijith. But given some very large x for which i would have to find factorial. I would either (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an interview (ii) use simple brute multiplication algorithm. The second approach requires (a) The no. of digits in n! for making storage available (b) The calculation itself which I would brute force References: http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it http://delphiforfun.org/programs/big_factorials.htm On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain sweetdivya@gmail.com wrote: wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Srivastava Human Knowledge is for all -- 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. -- There are two kinds of people. Those who care for others
Re: [algogeeks] a google question
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote:
@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare a[2]
b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. think
for ths case also.
On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.comwrote:
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1]
because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since
both the lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan
shoonya.mo...@gmail.comwrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array will
be max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using DP,
moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan
shoonya.mo...@gmail.comwrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array will
be max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using DP
moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.comwrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
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.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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
There are two kinds of people. Those who care for others and The others
--
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] 400!
I agree with abhijith. But given some very large x for which i would have to find factorial. I would either (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an interview (ii) use simple brute multiplication algorithm. The second approach requires (a) The no. of digits in n! for making storage available (b) The calculation itself which I would brute force References: http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it http://delphiforfun.org/programs/big_factorials.htm On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain sweetdivya@gmail.com wrote: wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] Divide and Conquer problem
You 've got n teams and nC2 ways of conducting the matches with specified constraints that's n/2(n-1). So, each day you need to conduct n/2 matches such that, no team repeats within a day, no match that was previously held repeats. Since the problem has an unique solution, you can either brute force it with a program or design an back track solution. regards, vignesh On 7 April 2010 12:20, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Can any one help me with this problem Its a divide and conquer problem where, there are n teams and each team plays each opponent only once. And each team plays exactly once every day. If n is the power of 2, I need to construct a timetable allowing the tournament to finish in n-1 days... Any help would be appreciated.. thanks -- 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.
Re: [algogeeks] Cartesian Product in set theory
The unordered pair will be a subset of cartesian product. What is the significance of it? On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote: Hi all, I have came across a problem and I am not aware if there is such a thing in set theory and if so what is it called. Mainly I have several sets that I am interested in their cartesian product. But this cartesian product should not be a set of ordered pairs but a set of sets. Basically unordered pairs. I wonder if this concept is well defined and what is it called. Thanks. P. -- 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.
