[algogeeks] Re: a puzzle
May not be only rotation, maybe rotation, flipping etc, just a orthogonal/orthonormal transformation matrix On Sat, May 8, 2010 at 9:19 AM, Afroz Mohiuddin afrozena...@gmail.comwrote: I have a set of n-dimensional vectors, lets say, v1, v2, v3, ... vm vi, vj means the dot product of vi and vj. It is known that vi, vj = 0 forall i, j i.e. the angle between any two of them is less equal to 90 degrees, which basically means that all of them can be occupied in a single quadrant in the n-dimensional space. Because in any quadrant, the maximum angle between two vectors both lying inside the quadrant is 90 degrees. Can you come up with a orthonormal transformation U, such that Uvi = 0 ... i.e. an orthonormal transformation (rotation basically, i want the rotation matrix U), such that all those vectors come in the positive quadrant. There will always exist such a matrix U because all the angles are less than 90degrees, can you get a way to find one of them. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] a puzzle
I have a set of n-dimensional vectors, lets say, v1, v2, v3, ... vm vi, vj means the dot product of vi and vj. It is known that vi, vj = 0 forall i, j i.e. the angle between any two of them is less equal to 90 degrees, which basically means that all of them can be occupied in a single quadrant in the n-dimensional space. Because in any quadrant, the maximum angle between two vectors both lying inside the quadrant is 90 degrees. Can you come up with a orthonormal transformation U, such that Uvi = 0 ... i.e. an orthonormal transformation (rotation basically, i want the rotation matrix U), such that all those vectors come in the positive quadrant. There will always exist such a matrix U because all the angles are less than 90degrees, can you get a way to find one of them. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin Final Year Masters Student Dept Computer Science and Engineering Indian Institute of Technology Kanpur Kanpur - 208016 INDIA Address: F-112 Hall 9 Telephone: [91]9838773891 Email: afrozena...@gmail.com a...@iitk.ac.in a...@cse.iitk.ac.in -- 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
Well if you want a sum of exactly 0 (or any constant) , there is an O(N^2) way Take your array, and hash it, note that it is always possible to hash a static set of keys so that the search/find in it is worst case O(1). This takes O(N) space, and time. Then over all the tuples of numbers in the original array (a,b) check if 0 - (a+b) is there in the hash set, time complexity O(N*N). For closest to 0 I guess the above solution is good. On Mon, May 3, 2010 at 2:18 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: given an array(unsorted) may contain negative numbers too find the index of three numbers whose sum is closest to zero in O(N2 log N) time and O(N) space. P.S -3 is more close to zero then -6 (number line ...) -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- 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. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin Final Year Masters Student Dept Computer Science and Engineering Indian Institute of Technology Kanpur Kanpur - 208016 INDIA -- 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] value of n
An easy way to do would be to plot both functions in matlab, n and 8log(n) ... just see when y = x is below y = 8log(x) happens between 3= n = 25 if log is to natural base if it was log base 2 ... 3= n = 43 On Sat, May 1, 2010 at 10:43 AM, Amit Agarwal lifea...@gmail.com wrote: I could not get you properly. This is an equation comes from the problem statement where I need to find out cut-off value of n between insertion and merge sort. I think equation is part of basic mathematics but I don't remember how do I solve it. -Regards Amit Agarwal Contact: 09765348182 www.amitagrwal.com On Sat, May 1, 2010 at 9:13 AM, abhijith reddy abhijith200...@gmail.comwrote: binary search on n On Fri, Apr 30, 2010 at 10:15 PM, Amit Agarwal lifea...@gmail.comwrote: how do I compute n from this equation. n 8lg(n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin Final Year Masters Student Dept Computer Science and Engineering Indian Institute of Technology Kanpur Kanpur - 208016 INDIA Address: F-112 Hall 9 Telephone: [91]9838773891 Email: afrozena...@gmail.com a...@iitk.ac.in a...@cse.iitk.ac.in -- 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] Add 2 long integers with digits represented by linked lists
The solution is essentially the same as Anurag's; Only that it would be simple to reverse both the lists So now the lists look like Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 head_num1 Link-1-Link-2-Link-3-Link-4 -head_num2 Now basically loop, and add the keys, remembering to take the carry ... and if there is carry in the last stage, then make an extra node. Regards On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia abhati...@gmail.com wrote: Let us take an example - Num 1 = 123456 Num 2= 1234 Link-1-Link-2-Link-3-Link-4-Link5-Link6 Link-1-Link-2-Link-3-Link-4 Add nodes into linkedlist 1 till either one of the list is not null. Make sure you process the carry in each iteration. --AB On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase harishp...@gmail.com wrote: conditions: NO extra memory (@ stack or Heap) at all. No recursion. Any body has got any hint about how to get this done ? -- 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. -- We are here on earth to do good for others. What the others are here for, I don't know. Afroz Mohiuddin Final Year Masters Student Dept Computer Science and Engineering Indian Institute of Technology Kanpur Kanpur - 208016 INDIA -- 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.