Re: [algogeeks] Casual: MS in US expenses
Prepare to spend atleast 20 Lakhs On Tue, Jun 25, 2013 at 4:49 PM, Jagannath Prasad Das jpdasi...@gmail.comwrote: Folks, I suppose this is not the right blog to query about the aforementioned subject, but i am of opinion that i can get a comprehensive reply to my question. On an average how much money(approx) does it take somebody to do a MS in US(including tution,hostel and miscellaneous) ? I suppose it is easy to get a RA in the university you study and that helps in someway. Regards, Jagannath -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Casual: MS in US expenses
I think you should go to Edulix.com. There you can find details about the expenses for MS in a many different US universities On Tue, Jun 25, 2013 at 4:54 PM, Shachin Sharma shac...@gmail.com wrote: Most of the good/top universities will have many TA and RA positions. Besides this University associated institutes provide RAs. As far as my experience goes almost all of the computer science MS students got RA or TA which covers for 75% waiver in tuition and like 1100 to 1500 $ money, which covered the expenses. But this may not be true for all the universities and you might want to ask specfically for the program you are applying. Regards, Shachin On Tue, Jun 25, 2013 at 4:49 PM, Jagannath Prasad Das jpdasi...@gmail.com wrote: Folks, I suppose this is not the right blog to query about the aforementioned subject, but i am of opinion that i can get a comprehensive reply to my question. On an average how much money(approx) does it take somebody to do a MS in US(including tution,hostel and miscellaneous) ? I suppose it is easy to get a RA in the university you study and that helps in someway. Regards, Jagannath -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
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] thanx to all
cool On Tue, Feb 28, 2012 at 9:22 PM, Ravi Ranjan ravi.cool2...@gmail.comwrote: hey Geeks thanx a lot .. for the valuable information in the discussions i got selected in Yatra.com (R n D profile) thanx a lot for the algorithms explained by to guys THANX A LOT :D:D:D:D -- 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] Re: google os ques on pipelining
Thats right. Clock speed is governed by slowest processing stage + register delay. With clock cycle of (160+5) ns even the faster stages will be forced to run slowly. As a result 1st instruction will take 165*4 ns and rest of following 999 instructions will take 165*999 ns. On Tue, Sep 27, 2011 at 4:03 PM, praneethn praneeth...@gmail.com wrote: clock period=(slowest stage delay)+(Buffer delay). slowest stage delay is 160 ns and Buffer delay is 5ns. Buffer delay will always be there between two stages . clock period=165ns. In the pipelining the time it takes =(k+n-1) * (clock period) k=number of stages and n=number of instructions(data items) hence time it takes=(4+1000-1)*(165)=165.4 microsec On Tue, Sep 27, 2011 at 11:51 AM, Aditya Virmani virmanisadi...@gmail.com wrote: 585 + (160 + 5)for slowest transactions *999 for the rest of the instructions! On Tue, Sep 27, 2011 at 12:49 AM, Gene gene.ress...@gmail.com wrote: You guys have the right idea except that since it's multiple choice you can do this with no math. With 1000 data items and only 4 stages, the bottleneck has to be the slowest pipeline stage with its register delay. So you can answer b in 10 seconds and move on to the next question! On Sep 26, 8:50 pm, Dumanshu duman...@gmail.com wrote: @bharat: for the second part where u multiplied (160+5) with 999, it should be 160*999 because it is max of (150,120,160,140,5). Correct me if i am wrong. On Sep 26, 4:02 pm, bharatkumar bagana bagana.bharatku...@gmail.com wrote: for the first instruction : 150+5+120+5+160+5+140=585 ns for the rest of the instructions , though pipeline max(150,120,160,140)=160 (160+5)*999=164835 ns we assume that there will be no extra stalls existed in our system -585 + 164835 =165420 ns =165.4 us... correct me if I'm wrong . On Sun, Sep 25, 2011 at 9:25 AM, siva viknesh sivavikne...@gmail.comwrote: A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds) respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will approximately be a. 120 us (micro seconds) b. 165 us c. 180 us d. 175 us ...plz give detailed explanation for the ans -- 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. -- **Regards *BharatKumar Bagana* **http://www.google.com/profiles/bagana.bharatkumar http://www.google.com/profiles/bagana.bharatkumar * Mobile +91 8056127652* bagana.bharatku...@gmail.com- 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 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. -- 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] C++ Doubts !!
Dude google C++ Faqs. You will find all your answers. You can also buy some
books
1. C++ Common Knowledge: Essential Intermediate Programming
2. Effective and More effective C++
3. C++ gotchas
On Sat, Sep 24, 2011 at 11:52 AM, Decipher ankurseth...@gmail.com wrote:
Q1) What does the compiler does if I declare a base class VIRTUAL ??
Q2) In the below test code ,
class A : public B, public C
{
};
The order of constructor invocation is :
B
C
A
but if C is virtual base class the it changes to :
C
B
A
Why ??
Q3) Write a macro that swaps any data given to it (Eg: char , int , pointer
of any kind , float )
--
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/-/mj25b-AYRgAJ.
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] Re: Blocked/Unrolled linked list with no duplicates and sorted
must be full
// so a newNode must be inserted between currentNode and nextNode(or null)
create newNode
newNode.next = currentNode.next
newNode.Array[newNode.last_index] =
currentNode.Array[currentNode.last_index]
insertionsort(elem, currentNode)
currentNode.next = newNode
return startNode
}
}
}
}
}
*END Function*
*You can look at below email for more explanation of unrolled linked list.*
*
*
*
*
*Thanks *
*V.*
*
*
*
*
On Thu, Jul 28, 2011 at 6:43 PM, Varun Nagpal varun.nagp...@gmail.comwrote:
Thanks a lot for your inputs Sunny. Your solution seems correct to me. Is
this the only method ? Can you think of any other methods which could be
more efficient. I heard merge sort or quick sort are also used for linked
lists. Do you see their applicability in this case?
What about duplicate avoidance ? Do I perform binary search on each node
during the list construction to check for duplicates? Or you can think of a
more efficient way?
Thanks a lot
Varun
On Thu, Jul 28, 2011 at 11:02 AM, sunny agrawal
sunny816.i...@gmail.comwrote:
Nice Problem :)
i think taking care of duplicates is very simple...but main point is
sorted insertion
that has to very carefully done
there are many cases that need to be taken care of
1. if the value to be inserted is between two nodes and both nodes are
fullthen a new node will be inserted in the link list and value to be
inserted will be the first element in the new node
case: (1,2)-(4,5) and 3 need to be inserted
after insertion list will be
(1,2)-(3,x)-(4,5)-NULL
2. else the value that need to be inserted will be inside some node...
if there is empty space in the nodesimply insert using insertion sort
(1,2)-(4,x) and 3 is to be inserted, insertion sort in node 2 will
suffice
(1,2)-(3,4)-NULL
3. but if the node in which the value need to inserted is full then last
number from that node will be shifted to a new node and then insert the
value in the node.
if array_sz is large the one instead of shifting the last element u can
split into two halves and put first half in first and second in 2nd
(1,2)-(3,5)4 to be inserted
(1,2)-(1,4) -(5,x) -NULL
i think considering these 3 cases would suffice...although first case
can be merged with 3rd if programmed carefully
On Thu, Jul 28, 2011 at 3:35 AM, banu varun.nagp...@gmail.com wrote:
Anyone ?
On Jul 26, 10:27 pm, banu varun.nagp...@gmail.com wrote:
Hi,
Basically I am trying to create a blocked linked list(unrolled linked
list) with following properties
- Configurable number of elements in each node
- No duplicate elements in the unrolled linked list
- Linked list is sorted either during insertion or after creating the
linked list
- In place
Assuming I need to create a sorted unrolled linked list with no
duplicate elements with block size say 2
Example: 10,2,4,2,5,7,9.11,11,5
Final blocked linked list: (2,4)-(5,7)-(9,10)-(11,x) or in reverse
order
Note: x means unutilized location in the array wihtin the node. In
case there are not enough elements to insert in a node, some memory
allocated for a node is unutilized
// Following is node structure
#define ARRAY_SZ 2
typedef struct node
{
struct node* next;
long long int elements[ARRAY_SZ];
long long int elemIndex;
}NODE, *NODE_PTR;
Can you suggest me a way to do this correctly and efficiently? It
could be an pseudo text or C-code.
Thanks
Varun
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: Blocked/Unrolled linked list with no duplicates and sorted
Thanks a lot for your inputs Sunny. Your solution seems correct to me. Is
this the only method ? Can you think of any other methods which could be
more efficient. I heard merge sort or quick sort are also used for linked
lists. Do you see their applicability in this case?
What about duplicate avoidance ? Do I perform binary search on each node
during the list construction to check for duplicates? Or you can think of a
more efficient way?
Thanks a lot
Varun
On Thu, Jul 28, 2011 at 11:02 AM, sunny agrawal sunny816.i...@gmail.comwrote:
Nice Problem :)
i think taking care of duplicates is very simple...but main point is
sorted insertion
that has to very carefully done
there are many cases that need to be taken care of
1. if the value to be inserted is between two nodes and both nodes are
fullthen a new node will be inserted in the link list and value to be
inserted will be the first element in the new node
case: (1,2)-(4,5) and 3 need to be inserted
after insertion list will be
(1,2)-(3,x)-(4,5)-NULL
2. else the value that need to be inserted will be inside some node...
if there is empty space in the nodesimply insert using insertion sort
(1,2)-(4,x) and 3 is to be inserted, insertion sort in node 2 will suffice
(1,2)-(3,4)-NULL
3. but if the node in which the value need to inserted is full then last
number from that node will be shifted to a new node and then insert the
value in the node.
if array_sz is large the one instead of shifting the last element u can
split into two halves and put first half in first and second in 2nd
(1,2)-(3,5)4 to be inserted
(1,2)-(1,4) -(5,x) -NULL
i think considering these 3 cases would suffice...although first case
can be merged with 3rd if programmed carefully
On Thu, Jul 28, 2011 at 3:35 AM, banu varun.nagp...@gmail.com wrote:
Anyone ?
On Jul 26, 10:27 pm, banu varun.nagp...@gmail.com wrote:
Hi,
Basically I am trying to create a blocked linked list(unrolled linked
list) with following properties
- Configurable number of elements in each node
- No duplicate elements in the unrolled linked list
- Linked list is sorted either during insertion or after creating the
linked list
- In place
Assuming I need to create a sorted unrolled linked list with no
duplicate elements with block size say 2
Example: 10,2,4,2,5,7,9.11,11,5
Final blocked linked list: (2,4)-(5,7)-(9,10)-(11,x) or in reverse
order
Note: x means unutilized location in the array wihtin the node. In
case there are not enough elements to insert in a node, some memory
allocated for a node is unutilized
// Following is node structure
#define ARRAY_SZ 2
typedef struct node
{
struct node* next;
long long int elements[ARRAY_SZ];
long long int elemIndex;
}NODE, *NODE_PTR;
Can you suggest me a way to do this correctly and efficiently? It
could be an pseudo text or C-code.
Thanks
Varun
--
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.
--
Sunny Aggrawal
B-Tech IV year,CSI
Indian Institute Of Technology,Roorkee
--
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] Re: A Graph Problem
Maybe this problem is related to pigeon hole problem On Mon, May 30, 2011 at 8:44 AM, Aakash Johari aakashj@gmail.comwrote: No, won't work. :( On Sun, May 29, 2011 at 11:39 PM, Aakash Johari aakashj@gmail.comwrote: Can this solution work? Create adjacency matrix where adj[i][j] representing person i doesnt like person j. Now toggle the relations (means now the adj[i][j] will represent person i and person j can live with each other) and find the no. of connected components. No. of connected components will be the number of rooms required. On Sun, May 29, 2011 at 11:29 PM, Aakash Johari aakashj@gmail.comwrote: yes, sorry.. i misunderstood the problem. On Sun, May 29, 2011 at 11:24 PM, anshu mishra anshumishra6...@gmail.com wrote: biaprtie graph is special case when we can color the whole graph just by two colors. -- 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. -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (IIIT Allahabad) -- -Aakash Johari (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 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] If anyone have this book please mail me Thanks in advance
Please refrain from sharing such links and engaging in piracy. I kindly request the admin of this forum to delete all such posts and to warn the users on the forum for possible barring in case they are found to use this forum for piracy and malpractices. On Sat, Apr 30, 2011 at 12:09 PM, Charles Turner chtu...@gmail.com wrote: This doesn't look legal to me. Has the author allowed you to redistribute their book? I can't see any such evidence. If you don't have permission to redistribute the book, you're breaking the law. This is a serious offence. You are lowering the reputation of this list. -- 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] A SIMPLE C++ PROGRAM.
I think these questions are stupid in the sense that no one would ever use these constructs in their production code unless someone wants to write an obscure obfuscated code in some competition. Many times similar expressions are non-portable. Anyways, to understand this and related concepts, please see iso c or c++ standard and try to understand operator precedence, operator associativity and sequence points. On Fri, Apr 29, 2011 at 3:06 PM, Nikhil Gupta nikhilgupta2...@gmail.comwrote: 12 5 because y=4+4+3+1 and x is incremented to 5 On Fri, Apr 29, 2011 at 2:01 PM, MANNU manishkr2...@gmail.com wrote: *Can anyone please explain me the output of this program:* int x=1; int y=x++ + ++x + ++x + x++; couty; coutx; -- 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. -- Nikhil Gupta Senior Co-ordinator, Publicity CSI, NSIT Students' Branch NSIT, New Delhi, India -- 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] Clock Algorithm
I do know about event based simulation in digital circuit simulators.. It would be interesting to know.what exactly algorithms they use On Fri, Mar 4, 2011 at 5:27 PM, Luciano Junior luciano@gmail.comwrote: Hello, I need a clock algorithm to use with in a simulation system that I be creating. Someone have any Idea ? -- Luciano Soares Pinheiro Jr. Analista desenvolvedor Sr. -- 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] Parallel algorithms
Practical - Good mix of theory and practice 1. The Art of Multiprocessor Programming by Maurice Herlihy Nir Shavit 2. Introduction to Parallel Computing, Second Edition. By Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar 3. Herb Sutter's Blog on Concurrency API Specific 4. Oreilly's Intel TBB. 5. Programming Massively Parallel Processors (CUDA) 6. Using OpenMP Portable Shared Memory Parallel Programming Advanced and more theoretical - Principles of Concurrent and Distributed Programming by M.Ben Ari On Fri, Feb 18, 2011 at 3:07 PM, Umer Farooq the.um...@gmail.com wrote: Hello, Can anyone suggest me a good book for parallel algorithms? -- Umer -- 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] Intel Question
I understand the algorithm, but what is the question? On Wed, Jan 26, 2011 at 10:10 AM, bittu shashank7andr...@gmail.com wrote: In order to make their newest microcontroller as cheap as possible, the ACME Widget Company designed it with a very simple cache. The processor is connected to a slow memory system that contains n bytes, numbered 0 to n - 1. The cache holds a copy of k of these bytes at a time, for fast access. It has a base address (referred to as base below), and it holds a copy of the bytes numbered base, base+1, ..., base+k-1. When a program reads a byte, the cache controller executes the following algorithm: 1. Find a new range of k bytes which contains the requested byte, such that the difference between the old and new base addresses is minimized. Note that if the requested byte was already in the cache, then the base address will not change. 2. Update the cache to the new range by reading from the memory system any bytes that are in the new range but not the old range, and discarding any bytes that were in the old range but not the new range. 3. Return the requested byte to the program. To analyze the performance of a program, you wish to know how many bytes are read from the memory system. The numbers of the bytes that the program reads are given in addresses, in the order that they are read. When the program starts, the base address is 0. Thanks Regards Shashank -- 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.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 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] P ! = NP
Yeah,,,...lets hope the next turing goes to this Indian. Its still being verified. On Thu, Aug 12, 2010 at 12:54 AM, Kishen Das kishen@gmail.com wrote: http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html Check out this cool news. Kishen -- 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] Google Interview Question
First attempt: sort them and add the 2 largest numbers 2nd attempt: find 1st and 2nd largest number and add them. On Wed, Jul 14, 2010 at 7:27 AM, Debajyoti Sarma sarma.debajy...@gmail.comwrote: An array contains the set of positive integer. Find the largest number c such that c=a+b where a,b,c are distinct number of the set? [Consider , reducing complexity] -- 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] Knapsack - 0-1 - Brute force
Why do you want to try a brute force approach, when you have some better algorithms and heuristics available? On Mon, Jun 7, 2010 at 10:07 PM, Jean Carlo Mendes jean.men...@gmail.comwrote: Hello Guys Anyone have a implementation of knapsack 0-1 using brute force approach ? Or… Do you have some link with a sample in C language? Thanks jean -- 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] matix flipping
This question was asked in a Microsoft interview 2 years back. On Mon, Jun 7, 2010 at 8:05 PM, divya jain sweetdivya@gmail.com wrote: let a[n][n] be the input array nd b[][] be the output for(i=0;in;i++) for(j=0;jn;j++) b[i][j]=a[n-j-1][n-i-1] On 7 June 2010 08:26, sharad sharad20073...@gmail.com wrote: write a c routine to flip an nXn matrix about its non major diagnol 3 4 5 6 7 9 1 2 8 Transpose is: 8 9 5 2 7 4 1 6 3 -- 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: Complexity of Algorithms
A program is just an implementation of an algorithm. You may use any language to implement an algorithm as a program. To make time and space complexity analysis independent of language or computing platform, we relate them with algorithm. This is also useful when you need to compare different solutions to same problem without bogging down by programming language constructs . That is why its a good practice to write algorithms in pseudo programming language and do the complexity analysis and then perform comparison, otherwise its simply impossible to do complexity analysis of all possible implementations of the algorithm. Book by Thomas cormen is bible of algorithms, but is too big and not easy to read. The other book that I had suggested has possibly the best possible explanations of concepts at undergraduate level. I havent come across any other books better then these two. There is one more book which is slightly more basic and is easier to read : Analysis of Algorithms, Jones Barlett Publications On Sat, May 8, 2010 at 5:18 PM, scanfile rahul08k...@gmail.com wrote: sorry for replying after a long hours. @varun thanx for great tutorialbut still i'm confused in the complexity concept of algorithm. I do not understand that complexity is for the algorithms or for programs. On May 8, 11:20 am, Ralph Boland rpbol...@gmail.com wrote: On May 5, 7:59 am, Varun Nagpal varun.nagp...@gmail.com wrote: Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. For data structures there is often three complexities. 1) Time to build the data structure. (e.g. build a balance binary tree in linear time). 2) Space required by data structure. (e.g. tree requires linear space). 3) Time to use the data structure to gather some piece of information. (e.g. find leaf node from root node in O(log n) time. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. I tend to think average case is more important than worst case. Which is more important: the average case for quicksort or the worst case for quicksort? One of the reasons once sees worst case analysis much more than average case analysis is that average case analysis is usually much harder to do, for example the worst case and average case analysis
Re: [algogeeks] Complexity of Algorithms
Complexity of an algorithms is focussed on two aspects: Time it takes to execute the algorithm(Time Complexity) and the amount of space in memory it takes to store the associated data(Space Complexity). Most literature in computer science focuses on Time Complexity as it directly influences the performance of algorithm. The complexity of an algorithm is usually based on a model of machine on which it will execute. The most popular model is RAMhttp://en.wikipedia.org/wiki/Random_access_machineor Random Access Machine Model. Simple assumption of this machine model is that every operation(arithmetic and logic) takes unit or single step and each of this step takes some constant time. So by finding the number of steps it takes to execute the algorithm, you can find the total time it takes to execute the algorithm. In this sense Unit Time or Unit Step are considered equivalent or synonymous. Although RAM is not accurate model of actual machine, but its main advantage is that it allows a machine independent analysis comparison of algorithms. So, the Time Complexity of an algorithm is measured in terms of the total number of steps the algorithm takes before it terminates. It is expressed usually as a function of Input Size or problem size. Input size can have different meanings, but for simplicity you can assume it to be number of objects that is given as input to the algorithm(say N). An object could mean an integer, character etc. Now if T(N) is the time complexity of the algorithm T(N) = Number of steps(or time) it takes to execute the algorithm. T(N) could be a any mathematical function like a function in constant , linear multiple of N function , polynomial in N function, poly-logarithmic function in N, or Exponential function in N etc. Finding the Time Complexity of an algorithm basically involves analysis from three perspectives: worst case execution time, average case execution time and best case execution time. The algorithm will take different number of steps for different class of inputs or different instances of input. For some class of inputs, it will take least time(best case). For another class of inputs it will take some maximum time(worst case). Average case execution time analysis requires finding average(finding expectation in statistical terms) of the number of execution steps for each and every possible class of inputs. Best case execution time is seldom of any importance. Average case execution time is sometimes important but most important is Worst Case execution time as it tells you the upper bound on the execution time and so tells you lower bounds on obtainable performance. In Computer science though, expressing T(N) as a pure mathematical function is seldom given importance. More important is knowing asymptotic behavior of algorithm or asymptotic growth rate i.e how quickly does T(N) grows as N goes to a extremely large values(approaching infinity or exhibits asymptotic behavior). So instead of expressing T(N) as a pure and precise mathematical function, different other notations have been devised. As far as I know, there are at least 5 notations used to express T(N) namely Big-O (O), Small-o(o), Big-Omega(Ω), Small-omega(w), Theta(*Θ). * Big-O is used for representing upper bound(worst case), while Big-Omega is for expressing lower bounds(best case). Small or Little notations are more stricter notations. Theta notation is used for expressing those functions whose upper and lower bounds are same or constant multiple of the same function For more thorough understanding, I suggest you to read the following: How to think about algorithms, Jeff Edmonds, Cambridge Press. Chapters: 22, 23, 24, 25, 26, 27 Regards Varun On Mon, May 3, 2010 at 8:15 PM, scanfile rahul08k...@gmail.com wrote: Pls can anyone help me out that how to calculate the complexity of any Algorithm? -- 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] Where does OS scheduling run??
I guess with Virtual machines, instructions that simulate instructions of microprocessor are scheduled onto the real processor. But good question is how the scheduling of real microprocessor instructions done in a virtual machine. And the answer is again that its done on virtual processor, which essentially has all hardware components of real processor modeled in software. All sub-parts of this software representing essential hardware components, again run synchronously (in parallel) either at instruction accurate level or cycle accurate level. All new processor that are designed as of today, are first mostly are verified using simulators written in hardware description languages like VHDL/SystemVerilog/SystemC and then simulated either in software or hardware. For hardware simulation, in some cases its eventually possible to create them on FPGA's and verify before they are sent to fab lab. Its an arduous task. For example, you can get HDL code for free for SUN Open Sparc processor and can flash it on FPGA. So It doesn't really matter whether your processor is real or virtual, so you need to understand architecture principles and some digital electronics to understand at hardware(VLSI ) level Intel x86 and now x64 are the most popular architectures. Other popular architectures are ARM, MIPS, SPARC, PowerPC, etc. You should probably read the book: Computer Architecture, by hennrey Peterson On Tue, May 4, 2010 at 10:49 PM, praba garan prabagara...@gmail.com wrote: I think it is necessary to study the full architecture of INTEL MotherBoard to get a full picture. How does scheduling happen incase of Virtual Machines?? Then how does a packet coming to the Guest OS is sent to Guest OS. ie, either directly to Guest OS or through Host OS. With Regards, Prabagaran. On Mon, May 3, 2010 at 12:25 PM, Varun Nagpal varun.nagp...@gmail.com wrote: I think its a good question and fairly complicated to explain at hardware(RTL) level. Anyways, let me give it a try : You suggested that only 1 instruction is executed by one processor, which is not true(if you have read computer architecture). Briefly, lets assume the instruction pipeline(assuming only single hardware thread) is filled with instructions from the present thread(or process) of execution. Assume number of pipeline stages to be 20. In the pipeline, 20 instructions from the current instruction control flow are executing synchronously on every clock tick. Depending upon the design of pipeline, data from registers/memory is read in different pipeline stages. Also there may also be many execution stages(ALU) before the data is written to register/memory. The OS kernel keeps a track of all the threads/processes presently executing, active, waiting, suspended etc. in memory in the form of a data structure, which is to say that it always knows the next thread/process it needs to schedule on to the processor. I think it has a compare register that stores an arbitrary number(as decided by kernel) of clock ticks for a time slice expiry and keeps another counter register to keep track of time slice expiration for present thread. At every clock tick, it increments the counter register and compares it with compare register. This summing and comparison is done by inserting an instruction in the current instruction flow. The point is that a clock interrupt is generated whenever the values of the counter and the compare registers match. When this does occur, the next PC value,registers etc(i.e its context information) is pushed onto the stack and a jump is made to an area in memory storing an interrupt vector table. I also assume that when this jump is made, the OS kernel supplies some information to the jump instruction about the next thread to be executed. This information maybe stored in another dedicated register. Now by using this information and interrupt vector table, it can find out the memory address of next thread(ii.e next instruction) to be executed. The PC including other registers is then simply loaded with context information of the new thread. Important thing here is again that when all of this is happening, the pipeline may still be executing instructions from the previous thread. In addition it will contain interrupt instructions! Only when PC is updated(in some stage of pipeline) that the instruction fetch stage will start fetching instructions from instruction memory area of new thread. In a 20 stage pipeline, it is still highly likely that it may be the case that pipeline contains instructions from old thread, followed by interrupt instruction , followed by instructions from new thread. I hope this explanation should give you better clarity. On Sun, May 2, 2010 at 7:01 PM, harit agarwal agarwalha...@gmail.com wrote: although CPU is busy in exexcution...it check's its registers values for the pending interrupts .. if any interrupt is pending at the end of the current CPU cycle
Re: [algogeeks] Where does OS scheduling run??
I think its a good question and fairly complicated to explain at hardware(RTL) level. Anyways, let me give it a try : You suggested that only 1 instruction is executed by one processor, which is not true(if you have read computer architecture). Briefly, lets assume the instruction pipeline(assuming only single hardware thread) is filled with instructions from the present thread(or process) of execution. Assume number of pipeline stages to be 20. In the pipeline, 20 instructions from the current instruction control flow are executing synchronously on every clock tick. Depending upon the design of pipeline, data from registers/memory is read in different pipeline stages. Also there may also be many execution stages(ALU) before the data is written to register/memory. The OS kernel keeps a track of all the threads/processes presently executing, active, waiting, suspended etc. in memory in the form of a data structure, which is to say that it always knows the next thread/process it needs to schedule on to the processor. I think it has a compare register that stores an arbitrary number(as decided by kernel) of clock ticks for a time slice expiry and keeps another counter register to keep track of time slice expiration for present thread. At every clock tick, it increments the counter register and compares it with compare register. This summing and comparison is done by inserting an instruction in the current instruction flow. The point is that a clock interrupt is generated whenever the values of the counter and the compare registers match. When this does occur, the next PC value,registers etc(i.e its context information) is pushed onto the stack and a jump is made to an area in memory storing an interrupt vector table. I also assume that when this jump is made, the OS kernel supplies some information to the jump instruction about the next thread to be executed. This information maybe stored in another dedicated register. Now by using this information and interrupt vector table, it can find out the memory address of next thread(ii.e next instruction) to be executed. The PC including other registers is then simply loaded with context information of the new thread. Important thing here is again that when all of this is happening, the pipeline may still be executing instructions from the previous thread. In addition it will contain interrupt instructions! Only when PC is updated(in some stage of pipeline) that the instruction fetch stage will start fetching instructions from instruction memory area of new thread. In a 20 stage pipeline, it is still highly likely that it may be the case that pipeline contains instructions from old thread, followed by interrupt instruction , followed by instructions from new thread. I hope this explanation should give you better clarity. On Sun, May 2, 2010 at 7:01 PM, harit agarwal agarwalha...@gmail.com wrote: although CPU is busy in exexcution...it check's its registers values for the pending interrupts .. if any interrupt is pending at the end of the current CPU cycle...it shedules the interrupt handler to further execute the interrupt subroutine... -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: a google question
Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from
cartesian products of A, B or B,A
Sort(A,B)
{
k = 1
N = length(A) = length(B)
C[1..2*N] = []// Empty array
cart_prod_order = 0 // 0 - AxB, 1 - BxA. 0 is default
// Complexity : O(N)
while(k != N+1)
{
if (A[k] B [k])
{
cart_prod_order = 1
break
}
else
{
k = k + 1
}
}
// Choose the correct order of Cartesian product sum
// Complexity: Theta(2N) = O(N)
if (cart_prod_order == 1)
{
// take cartesian product of B and A, storing the sum of ordered
pair (b,a) in each element of C
C[1..2N] = B[1..2] x A[1..N]
}
else
{
// take cartesian product of A and B, storing the sum of ordered
pair (a,b) in each element of C
C[1..2N] = A[1..2] x B[1..N]
}
// Merge
// C[1..N] and C[N+1..2N] are already sorted in descending order
// Complexity: Theta(N)
C[1..2N] = Merge(C[1..N],C[N+1..2N])
return C[1..N]
}
Merge(C,D)
{
i=1,j=1,k=1
E = []
while(i=length(C) OR j=length(D))
{
if(i=length(C) AND (jlength(D) OR C[i]D[j]))
{
E[k] = C[i]
i = i + 1
}
else
{
E[k] = D[j]
j = j + 1
}
k = k + 1
}
return E;
}
On Fri, Apr 30, 2010 at 7:50 PM, banu varun.nagp...@gmail.com wrote:
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
(aN,b1), (aN,b2)(aN,bN)}
assuming we have added in a way such that we find a pair ai bi,
for some i in 1..N such that a(i-1) = b(i-1)
A first observation is that in the worst case, the first 2N numbers in
S will contain the final result of N numbers.
i.e in (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN)
In the best case first N numbers in S will contain the final N numbers
(already sorted in decreasing order)
i.e in (a1,b1), (a1,b2)(a1,bN)
Now, if we consider again the worst case scenario, then we can first
divide 2N numbers in two groups of size N each and each of this group
is already sorted in decreasing order.
i.e (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN)
Now we can simply apply Merge Algorithm on these 2 already sorted
arrays of size N each in O(N) time, which solves the problem
I can be wrong only if the the results lie outside first 2N
numbers(which I hope is not the case).
On Apr 30, 2:05 pm, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
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.
--
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] 400!
@Rajesh gave a simple elegant solution.
A look at a Linux calculator : you can even calculate 99! =
8.854887824e+5584950 in few seconds. I just looked at the code(its open
source right!), which is not so easy to understand in few minutes.
Here is the some part of code I extracted from source files:
/* Size of the multiple precision values */
#define MP_SIZE 1000
/* Base for numbers */
#define MP_BASE 1
/* Object for a high precision floating point number representation
*
* x = sign * (MP_BASE^(exponent-1) + MP_BASE^(exponent-2) + ...)
*/
typedef struct
{
/* Sign (+1, -1) or 0 for the value zero */
int sign; //, im_sign;
/* Exponent (to base MP_BASE) */
int exponent; //, im_exponent;
/* Normalized fraction */
int fraction[MP_SIZE]; //, im_fraction[MP_SIZE];
} MPNumber;
void mp_factorial(const MPNumber *x, MPNumber *z)
{
int i, value;
/* 0! == 1 */
if (mp_is_zero(x)) {
mp_set_from_integer(1, z);
return;
}
if (!mp_is_natural(x)) {
/* Translators: Error displayed when attempted take the factorial of
a fractional number */
mperr(_(Factorial is only defined for natural numbers));
mp_set_from_integer(0, z);
return;
}
/* Convert to integer - if couldn't be converted then the factorial
would be too big anyway */
value = mp_cast_to_int(x);
mp_set_from_mp(x, z);
for (i = 2; i value; i++)
mp_multiply_integer(z, i, z);
}
mp_multiply_integer(z, i, z) subroutine is too big too put in here, too see
its code visit: http://live.gnome.org/Gcalctool
http://live.gnome.org/Gcalctool
On Mon, May 3, 2010 at 2:34 PM, Anil C R cr.a...@gmail.com wrote:
@Jitendra
but that's no fun [?]
-
Anil
On Mon, May 3, 2010 at 5:12 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@siddharth and prasoon either design a very long integer library yourself,
or use gmp library in cpp or BigInteger Class in java.
Regards,
vignesh
On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote:
But is there any way to accomplish this without an array ? Even for 100!.
On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote:
I think challenge here is not the Execution time, but the storage. 300 !
or 400! should generally go beyond the storage capabilities of long long
ints in cpp.
@ Rohit Saraf: Hence, I don't know if even tail recursion will
ultimately be able to store the output.
I think Rajesh Patidar's answer fits the bill well, in terms of storage.
On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
I agree with abhijith. But given some very large x for which i would
have to find factorial.
I would either
(i) use gmp in cpp or BigInteger or java if its not a lab exercise or
an interview
(ii) use simple brute multiplication algorithm.
The second approach requires
(a) The no. of digits in n! for making storage available
(b) The calculation itself which I would brute force
References:
http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html
http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it
http://delphiforfun.org/programs/big_factorials.htm
On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
google it... u will gt it
i am on mobile... cannot explain now..
On 5/2/10, divya jain sweetdivya@gmail.com wrote:
wat is tail recursion plz explan in detail
On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com
wrote:
@divya use tail recursion and rest should be fine..
--
--
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%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
Re: [algogeeks] Re: a google question
@Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do this. On Mon, May 3, 2010 at 1:23 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: The Question only ask to print first n number and each array array is of size n So in the worst case we will take combination of 1st element of first array with all the element of second array. my above code runs in O(n) taking this considerations... any comments or test case where it fails??? Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. 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 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
