Re: [algogeeks] Divide the array into groups
@ ^ Why do you try hard not to understand the question or what one meant by the question and instead try hard to find out flaws. I mean ain't that obvious that you need to divide into minimum number of groups? -- Rohit Saraf Third Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Re: Frequently one of the Top Question Asked in Amazon
Isn't it just a coding question? @ ^ : your code is not clean enough for anyone to read. As far as data-structures are concerned... a stack and a queue suffice. There is no algorithmic issue I can see. So, I guess you should solve these problems yourself or some programming forum. For those who don't know spiral order traversal : There is always something called *google. *Please google it out before asking. -- 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] Divide the array into groups
I don't see why you need O(n^2) time for rearranging. It can be done in O(n log n) if you maintain the index along with every element. Then reordering would mean sort as per the indices. -- Rohit Saraf Third Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] and or tree
Let No of flips reqd = solve(N, V) L=left subtree. R = right subtree N = root node. If V=0, then only problem is when L = 1 and R=1. (otherwise atmax changing the root node will do) then ans = min(solve(L, 0), solve(R,0)) + (R=AND)?0:1 If V=1 then only problem is when L=0 and R=0 similarly dealt. If V=something else output -1 -- 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] and or tree
Of course memoization is needed (Can be done by using an array and the fact that it is complete binary tree.) Also if the later half of the array is all 0, then 1 cannot be obtained at the root and vice versa. -- 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] Sparse Matrix multiplication
http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node20.html -- 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] find a way
@Divya : In that case, a greedy solution does not seem to exist. You need to use the traditional DP way. -- 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] Re: L values and r values
Perhaps it is not available. -- 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] Google Question
No special approach is needed. In O(log n), you can find the minimum element of the array which makes your circular array - normal array. -- 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] large array initialization
datastructure Validity - integer Value - Whatever Make an array of the above datastruct (say d[n+1] starting from 1) integer maxcount Init(val) d[n+1].Value = val d[n+1].Validity = ++maxcount Set(i,x) d[i].Value=x d[i].Validity = d[n+1].Validity+1 Get(i) if( d[i].Validity = d[n+1].Validity ) then d[n+1].Value else d[i].Value There is a practical issue that Validity may become larger than int etc... however that too can be easily overcome. -- Rohit Saraf Third Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] search a 2d sorted array in less than O(n)
Trivial algorithm : (Assuming it is in ascending order in both columns and rows) logarithmic time in max(n,m) Divide the 2-d table to 4 parts, the -right-bottom-most and the left-bottom-most are the smallest and largest values in the subtable. It should be clear that atleast two subtables can be rejected straightforward from just this info. Hence the complexity T(m,n) = 2 * T(m/4,n/4) + c Rohit Saraf Third Year Undergraduate Compter Science Engineering IIT Bombay -- 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] clear screen in mysql
See it here : jfgi http://www.urbandictionary.com/define.php?term=jfgi -- 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] clear screen in mysql
well i just wanted u to know that there is a very nice place called www.google,com where u can find many things. -- 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] ACTIVATION OF WINDOWS 7
So, is this the place for that? And apart from that, it is illegal to discuss about this on public threads. (if you don't know, this thread is public) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 2:42 PM, vishard sankhyan er.vish...@gmail.comwrote: HI ANY ONE HELP OUT I WANT TO ACTIVATE MY WINDOWS 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. -- 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] There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers
Why not just change the definition of when one number is bigger than another and do normal sort ? I guess that is better and simpler. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 7:52 AM, Anurag Sharma anuragvic...@gmail.comwrote: Keep 2 pointers 'start' and 'end' and make them point to start and beginning of the array. Now keep decresing *end* pointer until an odd element is found Keep increasing the *start* pointer until an even element is found swap the elements at start and end Continue the above 3 steps till startend Now the start/end points to a border element which divides the array in 2 parts, 1st have having all odd numbers and 2nd half with all even numbers. Now use any inplace sorting algorithm to sort in descending order the portion containing all odd numbers and in increasing order the portion containing all even numbers. Hope its clear. Anurag Sharma On Sun, Jun 20, 2010 at 2:15 AM, vijay auvija...@gmail.com wrote: There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order. You are not allowed to use any extra array and it has to use a conventional sorting mechanism and should not do any pre or post processing -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: SPOJ:RRSCHED
You must be doing some useless iterations . Otherwise, TLE is too strange for this prob. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 19, 2010 at 9:15 AM, Shravan shravann1...@gmail.com wrote: Even I have implemented it using arrays, but I am getting a TLE. Here's the code http://ideone.com/EfYRa On Jun 19, 8:15 am, Anand anandut2...@gmail.com wrote: It can be done using simple array data structure why do we need complex data structure. Here is how I did. Let me know if I understood correctly. http://codepad.org/rMbTI8PJ On Fri, Jun 18, 2010 at 8:15 AM, Shravan shravann1...@gmail.com wrote: I am trying to solve the problemhttp://www.spoj.pl/problems/RRSCHED/ . And a naive approach doesn't seem to work .What sort of data structure do I need. -- 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 .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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] finding nearest neighbour
It was my lab assignment prob last year. Will send u if i happen to find it by chance. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Jun 14, 2010 at 10:31 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Given n points in the space. Now given a new point you have to find the nearest neigbour to it from initial n points This can be done in O(n), a trivial solution. This can also be accomplished in O(logn) by space partioning. here is a link: http://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning can anybody give a pseudo code or commented C code to impliment it. I do not understood how to implement it. this is a google interview question and its variation is a amazon's question. :) -- 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] Re: SPOJ:RRSCHED
No -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 3:22 PM, Shravan shravann1...@gmail.com wrote: Did you see the code which I have posted. On Jun 20, 2:31 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: You must be doing some useless iterations . Otherwise, TLE is too strange for this prob. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 19, 2010 at 9:15 AM, Shravan shravann1...@gmail.com wrote: Even I have implemented it using arrays, but I am getting a TLE. Here's the code http://ideone.com/EfYRa On Jun 19, 8:15 am, Anand anandut2...@gmail.com wrote: It can be done using simple array data structure why do we need complex data structure. Here is how I did. Let me know if I understood correctly. http://codepad.org/rMbTI8PJ On Fri, Jun 18, 2010 at 8:15 AM, Shravan shravann1...@gmail.com wrote: I am trying to solve the problemhttp:// www.spoj.pl/problems/RRSCHED/ . And a naive approach doesn't seem to work .What sort of data structure do I need. -- 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 algogeeks%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 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. -- 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] Integer from number in words
You need to specify the max level upto which you want it to work. For rest, is there any prob? I can't see any. you see ninety - 90 u see thousand - 90*1000 + and so on -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 6:34 PM, debajyotisarma sarma.debajy...@gmail.comwrote: How to device an algorithm for converting the number given in words to an int? Eg: i/p : ninety thousand two hundred fourth three o/p: 90243 even the number can be very big ... in million or billion ... -- 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] back edges
You start from a vertex, then if you reach that vertex before dfs on that vertex finishes, then the edge u used to reach it is a back edge. And if you reach after the dfs finishes on that node, it's a cross edge. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 6:23 PM, Piyush Verma 114piy...@gmail.com wrote: back edge is usefull to find a cycle in graph in finding cycle algorithm ( using DFS) we mark every edge as back edge or tree edge then traverse again total number of back edges give the number of cycle present in directed graph. -- 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] STRONG ACTION GIRL REAL STUNTS SWEET AND SEXY http://businproz.blogspot.com/ http://businproz.blogspot.com/ http://businproz.blogspot.com/
Someone ban this spammer -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: coins
Yes right, i forgot the 1 -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Jun 17, 2010 at 6:05 PM, Dave dave_and_da...@juno.com wrote: No. The greedy algorithm also works on the U.S. coinage system, where the coins are 1, 5, 10, 25. Again, the rule is that there must be a 1 unit coin, and each coin has at least twice the value of the preceeding one. Dave On Jun 16, 11:34 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @Dave: The greedy will only work if the coins are k,2k,3k,4k, nk without any of these missing Clear? (Perhaps i did not write it clearly as i was on mobile) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Jun 17, 2010 at 10:00 AM, Dave dave_and_da...@juno.com wrote: The greedy algorithm doesn't work, e.g., when the coins are 1, 5, and 8 units, and you want to make 15 units. In this case, the greedy algorithm would choose 8, 5, 1, 1, whereas the optimal is 5, 5, 5. I believe the criterion for the greedy algorithm are that the smallest coin be 1 unit and each successive coin be at least twice the value of its predecessor. Dave On Jun 16, 9:19 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: If the coins are all multiple of some number k, you can greedily give as much as possible to the higher domination. Otherwise still, there is an optimal substructure and u can make a recurrence and use memoization(i.e. DP) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 -- 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.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- 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.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] coins
If the coins are all multiple of some number k, you can greedily give as much as possible to the higher domination. Otherwise still, there is an optimal substructure and u can make a recurrence and use memoization(i.e. DP) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: coins
@Dave: The greedy will only work if the coins are k,2k,3k,4k, nk without any of these missing Clear? (Perhaps i did not write it clearly as i was on mobile) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Jun 17, 2010 at 10:00 AM, Dave dave_and_da...@juno.com wrote: The greedy algorithm doesn't work, e.g., when the coins are 1, 5, and 8 units, and you want to make 15 units. In this case, the greedy algorithm would choose 8, 5, 1, 1, whereas the optimal is 5, 5, 5. I believe the criterion for the greedy algorithm are that the smallest coin be 1 unit and each successive coin be at least twice the value of its predecessor. Dave On Jun 16, 9:19 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: If the coins are all multiple of some number k, you can greedily give as much as possible to the higher domination. Otherwise still, there is an optimal substructure and u can make a recurrence and use memoization(i.e. DP) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Re: Cycle in Undirected and Directed Graphs
@vivek : was that a joke? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Jun 14, 2010 at 11:40 AM, souravsain souravs...@gmail.com wrote: @sharad: Do you have some article that explains cycle detection in bfs? Will be of help if you can share that or book or so which explains cycle detection via bfs. @amit: Both in directed and undirected graphs you can find a cycle in O(|v|) time using a dfs. See Algorithm Design Manual Second Edition, chapter 5 by Stiev. S. Skiena. Its a very good explanation. On Jun 14, 6:19 am, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: In any directed graph just check if dfs has a back edge. For undirected, check if there is a nontree edge -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 -- 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] unique number in an array
Just to point out : how many times have you all repeated this -- Xor works only -- even number of times. It will not work... Why don't you all read some earlier posts before posting. :P -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Tue, Jun 15, 2010 at 4:52 PM, Krishan Malik srikrishanma...@gmail.comwrote: Priyanka, will XOR work for {1,1,1,3,3,4,5} Thanks Sri On Mon, Jun 14, 2010 at 7:02 PM, Priyanka Chatterjee dona.1...@gmail.com wrote: XOR all the elements of array, the remaining value is the required unique number. (XORing two same numbers results in zero) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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. -- SK Malik -- 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] output
I read that. But still it should not be compiled as per the standard. The latest GNU C/C++ compiler correctly fails to compile this -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 10:44 AM, divya jain sweetdivya@gmail.comwrote: sorry for the silly question i got rhe point.. @ rohit compiler is doing rite..read mahesh's explanatn On 13 June 2010 08:27, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: This is very bad. Change your compiler if it compiles this stuff :) btw.. which compiler is it? Output for me : ro...@rohit-laptop:~/dump$ gcc c.c c.c: In function ‘main’: c.c:14: error: incompatible types when assigning to type ‘char[20]’ from type ‘char *’ c.c:15: error: incompatible types when assigning to type ‘char[20]’ from type ‘char *’ -- 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 On Sun, Jun 13, 2010 at 8:13 AM, Mahesh_JNU mahesh.jnumc...@gmail.comwrote: Well As we know for copying the string we can can copy it as a simple variable as in case of address copying. when u r doing names[3] = names[4] , it means u r trying to copy it directly bt in the case of char *names[] , as it is the array of pointers so u can copy the address from one pointer to another pointer Thanks On Sat, Jun 12, 2010 at 9:12 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { char names[][20]={ roshni, manish, sona, baiju, ritu }; int i; char *t; t=names[3]; names[3]=names[4]; names[4]=t; for(i=0;i=4;i++) printf(%s,names[i]); printf(\n); return 0; } here i get l value required as error and if i replace char names[][2] with char *names[].. then there is no error nd the names[3] n names[4] interchange pl explain why??? -- 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. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] c- pointers
@divya: u r rite.. that * should not be there -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 11:07 AM, divya jain sweetdivya@gmail.comwrote: ptr is a pointer naaa...then why ptr-p=*((arr+1)-arr) ??? why not (arr+1)-arr ?? i knw m wrong somewhr...plz correct me On 13 June 2010 07:57, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: agreed . On Sun, Jun 13, 2010 at 7:48 AM, sharad kumar aryansmit3...@gmail.comwrote: 111 222 333 344 ptr++ -u do posst increment hence it goes to 1 ptr-p=*((arr+1)-arr)=1 llrly for other cases when u do *ptr++ due to operator precedence ptr++ is done and then dereferenced. hence u get 222 next *++ptr the ptr is incremented after dereferencing hence u get 333 next ++*ptr here the value t ptr s incrementas it is treated as++(*ptr) hence u get 3 but others refer to location hence 44 On Sat, Jun 12, 2010 at 9:21 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { static int arr[]={0,1,2,3,4}; int *p[]={arr,arr+1,arr+2,arr+3,arr+4}; int **ptr=p; ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *++ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); ++*ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); return 0; } wat shd b the o/p n why... -- 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. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] c array
which compiler do you use? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 10:46 AM, divya jain sweetdivya@gmail.comwrote: hmm..the prob is here wid my compiler...!! anyways thanks to all On 13 June 2010 10:28, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: oh.. yes.. my mistake (strings\0).length=8 :P -- 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 On Sun, Jun 13, 2010 at 10:24 AM, Rahul Kushwaha rahul.kushw...@gmail.com wrote: #includestdio.h int main() { char str[7]=strings; printf(%s\n,str); return 0; } it is showing error on code block and dev cpp also... this is an error no doubt. also mentioned in denis m ritchie -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] union- c
what is this for... and which conversion are you talking abt? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 12, 2010 at 11:20 PM, divya sweetdivya@gmail.com wrote: #include stdio.h main() { union { long l_e; float f_e; } u; long l_v; float f_v; l_v = u.l_e = 10; printf(%f , (float)l_v); printf(%f , u.f_e); f_v = u.f_e = 3.555; printf(%d , (long)f_v); printf(%d , u.l_e); } hw to do the conversion here.. -- 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] Problem with Virtual Function
M-speed is private and you cannot call it from outside myPlugin. (though i did not understand what u wanted to say) Can you write ur prob explicitly? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 12:20 PM, akshay khatri akshaykhatri...@gmail.comwrote: I have the following code structure in my file myPlugin.h , i have defined this virtual int speed(); and gave a dummy implementation in myPlugin.cpp In another file otherPlugin.h I have included this line: #include myPlugin.h private: int m_speed; also class otherPlugin inherits myPlugin (public scope) I want to redefine speed in otherPlugin.cpp How should I return a value fromspeed() in it ? int myPlugin::speed() { return m_speed; } or int otherPlugin::speed() { return m_speed; } or anything else ? The error I get is that: m_speed was not declared in this scope. -- 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] Problem with Virtual Function
Make those functions public And even if M_speed is public of another class, it is still it another class, you cannot just address it like m_speed in other classes. Does it help? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 12:31 PM, akshay khatri akshaykhatri...@gmail.comwrote: Hi On 13 June 2010 12:26, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: M-speed is private and you cannot call it from outside myPlugin. (though i did not understand what u wanted to say) Can you write ur prob explicitly? I want to use speed() and direction() defined in myPlugin.h in otherPlugin.cpp. How can I use it(syntax) ? If I try to return a variable such as m_speed(even if defined in public part of class otherPlugin) , it gives an error. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 12:20 PM, akshay khatri akshaykhatri...@gmail.com wrote: I have the following code structure in my file myPlugin.h , i have defined this virtual int speed(); and gave a dummy implementation in myPlugin.cpp In another file otherPlugin.h I have included this line: #include myPlugin.h private: int m_speed; also class otherPlugin inherits myPlugin (public scope) I want to redefine speed in otherPlugin.cpp How should I return a value fromspeed() in it ? int myPlugin::speed() { return m_speed; } or int otherPlugin::speed() { return m_speed; } or anything else ? The error I get is that: m_speed was not declared in this scope. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Problem with Virtual Function
yes.. it should... make sure your virtual function is either public or protected but not private. and if it doesn't can u tell me the error? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 12:47 PM, akshay khatri akshaykhatri...@gmail.comwrote: I meant this: let me explain it like this. I have *virtual int speed()* in class A.(in file A.h) I inherited class in class B(in file B.h) as class B:public A class B have a private member m_speed. Now I have to return m_speed from speed() from class B as I would instantiate an object of class B to use it. So if write my prgram like this: class B:public A { private: int m_speed(); } int B::speed() { return m_speed; } would it work ? On 13 June 2010 12:37, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Make those functions public And even if M_speed is public of another class, it is still it another class, you cannot just address it like m_speed in other classes. Does it help? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 12:31 PM, akshay khatri akshaykhatri...@gmail.com wrote: Hi On 13 June 2010 12:26, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: M-speed is private and you cannot call it from outside myPlugin. (though i did not understand what u wanted to say) Can you write ur prob explicitly? I want to use speed() and direction() defined in myPlugin.h in otherPlugin.cpp. How can I use it(syntax) ? If I try to return a variable such as m_speed(even if defined in public part of class otherPlugin) , it gives an error. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 12:20 PM, akshay khatri akshaykhatri...@gmail.com wrote: I have the following code structure in my file myPlugin.h , i have defined this virtual int speed(); and gave a dummy implementation in myPlugin.cpp In another file otherPlugin.h I have included this line: #include myPlugin.h private: int m_speed; also class otherPlugin inherits myPlugin (public scope) I want to redefine speed in otherPlugin.cpp How should I return a value fromspeed() in it ? int myPlugin::speed() { return m_speed; } or int otherPlugin::speed() { return m_speed; } or anything else ? The error I get is that: m_speed was not declared in this scope. -- 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. -- 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
Re: [algogeeks] Problem with Virtual Function
Put the function speed or its declaration inside the class b. Did u forget that? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] c array
@ram : oh.. that cygwin thing.. why don't you use pure gcc then... why use minimalistic one? @divya: isn't it obsolete yet? Did not see anyone using it after I started using a computer :D. Do you use it because your prof's force you. If not try g++/gcc. That is the standard the best compiler today. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 1:47 PM, divya jain sweetdivya@gmail.comwrote: i use tc On 13 June 2010 13:11, ram karthik.gin...@gmail.com wrote: @rohit bro http://www.mingw.org/ *MinGW*, a contraction of Minimalist GNU for Windows, is a port of the GNU Compiler Collection (GCC), and GNU Binutils, for use in the development of native Microsoft Windows applications. *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On Behalf Of *Rohit Saraf *Sent:* 13 June 2010 08:19 *To:* algogeeks@googlegroups.com *Subject:* Re: [algogeeks] c array @ram : i guess you have used some longer string and not strings btw.. what is Mingw ? gcc/g++ is not mingw, i guess -- 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 On Sun, Jun 13, 2010 at 8:13 AM, ram karthik.gin...@gmail.com wrote: D:\code\samplecode\main.cpp|5|error: initializer-string for array of chars is too long| I get this error on gcc (Mingw) . Though the array indexing starts from 0. The length specified in char str[7] is always straightforward . in this case char str[7] . the length of str is seven not eight ;hence the error -- ram *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On Behalf Of *sharad kumar *Sent:* 13 June 2010 07:59 *To:* algogeeks@googlegroups.com *Subject:* Re: [algogeeks] c array hey array indexing starts from 0 rite?? then y shld u get overflow in first place.. s t r i n g s \0 0 1 2 3 4 5 6 7 On Sat, Jun 12, 2010 at 9:14 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { char str[7]=strings; printf(%s\n,str); return 0; } here i m nt getting overflow error whereas if i write stringss instead of strings then there is overflow error.. isnt null stored after s in strings nd 1st case shd also give overflow??? -- 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. -- 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. -- 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
Re: [algogeeks] c- pointers
@jalaj: exactly... so you(@divya) are right. Sharad's ans was right but logic wasn't. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 2:35 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: actually when you subtract two pointers ... its get divided by the size of the variable type its point two... for example.. if you do .. p+1... where let say p is 200 and points to an int type variable then p+1 is 202...(assuming int is of size 2) so (p+1)-p..i.e 202-200 is 1 and not 2 On Sun, Jun 13, 2010 at 1:46 PM, divya jain sweetdivya@gmail.comwrote: bt the ans that sharad gave is ryt.. acc to me 1st row n 1st col of o/p shd b 2 (if size of int is 2) bt it is 1... On 13 June 2010 12:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya: u r rite.. that * should not be there -- 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 On Sun, Jun 13, 2010 at 11:07 AM, divya jain sweetdivya@gmail.comwrote: ptr is a pointer naaa...then why ptr-p=*((arr+1)-arr) ??? why not (arr+1)-arr ?? i knw m wrong somewhr...plz correct me On 13 June 2010 07:57, Mahesh_JNU mahesh.jnumc...@gmail.com wrote: agreed . On Sun, Jun 13, 2010 at 7:48 AM, sharad kumar aryansmit3...@gmail.com wrote: 111 222 333 344 ptr++ -u do posst increment hence it goes to 1 ptr-p=*((arr+1)-arr)=1 llrly for other cases when u do *ptr++ due to operator precedence ptr++ is done and then dereferenced. hence u get 222 next *++ptr the ptr is incremented after dereferencing hence u get 333 next ++*ptr here the value t ptr s incrementas it is treated as++(*ptr) hence u get 3 but others refer to location hence 44 On Sat, Jun 12, 2010 at 9:21 PM, divya sweetdivya@gmail.comwrote: #includestdio.h int main() { static int arr[]={0,1,2,3,4}; int *p[]={arr,arr+1,arr+2,arr+3,arr+4}; int **ptr=p; ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *ptr++; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); *++ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); ++*ptr; printf(%d %d %d\n,ptr-p,*ptr-arr,**ptr); return 0; } wat shd b the o/p n why... -- 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. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- 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. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you
Re: [algogeeks] union- c
If you are not able to print the long int and that's the prob, you can use %ld instead of %d -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 1:49 PM, divya jain sweetdivya@gmail.comwrote: its an o/p questn.. conversion wen ur variable is long..nd u r printing using %f...i dont know how to perform conversion from float to int long nd vice versa.. pl help On 13 June 2010 12:12, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: what is this for... and which conversion are you talking abt? -- 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 On Sat, Jun 12, 2010 at 11:20 PM, divya sweetdivya@gmail.com wrote: #include stdio.h main() { union { long l_e; float f_e; } u; long l_v; float f_v; l_v = u.l_e = 10; printf(%f , (float)l_v); printf(%f , u.f_e); f_v = u.f_e = 3.555; printf(%d , (long)f_v); printf(%d , u.l_e); } hw to do the conversion here.. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: bits
@Souravsain : Is there any serious problem in this. Anyone can just add a [C++] in the subject and uninterested people can make filters in gmail :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 6:35 PM, souravsain souravs...@gmail.com wrote: @divya Lets keep discussions in t his group limited to Algos and problems neutral to any language. Request you to post these C++ / C language specific questions to those language specific groups. This will not only help this group remain confined to its core purpose but will help you get better insights to ur problem by language specific geeks there. For C++ I would recommend you to try the group http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en. Regards, Sourav On Jun 13, 2:29 pm, divya sweetdivya@gmail.com wrote: tell the o/p of following with explanations 1. #includestdio.h int main() { struct value { int bit1:1; int bit3:4; int bit4:4; }bit; printf(%d\n,sizeof(bit)); return 0; } 2. #includestdio.h int main() { struct value { int bit1: 1; int bit3: 4; int bit4: 4;} bit={1,2,2}; printf(%d %d %d\n,bit.bit1,bit.bit3,bit.bit4); return 0; } 3 can bit field be used in union?? -- 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] Re: bits
I agree mass bombarding with such questions is not very good.. but one doesn't join groups and all for getting a few doubts cleared. Anyways, i have no problem with anything. :D -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 9:26 PM, souravsain souravs...@gmail.com wrote: and @rohit you will get better insight into the topic by more expert people by posting the question in right forum. I guess thats a win-win situation for one who has the question as he is get to know more and for people you are interested in going through C++ questions as they will read views from many more experts :) On Jun 13, 7:31 pm, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @Souravsain : Is there any serious problem in this. Anyone can just add a [C++] in the subject and uninterested people can make filters in gmail :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 6:35 PM, souravsain souravs...@gmail.com wrote: @divya Lets keep discussions in t his group limited to Algos and problems neutral to any language. Request you to post these C++ / C language specific questions to those language specific groups. This will not only help this group remain confined to its core purpose but will help you get better insights to ur problem by language specific geeks there. For C++ I would recommend you to try the group http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en. Regards, Sourav On Jun 13, 2:29 pm, divya sweetdivya@gmail.com wrote: tell the o/p of following with explanations 1. #includestdio.h int main() { struct value { int bit1:1; int bit3:4; int bit4:4; }bit; printf(%d\n,sizeof(bit)); return 0; } 2. #includestdio.h int main() { struct value { int bit1: 1; int bit3: 4; int bit4: 4;} bit={1,2,2}; printf(%d %d %d\n,bit.bit1,bit.bit3,bit.bit4); return 0; } 3 can bit field be used in union?? -- 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.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- 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.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] Cycle in Undirected and Directed Graphs
In any directed graph just check if dfs has a back edge. For undirected, check if there is a nontree edge -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] trees
Repeated q. Search in the group -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] c array
@ram : i guess you have used some longer string and not strings btw.. what is Mingw ? gcc/g++ is not mingw, i guess -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 8:13 AM, ram karthik.gin...@gmail.com wrote: D:\code\samplecode\main.cpp|5|error: initializer-string for array of chars is too long| I get this error on gcc (Mingw) . Though the array indexing starts from 0. The length specified in char str[7] is always straightforward . in this case char str[7] . the length of str is seven not eight ;hence the error -- ram *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On Behalf Of *sharad kumar *Sent:* 13 June 2010 07:59 *To:* algogeeks@googlegroups.com *Subject:* Re: [algogeeks] c array hey array indexing starts from 0 rite?? then y shld u get overflow in first place.. s t r i n g s \0 0 1 2 3 4 5 6 7 On Sat, Jun 12, 2010 at 9:14 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { char str[7]=strings; printf(%s\n,str); return 0; } here i m nt getting overflow error whereas if i write stringss instead of strings then there is overflow error.. isnt null stored after s in strings nd 1st case shd also give overflow??? -- 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. -- 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] output
This is very bad. Change your compiler if it compiles this stuff :) btw.. which compiler is it? Output for me : ro...@rohit-laptop:~/dump$ gcc c.c c.c: In function ‘main’: c.c:14: error: incompatible types when assigning to type ‘char[20]’ from type ‘char *’ c.c:15: error: incompatible types when assigning to type ‘char[20]’ from type ‘char *’ -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 13, 2010 at 8:13 AM, Mahesh_JNU mahesh.jnumc...@gmail.comwrote: Well As we know for copying the string we can can copy it as a simple variable as in case of address copying. when u r doing names[3] = names[4] , it means u r trying to copy it directly bt in the case of char *names[] , as it is the array of pointers so u can copy the address from one pointer to another pointer Thanks On Sat, Jun 12, 2010 at 9:12 PM, divya sweetdivya@gmail.com wrote: #includestdio.h int main() { char names[][20]={ roshni, manish, sona, baiju, ritu }; int i; char *t; t=names[3]; names[3]=names[4]; names[4]=t; for(i=0;i=4;i++) printf(%s,names[i]); printf(\n); return 0; } here i get l value required as error and if i replace char names[][2] with char *names[].. then there is no error nd the names[3] n names[4] interchange pl explain why??? -- 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. -- Mahesh Giri MCA Final Sem JNU, New Delhi -- 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] Re: Array Problem
@Satya: I don't think what you have coded will work.. though i have not read the whole code. Don't you think a simple divide and conquer scheme would work...(almost like the mergesort) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 12, 2010 at 9:06 PM, Satya satya...@gmail.com wrote: This problem seems to be finding the maxdiff in an array. int maxdiff ( int A[], int n ) { // write your code here int max_diff = A[1] - A[0]; int min_element = A[0]; int i; for(i = 1; i n; i++) { if(A[i] - min_element max_diff) max_diff = A[i] - min_element; if(A[i] min_element) min_element = A[i]; } if(max_diff 0) max_diff = 0; return max_diff; } . Satya On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: infix
@vivek: read again: ) = -1 ( = +1 Keep a sum of all these as u iterate. That should never be negative Plus check for these types (if you need correct arithmetic expressions as well *some operator followed by )* * or / after a ( () -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, Jun 11, 2010 at 12:07 PM, Vivek Sundararajan s.vivek.ra...@gmail.com wrote: @Rohit Consider : (a+)b The above is not well formed! :) On 11 June 2010 11:58, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @BALARUKESH : What are you saying !! and Why would this not work As you start you get sum -1 at start itself. Hence you quit. The sum should be 0 always and 0 at last -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, Jun 11, 2010 at 11:09 AM, BALARUKESH sbalarukesh1...@gmail.comwrote: The increment and decrement method wont work correctly for all cases Ex:- ))a+b(( This is not a well formed parenthesis... But satisfies the algorithm. The better way is to use a stack... When u find a ' ( ' push it into the stack and when u find a ' )' pop off the top element. Finally the stack should be empty. If [stack has one or more ' ( ' ] or [the stack is empty and exp is not empty] then it is not a well formed parenthesis... -- 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. -- Reduce, Reuse and Recycle Regards, Vivek.S -- 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] Print large Fibonacci numbers
Fibonacci numbers can be calculated very efficiently using matrix multiplications. I hope you can think it/google it now.. that is better than me writing so much again :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, Jun 11, 2010 at 8:12 PM, Raj N rajn...@gmail.com wrote: How to print very large Fibonacci numbers eg fib(1000). My approach: When any one of fib(i-1) or fib(i-2) has more than 12 or 13 digits, partition them into groups of 4 digits and put them in a linked list. fib(i-1) is put in list1, fib(i-2) in list2. Perform the addition of these long numbers and overwrite in list2. Now to find next fib list1 is taken as fib(i-2) and list2 as fib(i-1) and this repeats until we approach the given number and finally the result is in list2. As the number of digits goes on increasing, the list is constructed dynamically. If anyone has an efficient approach pls tell me. -- 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] sum to x
I guess it can be done in efficiently using a simple divide and conquer scheme almost imitating mergesort. Can you think of it now? :D -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, Jun 11, 2010 at 10:07 PM, sharad kumar sharad20073...@gmail.comwrote: all possible pairs -- 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] Re: binary nos
write an efficient algo to compute no. of sequences of n binary digits that do not contain 2 1's in a row. eg 111 is invalid whereas 1001001 is valid. HERE the number of sequences comes to be a fibonacci number , precisely fib(n+2). So this prob is equivalent to finding fibonacci numbers -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh singh.sund...@gmail.comwrote: @rohit: fibonacci sequence may be the answer to the prob, but I am curious why? I haven't come across any such fib sequence property... On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @junta : are fibonacci sequence is the answer of the prob, it is not used :D -- 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 On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @debajyoti: read the prob before posting -- 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 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: First 20 fibo no as follows with binary form 0 = 0 1 = 1 1 = 1 2 = 10 3 = 11 5 = 101 8 = 1000 13 = 1101 21 = 10101 34 = 100010 55 = 110111 89 = 1011001 144 = 1001 233 = 11101001 377 = 10001 610 = 1001100010 987 = 011011 1597 = 1100001 2584 = 10111000 4181 = 101010101 Now please explain how fibo no is coming under consideration.Both kind of no is mixed here. On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Fib comes because she wants the number of such sequences -- -- 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. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] infix
) = -1 ( = +1 Keep a sum of all these as u iterate. That should never be negative Plus check for these types (if you need correct arithmetic expressions as well some operator followed by ) * or / after a ( () -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] c output
c 1 6,2 u might be expecting 5,1 if u are forgetting the newline character :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: binary nos
@debajyoti: read the prob before posting -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma sarma.debajy...@gmail.comwrote: First 20 fibo no as follows with binary form 0 = 0 1 = 1 1 = 1 2 = 10 3 = 11 5 = 101 8 = 1000 13 = 1101 21 = 10101 34 = 100010 55 = 110111 89 = 1011001 144 = 1001 233 = 11101001 377 = 10001 610 = 1001100010 987 = 011011 1597 = 1100001 2584 = 10111000 4181 = 101010101 Now please explain how fibo no is coming under consideration.Both kind of no is mixed here. On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Fib comes because she wants the number of such sequences -- -- 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. -- 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] Single ordered list
I had answered this question(of multiple lists) 2 or three days back. Go into the archive if u wanna see :P -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 6:52 PM, Raj N rajn...@gmail.com wrote: But what if the same same problem is extended for multiple lists. As the individual lists have already been sorted, is there any efficient way or any other sorting algo which exploits this fact. On Tue, Jun 8, 2010 at 10:56 PM, divya jain sweetdivya@gmail.comwrote: merging as in merge sort. On 8 June 2010 19:59, Raj N rajn...@gmail.com wrote: What is the most efficient way of combining 2 separate ordered list into a single ordered list ? -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: binary nos
@junta : are fibonacci sequence is the answer of the prob, it is not used :D -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @debajyoti: read the prob before posting -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: First 20 fibo no as follows with binary form 0 = 0 1 = 1 1 = 1 2 = 10 3 = 11 5 = 101 8 = 1000 13 = 1101 21 = 10101 34 = 100010 55 = 110111 89 = 1011001 144 = 1001 233 = 11101001 377 = 10001 610 = 1001100010 987 = 011011 1597 = 1100001 2584 = 10111000 4181 = 101010101 Now please explain how fibo no is coming under consideration.Both kind of no is mixed here. On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Fib comes because she wants the number of such sequences -- -- 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. -- 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] Re: sorted 2-d array
@senthilnathan : very nice indeed -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: constraints satisfied?
Your time complexity is not O(c) but O(n^2) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: binary nos
Fib comes because she wants the number of such sequences -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: ds
which is just the recursive version of the abovementioned iterative solution. P.S. -Please remove this quoted text when you are composing -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] binary nos
So u want efficient algo for fibonacci numbers? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] constraints satisfied?
A simple solution : Use the union find data structure and add notes for x1...xn and the negation of all these. Every constraint makes one union. Finally check if for any i , xi and !xi are connected. It is worst case O(n lg n) for sure where n is the number of equations. Average case is much better. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: binary nos
getting fibonacci nos is trivial using matrix multiplication in almost constant time. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] ds
Of course you should do it via swappings.. why would one think of anything else :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Mon, Jun 7, 2010 at 10:39 PM, vadivel selvaraj gct.vadi...@gmail.comwrote: Hi guys d soln z quite easy by swapping the variables.. consider a1a2a3a4b1b2b3b4 In the first iteration, swap (a2,b1),(a4,b3) giving a1b1a3b3a2b2a4b4 In the second iteration, swap (a3b3,a2b2) which gives d soln... a1b1a2b2a3b3a4b4... Any comments on dis?? On Mon, Jun 7, 2010 at 1:51 PM, Raj N rajn...@gmail.com wrote: @sain: But the question demands O(n) time On Mon, Jun 7, 2010 at 3:35 AM, Anand anandut2...@gmail.com wrote: Here is my approach is o(n). http://codepad.org/YAFfZpxO http://codepad.org/YAFfZpxO On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar sharad20073...@gmail.comwrote: this is ques by adobe and they want inplace soln.. -- 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. -- Simplicity is prerequisite for reliability. – Edsger W. Dijkstra -- 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] Re: Largest even length palindrome in a string!!
but actually we need something better as per prob, cannot be done in O(n). so we need to think of something like O(n lg n) or O( n ^ 3/2) :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] array question
No it will be O(n). -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr
Tokenization is done in linear time. Just save the words in an list (And what makes you think of non-linearity in tokenization!) And then iteration over the tokens is trivially linear. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 5, 2010 at 11:01 AM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Shobhit @Rohit Is it done it linear time?? I dont think so... On Sat, Jun 5, 2010 at 9:33 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Tokenize the string and print it reverse! -- -- 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. -- Luv, S.Antony Vincent Pandian -- 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] Quick short stack space reduction
Actually he means the case when you implement quicksort using stacks. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] dynamic vs greedy aproach
Greedy can be used to find one solution which has some special characteristics. It should be like - You are able to say that if for any instance of size k the greedy and the optimal solution match, then for any corresponding instance of size k+1, the greedy solution is atleast as good as optimal. Dynamic programming is a more general approach which is generally used when there is optimal substructure and has mostly found use in doing exponential looking problems in polynomial time. i hope u understood -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] o/p
If you make it unsigned short int.. then it goes to 65535 on g++/gcc -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr
Ok. so you have a list. Iterating over it is linear isn't it? Ahh... you will need a doubly linked list or an arraylist.does it solve ur prob? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 5, 2010 at 5:17 PM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Rohit I accept that tokenization is linear. But how do you say iteration over tokens in the new list and printing in reverse order as linear? On 6/5/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Tokenization is done in linear time. Just save the words in an list (And what makes you think of non-linearity in tokenization!) And then iteration over the tokens is trivially linear. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 5, 2010 at 11:01 AM, Antony Vincent Pandian.S. sant...@gmail.com wrote: @Shobhit @Rohit Is it done it linear time?? I dont think so... On Sat, Jun 5, 2010 at 9:33 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Tokenize the string and print it reverse! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 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. -- Luv, S.Antony Vincent Pandian -- 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. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- 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] Re: o/p
oh... why did u put %u. i did not even notice that :P -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Largest even length palindrome in a string!!
What makes you think it is O(n^3). I did not read the code one but divya's solution seems to be O(n^2) for worst case. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Largest even length palindrome in a string!!
Just read your code. It wont even work. Do you assume only one even length palindrome!? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] One question on Heap sort
Can u elaborate on the 2nd step. btw, did u understand my soln? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
This is almost the most basic dp. Read some of the examples from eva tardos. That would help. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
@jitendra: How can you say that no polynomial algo can be found. I think you are wrong. A simple memoized formulation will make this polynomial because of the optimal substructure.. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
Oh i am talking only about printing the total number of solutions... If you backtrack... Obviously it would not be polynomial -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Quick short stack space reduction
if you short the larger one first, then the smaller one will be in the stack for a long time. Which is wasting stack space. Now stop shorting and start sorting ! :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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]
Make a hashmap... Any problem doing that? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
What precisely did you not understand?? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Print the string in reverse order (not revstr)
Have you posted the same question twice or i am feeling sleepy? -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
Exactly that's what you need to do. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
@divya: but still haven't you seen Jagadish's example? It is a counterexample to your greedy approach. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: Can you solve this?
Still the solution will be similar and actually a bit simpler. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
A*(B+C*D) -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Removing extra parentheses in an infix string
So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] Valid permutation of the brackets
why don't you make use of the optimal substructure. You can easily use the recurrence relation as DP @all : people don't just paste your code. Words are better than code -- 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] Check if 2 linked lists are identical
simple in place O(n lg n) solution. Choose a pivot in first array and partition it like in quicksort. Find the pivot in second array and partition. Now recurse on both halves. At any point if no of elements in array are not equal... Abort! -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: another google telephone interview question
Heap maintains the word and frequency count On 5/18/10, 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) 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.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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] partion of array
@divya : descending order sorting works. BRILLIANT !! On 5/17/10, divya jain sweetdivya@gmail.com wrote: my algo on the array 1 200 500 2000 sort the array therefore we have now 2000 500 200 1 1st array will have largest element A= {2000} and B={500} sumA=2000 sumB=500 now abs((2000+200)-500)abs((2000)-(500+200)) so we ll put 200 in array B. now since B has n/2 elements rest of the element goes to array which is 1. so the ans is A={2000,1} b={500,200} On 15 May 2010 19:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: so what will ur algo give for array 1,200,500,2000 On 5/15/10, divya jain sweetdivya@gmail.com wrote: my approach: 1. sort the array 2. take a variable diff. intitialize it to 0. 3. take the 1st element from array nd place it in array A and 2nd element in array B. stoe in diff sum(A)-sum(B). 4. now place the next element in array A or B according to the condition if if sum(A+element)-sum(B) sum(a)-sum(B+element). store the element in B otherwise in A. also while storing the element in ny array maintain the count of element in that aaray. if any time the count reaches n/2 where n is the no. of elements in the given aaray. then store rest element in the other array. 5. repeat step 5 until both array A n B get n/2 elements.. hope my approach is clear and correct. comments are welcomed. On 15 May 2010 08:47, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Choosing a greedy strategy for this would be difficult. For a simple dp you can maintain A[i,total,present] using a recurrence i is the present index of array total is the number of elements reqd in first partition. present is the no of elements already there in first partition. the array stores difference between sums. GET the minimum of all these and backtrack. On 5/15/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your diff would be 95 but the best result is 91 i think we can solve this problem by dynamic programming but not a simple one! since the size of the two subsets must be equal. so it's DP solution has at least 3 dimensions: tow dimensions representing the number of elements in each subset and another for the difference between their sums On Fri, May 14, 2010 at 10:11 PM, W Karas wka...@yahoo.com wrote: On May 14, 4:51 am, divya sweetdivya@gmail.com wrote: Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements void part(const int a[], int n_a, int g1[], int g2[]) { int i, j, k; /* diff = sum(g1) - sum(g2) */ int diff; sort(a, n_a); diff = 0; for (i = 0, j = 1, k = 0; j n_a; ++k, i += 2, j += 2) { if ((a[i] a[j]) == (diff 0)) { g1[k] = a[j]; g2[k] = a[i]; } else { g1[k] = a[i]; g2[k] = a[j]; } diff += g1[k] - g2[k]; } } -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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 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
Re: [algogeeks] partion of array
I was really not able to digest the greedy thing Great example!! On 5/17/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @divya : it's a greedy approach and again it's WRONG! your answer for {110,100,90,70,60,10 } would be: A = { 110, 70, 60 } B = { 100, 90 , 10 } the difference is 40 the correct ans: A = { 110, 100 , 10 } B = { 90 , 70 , 60 } the difference is 0 i don't believe a greedy algorithm would work for this problem! On Mon, May 17, 2010 at 5:06 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @divya : descending order sorting works. BRILLIANT !! On 5/17/10, divya jain sweetdivya@gmail.com wrote: my algo on the array 1 200 500 2000 sort the array therefore we have now 2000 500 200 1 1st array will have largest element A= {2000} and B={500} sumA=2000 sumB=500 now abs((2000+200)-500)abs((2000)-(500+200)) so we ll put 200 in array B. now since B has n/2 elements rest of the element goes to array which is 1. so the ans is A={2000,1} b={500,200} On 15 May 2010 19:10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: so what will ur algo give for array 1,200,500,2000 On 5/15/10, divya jain sweetdivya@gmail.com wrote: my approach: 1. sort the array 2. take a variable diff. intitialize it to 0. 3. take the 1st element from array nd place it in array A and 2nd element in array B. stoe in diff sum(A)-sum(B). 4. now place the next element in array A or B according to the condition if if sum(A+element)-sum(B) sum(a)-sum(B+element). store the element in B otherwise in A. also while storing the element in ny array maintain the count of element in that aaray. if any time the count reaches n/2 where n is the no. of elements in the given aaray. then store rest element in the other array. 5. repeat step 5 until both array A n B get n/2 elements.. hope my approach is clear and correct. comments are welcomed. On 15 May 2010 08:47, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Choosing a greedy strategy for this would be difficult. For a simple dp you can maintain A[i,total,present] using a recurrence i is the present index of array total is the number of elements reqd in first partition. present is the no of elements already there in first partition. the array stores difference between sums. GET the minimum of all these and backtrack. On 5/15/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your diff would be 95 but the best result is 91 i think we can solve this problem by dynamic programming but not a simple one! since the size of the two subsets must be equal. so it's DP solution has at least 3 dimensions: tow dimensions representing the number of elements in each subset and another for the difference between their sums On Fri, May 14, 2010 at 10:11 PM, W Karas wka...@yahoo.com wrote: On May 14, 4:51 am, divya sweetdivya@gmail.com wrote: Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements void part(const int a[], int n_a, int g1[], int g2[]) { int i, j, k; /* diff = sum(g1) - sum(g2) */ int diff; sort(a, n_a); diff = 0; for (i = 0, j = 1, k = 0; j n_a; ++k, i += 2, j += 2) { if ((a[i] a[j]) == (diff 0)) { g1[k] = a[j]; g2[k] = a[i]; } else { g1[k] = a[i]; g2[k] = a[j]; } diff += g1[k] - g2[k]; } } -- 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 algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@googlegroups.com algogeeks%25252bunsubscr...@googlegroups.comalgogeeks%2525252bunsubscr...@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
Re: [algogeeks] string question
@Navin: and that works ! :) @all : i am sure no heuristic/greedy strategy can be applied. @divya : did you check your array partitioning algorithm with my example ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] tree question
Either the root will be included or it will not be. If it's not, then it's equivalent to solving the problem on the subtrees. So let's consider the case when root node is included Now we keep track of A[node1,node2,reqdWeight] reqdWeight is the sum of wt reqd from paths starting from node1 and node2 Again, let's only see the case when we don't get a path of reqdWeight from one of the nodes alone. Then both node1 and node2 will be included. And i guess it's now a simple DP. @jalaj : i did not read your code but the topview shows that if it works, it is exponential. The algorithm I am suggesting will be polynomial. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] question
@anurag : won't work -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] regarding DSW algortihm
Read it up : http://www.eecs.umich.edu/~qstout/pap/CACM86.pdf -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: median of a bst
@Nikhil : For that size of subtrees at all nodes needs to be maintained. And in that case this is a trivial problem. @Sathaiah : See my solution :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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: partion of array
so what will ur algo give for array 1,200,500,2000 On 5/15/10, divya jain sweetdivya@gmail.com wrote: my approach: 1. sort the array 2. take a variable diff. intitialize it to 0. 3. take the 1st element from array nd place it in array A and 2nd element in array B. stoe in diff sum(A)-sum(B). 4. now place the next element in array A or B according to the condition if if sum(A+element)-sum(B) sum(a)-sum(B+element). store the element in B otherwise in A. also while storing the element in ny array maintain the count of element in that aaray. if any time the count reaches n/2 where n is the no. of elements in the given aaray. then store rest element in the other array. 5. repeat step 5 until both array A n B get n/2 elements.. hope my approach is clear and correct. comments are welcomed. On 15 May 2010 08:47, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Choosing a greedy strategy for this would be difficult. For a simple dp you can maintain A[i,total,present] using a recurrence i is the present index of array total is the number of elements reqd in first partition. present is the no of elements already there in first partition. the array stores difference between sums. GET the minimum of all these and backtrack. On 5/15/10, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: @karas: your solution is greedy and its wrong e.g. for {1,2,3,4,5,100} your diff would be 95 but the best result is 91 i think we can solve this problem by dynamic programming but not a simple one! since the size of the two subsets must be equal. so it's DP solution has at least 3 dimensions: tow dimensions representing the number of elements in each subset and another for the difference between their sums On Fri, May 14, 2010 at 10:11 PM, W Karas wka...@yahoo.com wrote: On May 14, 4:51 am, divya sweetdivya@gmail.com wrote: Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements void part(const int a[], int n_a, int g1[], int g2[]) { int i, j, k; /* diff = sum(g1) - sum(g2) */ int diff; sort(a, n_a); diff = 0; for (i = 0, j = 1, k = 0; j n_a; ++k, i += 2, j += 2) { if ((a[i] a[j]) == (diff 0)) { g1[k] = a[j]; g2[k] = a[i]; } else { g1[k] = a[i]; g2[k] = a[j]; } diff += g1[k] - g2[k]; } } -- 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. -- 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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] k the smallest in BST without using static variable
there is something called morris inorder traversal. credits to donald knuth On 5/15/10, kaushik sur kaushik@gmail.com wrote: Hi Friends I have encountered the question in sites - Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can't pass the value k to any function also. I have tried my hands using explicit stack for inorder and keeping a non-static count variable. I welcome any better solution, time and space efficient. Best Regards Kaushik Sur -- 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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] median of a bst
If you maintain the size of the subtree rooted at the nodes, then it will become easier. I guess you can see how. Else, 1) Use any algo to count the number of nodes in the BST.Let it be n. 2) Use morris inorder(no recursion/no stacks-all constraint met ) to traverse the tree. For each node visited increment the counter. a) If n is even then return avg(n/2,n/2+1)(counter == n/2) b) If n is odd return when counter == (n+1)/2(1-based indexing) You might want to read this up. : http://www.scss.tcd.ie/disciplines/software_systems/fmg/fmg_web/IFMSIG/winter2000/HughGibbonsSlides.pdf -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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
You have to take some i nodes from array A and the rest k-i-1 from array B. You do not know i. = Problem is to Find i So we do a binary search for that. The value i is acceptable if the (k-i) th element in B is greater than ith element in A. So, i guess you would have got it now. -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] partion of array
A simple DP should work. Should it not? -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 4:15 PM, Sathaiah Dontula don.sat...@gmail.comwrote: Any assumption like, it has even number of elements and two distinct sets ? Thanks, Sathaiah On Fri, May 14, 2010 at 2:21 PM, divya sweetdivya@gmail.com wrote: Algorithm to partition set of numbers into two s.t. diff bw their sum is min and they hav equal num of elements -- 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 at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] 2nd shortest path in a graph
I think... it will work :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Fri, May 14, 2010 at 2:20 PM, divya sweetdivya@gmail.com wrote: Given a graph's shortest path algorithm, how can you make use of it to find the second shortest path? my solution well just a thought... is it something like.assume this is the smallest distance path start-node1-node2-node3-node4-destination (now the graph will be represented by a matrix of order 2) in order start breaking any of the link(break only one) eg:- break the link start-node(i.e. delete the entry in the matrix which connects start and node1) and then again use dijikras to find a distance(store it) now again link the start node with the node1 and break the node1- node2 and find a distance... after getting all the distances.find the min...that will be the second min of all... hope i am going on the right tracktell me if i am wrong...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.