Re: [algogeeks] matrix Multiplication
I need to multiply an array A by it self. Is there an algorithm that does array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)? On Sun, Jan 20, 2013 at 12:44 AM, Dave dave_and_da...@juno.com wrote: @Guneesh: I think you mean to say that the complexity of both the iterative and recursive algorithms is O(n^3 log k), using the notation of the original poster (A is n-by-n, and it is to be raised to the power k). If what you really need is a way to calculate A^k * x, for some vector x, it may be cheaper to use matrix-vector multiplication k times; this will be O(n^2 * k). Dave On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote: both recursive and iterative codes are O(nlogn) algos.. but memory will be more in recursion.. so we will prefer iteration -- --
Re: [algogeeks] MS Question
not possible unless u use augmented bst..which itself takes o(n) to built --
Re: [algogeeks] Modified String Searching
This is a test This is a programming test This is a programming test in any language 1 1 1 122 2 2 233 3 3 3 3 33(count of this) 0 0 1 111 2 2 222 3 3 3 3 33 (count of a) 0 0 0 111 1 1 222 2 2 3 3 33 (count of test) 0 0 0 000 0 1 111 1 2 2 2 22 (count of programming) 0 1 2 345 6 7 8910 11 12 13 14 15 16 (index) now we need to select 2 indexes such tha the diff array i greater or equal to [1,1,1,1] (0,7) (1,7) (6,9) etc are some sol out of which (6,9) is min --
[algogeeks] Check simple polygon
How to check if polygon is simple based on given list of points ? --
Re: [algogeeks] MS Question
http://stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way On Sun, Jan 20, 2013 at 4:57 PM, Guneesh Paul Singh gunees...@gmail.comwrote: not possible unless u use augmented bst..which itself takes o(n) to built -- --
Re: [algogeeks] MS Question
If for all the nodes in BST we also store the size of subtree, then it is possible to find nth smallest element in O(logN). On Sun, Jan 20, 2013 at 4:57 PM, Guneesh Paul Singh gunees...@gmail.comwrote: not possible unless u use augmented bst..which itself takes o(n) to built -- -- Praveen Sonare +91-7838908235 --
Re: [algogeeks] matrix Multiplication
@Koup: No, I meant O(n^3 log k). Sorry. Dave On Sunday, January 20, 2013 3:09:00 AM UTC-6, Koup wrote: I need to multiply an array A by it self. Is there an algorithm that does array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)? On Sun, Jan 20, 2013 at 12:44 AM, Dave dave_an...@juno.com javascript:wrote: @Guneesh: I think you mean to say that the complexity of both the iterative and recursive algorithms is O(n^3 log k), using the notation of the original poster (A is n-by-n, and it is to be raised to the power k). If what you really need is a way to calculate A^k * x, for some vector x, it may be cheaper to use matrix-vector multiplication k times; this will be O(n^2 * k). Dave On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote: both recursive and iterative codes are O(nlogn) algos.. but memory will be more in recursion.. so we will prefer iteration -- --
[algogeeks] Re: Check simple polygon
@Shady: See http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm. Dave On Sunday, January 20, 2013 10:02:19 AM UTC-6, shady wrote: How to check if polygon is simple based on given list of points ? --
Re: [algogeeks] Modified String Searching
to make it O(n logn) 1.Chose one index O(n) 2.For this index do a bsearch on remaining array to find the postion bsearch can be done as the array is an increasing function(it donotes no of occurrence of each word,so=previous index value) bsearch will be done like this 1.make a new temp array that is sum of the array to be found([1,1,1,1])and the chosen index array 2.now take the middle element array if all values of array are eual to temp array u have ans; if any one value is lesser go to right half else goto left half finally while returnin(after while loop) do chck greater than condition again --
