Re: [algogeeks] How many games you will conduct to decide a winner for N players. Visualize in terms of a Data Structure.
Ya tournament tree is fine, you can even check it on http://www.geeksforgeeks.org/archives/11556 To decide a winner among N people, ( n-1 ) people should loose. So N-1 games will decide. On Mon, Apr 9, 2012 at 12:45 AM, SAMM somnath.nit...@gmail.com wrote: This can be done using Tournament Tree ... PLzz refer wiki or http://www.geeksforgeeks.org/archives/11556 ... This will surely help .. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Modified binary search
how can there be multiple spikes and valleys?? say 1 2 3 4 5 6 7 if you rotate it once with rotation index 3 4 5 6 7 1 2 3 then again with index 2 6 7 1 2 3 4 5 So the multiple times rotation just means that the index of rotation is more then 1. On Fri, Apr 6, 2012 at 7:02 AM, Ashish Goel ashg...@gmail.com wrote: code needed… not ble to visualize what to do if there are too many spikes and valleys in the multiple times rotated array, is that possible?? On Sep 28, 2011, at 1:36 AM, Gene wrote: Indeed you must be given that all the array elements are unique or at least that there are no more than floor(n/2) repeats). Otherwise this is impossible. The simplest way to think about it is first to search for i such that a[i] a[i+1]. At that point you know there are two sorted ranges a[0]..a[i] and a[i+1] to a[n-1], so you can use regular binary search on each of these pieces. So how to find i? This is itself a binary search. At each stage, check whether a[0] a[mid] and a[mid] a[n-1]. The half that passes this test contains i. So throw away the other. On Sep 27, 10:01 am, Decipher ankurseth...@gmail.com wrote: A given sorted array is rotated unknown number of times , write a C/C++ code to find an element in the sorted array in O(log n) time . I know the solution to this problem is through binary search , but don't know the exact solution . Please help !! -- 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.
[algogeeks] how to solve
how should i approach this problem https://www.spoj.pl/problems/DCEPC206/ can it be solved in O(n)..? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: GPU doubt
Hey Arun, IIya, the GPUs are faster because of 1. designed for graphics processing, which involves a lot of matrix processing capabilities , simple example transformation of matrices in to various view (projection, model and viewport , some times needed even in real time) so these computation are done in parallel 2. all or most of processing are done at much precise rate and until one does not specify, all are 'double computations' which is quite costly even in modern CPU - ALU 3. not only computations, a lot of other parallel architectural advantage gives normal algorithms ( e.g. cache) better speedup than CPU hope it clarifies. So if you are planning to start on GPU, start thinking in multi-threaded copying data generally involves separate processing of DMA, I worked with USB and PCI 66MHz connection of CPU/GPU , and does not seem to be slow. even Fujitsu CoralPA was ok which has very slow dma and a PCI 33 connection. On Apr 8, 4:04 am, Ilya Albrekht ilya.albre...@gmail.com wrote: Hey Phoenix, It is true that current GPU have way better floating point throughput than any general purpose processor. But when you want to run your algo. on the GPU there are always an overhead of copying data between CPU GPU, drivers and other system calls and you can gain performance even with those overhead if you have a lot of calculations (more calculations, less overhead %). And I assume in general you have to do at least O(n^3) calculations to gain any perf. Out of my experience, the same thigh with the SSE vectorization - it doesn't make sense to vectorize the loop if it is less than ~25-27 iterations, because the overhead of preparing data and aligning buffers will be too high. On Saturday, 7 April 2012 08:54:20 UTC-7, phoenix wrote: @SAMM: what about general mathematical computations such as matrix multiplication which is O(n^3) as such? How do you relate your explanation to such math computations or any algorithm of atleast O(n^3)? On Sat, Apr 7, 2012 at 3:22 AM, SAMM somnath.nit...@gmail.com wrote: This is becoz the GPU is multithreaded . In graphics there are three main steps , Application based work where vertex Processing , read the data , pixel processing are done . Secondly come the Culling which which determimes which portion will be shown given the Line of sight . This also checks for any intersection with other objects . For instance a man is present behind the building ,so he should not be visible to us in Graphics or some portion of this body will be shown , This intersection is called redering . The third step if draw . to finally draw the model . These three process are done multithreaded parallerly given 3x Processing speed . You can refer this link below :- http://www.panda3d.org/manual/index.php/Multithreaded_Render_Pipeline -- 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. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Intuit interview question
Hi, Any idea, what is the interview process of Intuit Inc.? I mean what do they concentrate on? Thanks, Vaibhav -- 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: GPU doubt
Sorry for lot of typos On Mon, Apr 9, 2012 at 1:53 PM, Varun Nagpal varun.nagp...@gmail.comwrote: GP programming on GPU is useful for those algorithms which are computationally intensive, can be paralleled with least overheads, granularity of per thread computations is not big, less+similar control flow per thread and at the same time do regular data access(for example array based data is regular while pointer based data is irregular). Massive multi-threading us used by GPU's to hide memory latency CPUs are essentially meant to run control-intensive(lot of conditional code: branch predictors help here) , irregular memory access (Memory hierarchy Register file, L1, L2 L3 caches helps here) and coarse grained multi-threaded applications(Multi-threaded processor architectures and HyperThreading helps here). Memory hierarchy + hardware multi-threading is used for hiding memory latency For a given algorithm, thousands of threads run on a GPU compared to handful (max some hundreds) that would run on a CPU. There is no general rule to say that an algorithm of O(n^3) complexity will run faster on CPU or GPU. My answer would be it depends. It depends upon lot of other things about the algorithm(data structure layout, floating point calculations etc.) and the available hardware options and its architecture. One of the criteria of how to choose would be see the calculations/per memory access. The higher is this value, the better it would be suitable for GPU than CPU and vice versa I suggest you to this question on a computer architecture forum. Thanks Varun On Mon, Apr 9, 2012 at 1:21 PM, vikas vikas.rastogi2...@gmail.com wrote: Hey Arun, IIya, the GPUs are faster because of 1. designed for graphics processing, which involves a lot of matrix processing capabilities , simple example transformation of matrices in to various view (projection, model and viewport , some times needed even in real time) so these computation are done in parallel 2. all or most of processing are done at much precise rate and until one does not specify, all are 'double computations' which is quite costly even in modern CPU - ALU 3. not only computations, a lot of other parallel architectural advantage gives normal algorithms ( e.g. cache) better speedup than CPU hope it clarifies. So if you are planning to start on GPU, start thinking in multi-threaded copying data generally involves separate processing of DMA, I worked with USB and PCI 66MHz connection of CPU/GPU , and does not seem to be slow. even Fujitsu CoralPA was ok which has very slow dma and a PCI 33 connection. On Apr 8, 4:04 am, Ilya Albrekht ilya.albre...@gmail.com wrote: Hey Phoenix, It is true that current GPU have way better floating point throughput than any general purpose processor. But when you want to run your algo. on the GPU there are always an overhead of copying data between CPU GPU, drivers and other system calls and you can gain performance even with those overhead if you have a lot of calculations (more calculations, less overhead %). And I assume in general you have to do at least O(n^3) calculations to gain any perf. Out of my experience, the same thigh with the SSE vectorization - it doesn't make sense to vectorize the loop if it is less than ~25-27 iterations, because the overhead of preparing data and aligning buffers will be too high. On Saturday, 7 April 2012 08:54:20 UTC-7, phoenix wrote: @SAMM: what about general mathematical computations such as matrix multiplication which is O(n^3) as such? How do you relate your explanation to such math computations or any algorithm of atleast O(n^3)? On Sat, Apr 7, 2012 at 3:22 AM, SAMM somnath.nit...@gmail.com wrote: This is becoz the GPU is multithreaded . In graphics there are three main steps , Application based work where vertex Processing , read the data , pixel processing are done . Secondly come the Culling which which determimes which portion will be shown given the Line of sight . This also checks for any intersection with other objects . For instance a man is present behind the building ,so he should not be visible to us in Graphics or some portion of this body will be shown , This intersection is called redering . The third step if draw . to finally draw the model . These three process are done multithreaded parallerly given 3x Processing speed . You can refer this link below :- http://www.panda3d.org/manual/index.php/Multithreaded_Render_Pipeline -- 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. -- People often
Re: [algogeeks] Path along the diameter of the binary tree
finding end nodes of the diameter can be found in the below link :- http://groups.google.com/group/algogeeks/browse_thread/thread/8b6e326b75904d9a/92839f502d671599?hl=enlnk=gstq=Two+most+distant+element+in+tree#92839f502d671599 after finding 2 nodes we just need to find path between those 2 nodes , which can be found in below link http://groups.google.com/group/algogeeks/browse_thread/thread/9bbdd33a6b1e1c5f/fab5d6ad3840b74d?hl=enlnk=gstq=Find+the+path+in+two+nodes+of+a+binary+search+tree#fab5d6ad3840b74d On Fri, Apr 6, 2012 at 10:58 PM, Doom duman...@gmail.com wrote: We have seen the question of computing the diameter of binary tree. Any ideas to compute the path of nodes along that diameter? No parent pointer exists. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/CMNxVKMrfasJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Which data structure to use in searching a list for information about - -
dual key hashmap actor,film
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Apr 8, 2012 at 2:37 PM, bharat b bagana.bharatku...@gmail.comwrote:
Maintain an vector of structure Film_actors for List of actors
Maintain an vector of structure Actor_films for List of Films
I'll explain this with the help of an example .
Films:
1.Hai
2.Bye
Actors:
A,B,C,D acted in Film Hai.
A,D,F,G acted in Film Bye.
struct Film_actors {
String Film_name;
int * list_of_actors; // indices in other datastructure ..
int number_of_actors;
};
create hashtable on actor'sNames and filmNames..
List_of_actors is as follows
add new film in this list and check whether the actor 'A' is already in
hash table., if not add 'A' to hash tableA,index in List_of_Films data
structure
when ever we add a new film to List_of_actors[], we add that FilmName to
hash tablefilmname,index in List_of_actors datastructure.
List_of_actors[0] = {Hai,{0,1,2,3},4};
List_of_actors[1] = {Bye,{0,3,4,5},4};
struct Actor_films {
String Actor_name;
int * list_of_films; // indices(values in hash table on films) in other
data structure
int number_of_films;
};
With these data structures, we can do all operations in O(1) time ..
if any mistakes, let me know ...
On Fri, Apr 6, 2012 at 10:50 PM, Rose itro...@gmail.com wrote:
Thanks all of you. I'm new to algorithms and data structure and I'm new
in this forum.
I have an assignment but not sure yet:
A. Describe a data structure which can effectively answer the following
questions:
1. A list of actors (f) : Print a list of actors who took part in film*f
*.
2. A list of films -(s): Print a list with all the films that actor s has
been in.
3. Participation (s,f): Return true if the actor s took part in film f,
and false if not.
Explain the data structure and how the questioning is done.
Analyse the worst case running time for the above queries- in asymptotic
notation, as tight as possible
In the analysis use e.g. F=number of films; S =number of actors; Fs=
number of films actor s took part in;
and Sf =number of actors who took part in film f.
Thanks a lot for your help
--
Med Venlig Hilsen/Kind regards
Rose
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] how to solve
I dont know if it can be solved in O(n). But O(nlogn) can be done using BIT. Refer topcoder tutorial for Binary indexed trees. On Mon, Apr 9, 2012 at 10:56 AM, tarun chabarwal admin20...@gmail.comwrote: how should i approach this problem https://www.spoj.pl/problems/DCEPC206/ can it be solved in O(n)..? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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.
