[algogeeks] Re: function overloading query
Hi This type of function overloading works in c . Execute following code and it will call function fun as per the function parameter code snip-in - #includestdio.h void fun(const char *p) { printf(funsfsdafsf1\n); } void fun(char *P) { printf(fun2\n); } void main() { char str[] = funcheck; const char str1[] = constcheck; fun(str); fun(str1); } - output fun2 funsfsdafsf1 Mayur On Nov 21, 6:30 pm, Anil Arya anilarya...@gmail.com wrote: dudecompile using g++ On 11/21/11, atul anand atul.87fri...@gmail.com wrote: this is what i am getting after executing code meintion in the above link. (using gcc compiler ) temp.c:12: error: conflicting types for 'fun' temp.c:7: error: previous definition of 'fun' was here On Mon, Nov 21, 2011 at 3:09 PM, UTKARSH SRIVASTAV usrivastav...@gmail.comwrote: http://www.ideone.com/JQFNh CHECK THE OUTPUT THERE IS NO AMBIGUITY BUT PLEASE EXPLAIN THE RESULTS On Sun, Nov 20, 2011 at 11:00 PM, Akash Coder akash.coder.g...@gmail.comwrote: it wont work even this wont function(char a[]) function (char *) coz the two forms are interchangeable On Sun, Nov 20, 2011 at 10:12 PM, saurabh singh saurab...@gmail.comwrote: wont work..Thre is no way compilers gonna guess which function to call.The const qualifier only guarantees that the value at the address wont be altered inside the function.That has nothing to do with calling, On Sun, Nov 20, 2011 at 9:50 PM, rahul vatsa vatsa.ra...@gmail.comwrote: yes, it will work. On Sun, Nov 20, 2011 at 9:12 PM, Akash Coder akash.coder.g...@gmail.com wrote: no it wont work ... const is not a datatype. its a qualifier On Sun, Nov 20, 2011 at 7:49 PM, rahul sharma rahul23111...@gmail.com wrote: void fun(char *) void fun(const char *) is this overloading works or these are same type of arguments?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *UTKARSH SRIVASTAV CSE-3 B-Tech 3rd Year @MNNIT ALLAHABAD* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Anil Arya, Computer Science * *Motilal Nehru National Institute of Technology,Allahabad . * -- 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
[algogeeks] Re: Problems 4-6 of CLRS: VLSI chip testing
I think its a problem similar to finding out one good chip and one bad chip in the given set. If you get a good chip then you can find out the bad chip. I think its a problem similar to finding a soilder which has a infected blood or so... there is some problem based I dont remember. I this case you should devide the chips in n/2 set and try to figure out one good chip. something like devide and quanqer algo used in merge sort. Thank You, Mayur On Nov 23, 11:36 am, LostL [EMAIL PROTECTED] wrote: Here is the description of this problem: Professor Diogenes has n supposedly identical VLSI[1] chips that in principle are capable of testing each other. The professor's test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows: Chip A says Chip B says Conclusion B is good A is good both are good, or both are bad B is good A is bad at least one is bad B is bad A is good at least one is bad B is bad A is bad at least one is bad a. Show that if more than n/2 chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor. b. Consider the problem of finding a single good chip from among n chips, assuming that more than n/2 of the chips are good. Show that ⌊n/2⌋ pairwise tests are sufficient to reduce the problem to one of nearly half the size. c. Show that the good chips can be identified with Θ(n) pairwise tests, assuming that more than n/2 of the chips are good. Give and solve the recurrence that describes the number of tests. -- Solutions/hints will be appreciated. Thanks! --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 答复: [algogeeks] Re: Array of int egers
Hi I got the answer. Correcting the program as we need to add a condition to take care of -ve values Please correct me if I am wrong int i = 0; int nPair while (in) { nPair = X - array[i]; if(nPair = 0) continue; else if(bitmap[nPair] == marked) printf(found the answer!); else bitmap[array[i]] = marked; i++; } Thank You, Mayur On Nov 23, 3:25 pm, MJ [EMAIL PROTECTED] wrote: Hi James, As per your solution the variable pair can go negative and if Array[i] X, and in that case you can not use bitmap[pair] which will give an exception as we can not access the array elements using -ve value. SO how will you take care of -ve values of variable pair... pair = X - array[i]; //this can go negative if( bitmap[pair] == marked )// if pair is - ve value this operation is not allowed found the answer! else mark bitmap[array[i]] Thank You, Mayur On Nov 23, 2:22 pm, MJ [EMAIL PROTECTED] wrote: Hi James, your approach is cool, The bitmap approach works in O(n), but as mention by dave, it take extra memory and initialization. If we dont want to use extra memory, can it be done in O(n)? Thank You MJ On Nov 21, 8:11 pm, Dave [EMAIL PROTECTED] wrote: Okay. This works better. It is O(n), but also requires a large amount of extra memory ( regard 512MB to be large), with a corresponding huge constant overhead to initialize the bitmap. Can you estimate, using reasonable assumptions, the n for which the O(n log n) algorithm using sorting would be faster than this algorithm. I think you will find the breakeven point to be pretty large, perhaps 2^20 or more. So, for n = 10, 100, or 1000, the bitmap as you describe it would be pretty impractical. This raises the interesting question: How do you trade off lower asymptotic order with possible higher cost for smaller values of n. There are some places where this tradeoff is crucial to program performance. For example, in manipulating sparse matrices, a common operation is as follows: for i = 1 to n y[index[i]] = a * x[i] + y[index[i]]; You can write code to be fast for large n, but it is more important to be fast for small n because most of the time n will be small. Dave On Nov 20, 7:30 pm, James Fang [EMAIL PROTECTED] wrote: Oh sorry I've made a mistake in the pseudo code: It should be rectified like this: for i=0 to N pair = X - array[i]; if( bitmap[pair] == marked ) found the answer! else mark bitmap[array[i]] For a 32bit processor , the bitmap takes about 512MB of memory. However, if this operation is in server side and is the bottle neck , the bitmap method can be tried. If the integer in the array have a stricted range, like [-x,y], the bitmap method can be better applied. Best Regards, James Fang -邮件原件- 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表 Dave 发送时间: 2007年11月21日 星期三 2:29 收件人: Algorithm Geeks 主题: [algogeeks] Re: Array of integers Want to try again? Consider the case where array = {2,3} and X = 5. First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so you mark bitmap[3]. Then you have pair = 5 - 3 = 2 and noet that bitmap[2] != marked, so you mark bitmap[2]. Presumably, at this point, since you have exhausted array, you deduce that there is no solution. You might also want to talk about the size of bitmap. Dave On Nov 20, 11:03 am, James Fang [EMAIL PROTECTED] wrote: You can acheive O(n) by using a bitmap. the pseudo code can be described below: for i=0 to N pair = X - array[i]; if( bitmap[pair] == marked ) found the answer! else mark bitmap[pair] the bitmap can be an array in the RAM or external disk, with each bit represents an integar number. Best Regards, James Fang On 11月18日, 上午4时42分, geekko [EMAIL PROTECTED] wrote: Suppose that you have an array of integers. Given a number X are there any two numbers in the array in which their summation is equal to the X? Can you find a solution in O(n)?- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text -- 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more
[algogeeks] Re: 答复: [algogeeks] Re: Array of int egers
Hi James, your approach is cool, The bitmap approach works in O(n), but as mention by dave, it take extra memory and initialization. If we dont want to use extra memory, can it be done in O(n)? Thank You MJ On Nov 21, 8:11 pm, Dave [EMAIL PROTECTED] wrote: Okay. This works better. It is O(n), but also requires a large amount of extra memory ( regard 512MB to be large), with a corresponding huge constant overhead to initialize the bitmap. Can you estimate, using reasonable assumptions, the n for which the O(n log n) algorithm using sorting would be faster than this algorithm. I think you will find the breakeven point to be pretty large, perhaps 2^20 or more. So, for n = 10, 100, or 1000, the bitmap as you describe it would be pretty impractical. This raises the interesting question: How do you trade off lower asymptotic order with possible higher cost for smaller values of n. There are some places where this tradeoff is crucial to program performance. For example, in manipulating sparse matrices, a common operation is as follows: for i = 1 to n y[index[i]] = a * x[i] + y[index[i]]; You can write code to be fast for large n, but it is more important to be fast for small n because most of the time n will be small. Dave On Nov 20, 7:30 pm, James Fang [EMAIL PROTECTED] wrote: Oh sorry I've made a mistake in the pseudo code: It should be rectified like this: for i=0 to N pair = X - array[i]; if( bitmap[pair] == marked ) found the answer! else mark bitmap[array[i]] For a 32bit processor , the bitmap takes about 512MB of memory. However, if this operation is in server side and is the bottle neck , the bitmap method can be tried. If the integer in the array have a stricted range, like [-x,y], the bitmap method can be better applied. Best Regards, James Fang -邮件原件- 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表 Dave 发送时间: 2007年11月21日 星期三 2:29 收件人: Algorithm Geeks 主题: [algogeeks] Re: Array of integers Want to try again? Consider the case where array = {2,3} and X = 5. First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so you mark bitmap[3]. Then you have pair = 5 - 3 = 2 and noet that bitmap[2] != marked, so you mark bitmap[2]. Presumably, at this point, since you have exhausted array, you deduce that there is no solution. You might also want to talk about the size of bitmap. Dave On Nov 20, 11:03 am, James Fang [EMAIL PROTECTED] wrote: You can acheive O(n) by using a bitmap. the pseudo code can be described below: for i=0 to N pair = X - array[i]; if( bitmap[pair] == marked ) found the answer! else mark bitmap[pair] the bitmap can be an array in the RAM or external disk, with each bit represents an integar number. Best Regards, James Fang On 11月18日, 上午4时42分, geekko [EMAIL PROTECTED] wrote: Suppose that you have an array of integers. Given a number X are there any two numbers in the array in which their summation is equal to the X? Can you find a solution in O(n)?- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text -- 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: 答复: [algogeeks] Re: Array of int egers
Hi James, As per your solution the variable pair can go negative and if Array[i] X, and in that case you can not use bitmap[pair] which will give an exception as we can not access the array elements using -ve value. SO how will you take care of -ve values of variable pair... pair = X - array[i]; //this can go negative if( bitmap[pair] == marked )// if pair is - ve value this operation is not allowed found the answer! else mark bitmap[array[i]] Thank You, Mayur On Nov 23, 2:22 pm, MJ [EMAIL PROTECTED] wrote: Hi James, your approach is cool, The bitmap approach works in O(n), but as mention by dave, it take extra memory and initialization. If we dont want to use extra memory, can it be done in O(n)? Thank You MJ On Nov 21, 8:11 pm, Dave [EMAIL PROTECTED] wrote: Okay. This works better. It is O(n), but also requires a large amount of extra memory ( regard 512MB to be large), with a corresponding huge constant overhead to initialize the bitmap. Can you estimate, using reasonable assumptions, the n for which the O(n log n) algorithm using sorting would be faster than this algorithm. I think you will find the breakeven point to be pretty large, perhaps 2^20 or more. So, for n = 10, 100, or 1000, the bitmap as you describe it would be pretty impractical. This raises the interesting question: How do you trade off lower asymptotic order with possible higher cost for smaller values of n. There are some places where this tradeoff is crucial to program performance. For example, in manipulating sparse matrices, a common operation is as follows: for i = 1 to n y[index[i]] = a * x[i] + y[index[i]]; You can write code to be fast for large n, but it is more important to be fast for small n because most of the time n will be small. Dave On Nov 20, 7:30 pm, James Fang [EMAIL PROTECTED] wrote: Oh sorry I've made a mistake in the pseudo code: It should be rectified like this: for i=0 to N pair = X - array[i]; if( bitmap[pair] == marked ) found the answer! else mark bitmap[array[i]] For a 32bit processor , the bitmap takes about 512MB of memory. However, if this operation is in server side and is the bottle neck , the bitmap method can be tried. If the integer in the array have a stricted range, like [-x,y], the bitmap method can be better applied. Best Regards, James Fang -邮件原件- 发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表 Dave 发送时间: 2007年11月21日 星期三 2:29 收件人: Algorithm Geeks 主题: [algogeeks] Re: Array of integers Want to try again? Consider the case where array = {2,3} and X = 5. First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so you mark bitmap[3]. Then you have pair = 5 - 3 = 2 and noet that bitmap[2] != marked, so you mark bitmap[2]. Presumably, at this point, since you have exhausted array, you deduce that there is no solution. You might also want to talk about the size of bitmap. Dave On Nov 20, 11:03 am, James Fang [EMAIL PROTECTED] wrote: You can acheive O(n) by using a bitmap. the pseudo code can be described below: for i=0 to N pair = X - array[i]; if( bitmap[pair] == marked ) found the answer! else mark bitmap[pair] the bitmap can be an array in the RAM or external disk, with each bit represents an integar number. Best Regards, James Fang On 11月18日, 上午4时42分, geekko [EMAIL PROTECTED] wrote: Suppose that you have an array of integers. Given a number X are there any two numbers in the array in which their summation is equal to the X? Can you find a solution in O(n)?- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text -- Hide quoted text - - Show quoted text -- 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: NxN matrix
HI Chandra, As per the problem statement Given an array of 0's and 1's whenever you encounter an 0 make corresponding column and row elements 0. Does it mean make all the rows and column zero or only last row and column elemnt zero?? could you reframe the problem statement with more details or an example. Thank YOu, Mayur On Nov 23, 1:20 pm, chandra kumar [EMAIL PROTECTED] wrote: I have some questions in case 2 questions inlined.. Thanks and regards, K.V.Chandra kumar. On 22/11/2007, Dave [EMAIL PROTECTED] wrote: Case 1 Start: 0 1 1 1 1 1 1 1 1 After first scan: 0 1 0 1 1 1 0 1 1 After second scan: 0 1 0 0 1 1 0 1 1 After third scan: 0 0 0 0 1 1 0 1 1 Case 2 Start: 1 1 0 1 1 1 0 1 1 After first scan: 0 1 0 how did we get 0 in the first row first column, we should only alter the last row and column, right? 1 1 1 0 1 0 After second scan: 0 0 0how did we get these zero, only columns are to be changed, right? 0 1 1 0 0 0 After third scan: 0 0 0 0 1 0how did we get this as, ast element is ignored, right? 0 0 0 Hope this helps. Dave On Nov 22, 9:34 am, chandra kumar [EMAIL PROTECTED] wrote: Hi Dave, Can you explain your algo for these 2 cases... 0 1 11 1 0 1 1 11 1 1 1 1 10 1 1 Please explain me in steps cause we tried the same problem and can't get it done for without using extra space. ( we used 1 extra space, if the array can contain only 0 or 1 and no other number, otherwise we store some other number indicating a yet to become zero and proceed, in the later case we need no extra space ) Thanks and Regards, K.V.Chandra Kumar On 15/11/2007, Dave [EMAIL PROTECTED] wrote: Scan the array. If the i,j element is zero, set the last element of row i and the last element of column j to zero. Then, scan the last row, ignoring the last element, and zero every column that ends with a zero. Similarly, scan the last column, ignoring the last element, and zero every row that ends with a zero. This touches every element at most 3 times; i.e., if the array has m rows and n columns, the algorithm is O(1) in space and O(m*n) in time. Dave On Nov 14, 1:27 pm, geekko [EMAIL PROTECTED] wrote: Given an array of 0's and 1's whenever you encounter an 0 make corresponding column and row elements 0. How could you do that efficiently(minimum time and minimum space complexity)? This question is taken from placementsindia.blogspot.com- Hide quoted text - - Show quoted text -- 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 algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Array of integers
you can do it O(n) time if the input array is sorted. Find the min and max value of the array and then decide how many number can be eliminated based if they are greater than X. This problem get complecated if we consider the integers are +ve as well as -Ve intergers in an array. But any way sorting take minimum of O(nlogn), so I dont think it can be done in just O(n). Thank You, Mayur On Nov 19, 3:19 pm, Manish Garg [EMAIL PROTECTED] wrote: can find in O(n) if array is sorted On Nov 18, 2007 9:13 AM, dor [EMAIL PROTECTED] wrote: You can do it in O(n log(n)) (without extra space). If you can afford O(T) extra space (where T is the largest number in the array, in absolute value), you can do it in O(n). On Nov 17, 3:42 pm, geekko [EMAIL PROTECTED] wrote: Suppose that you have an array of integers. Given a number X are there any two numbers in the array in which their summation is equal to the X? Can you find a solution in O(n)? -- With Best Regards... --- Manish --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Discussion on unique-elements-in-an-array
Heap sort has a function heapify which will build the heap. If you just modify this heapify algorithm to eliminate the repeated elemenst it will work in O(nLogn). Also this will work for any number of repeated elements. you can find this algo in hte Design analysis and algorithms by Corment in Chapter 7 : heap Sort. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---