Re: [algogeeks] question
@vivek, Where do you store pairs sum ?, Space is O(N) ... :) Thanks, Sathaiah On Mon, May 3, 2010 at 9:03 PM, vivek bijlwan viv...@gmail.com wrote: copy the array(A) in a different array(B) to store the index info.(space O(n)) sort(A) take each pair's sum ( complexity O(n^2) ) and with that do a binary search for the 3rd element needed.(O(log(n))). Check for the indices in B. i believe it can be done in better time somehow. On Mon, May 3, 2010 at 6:48 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(N2log 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. -- 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] question
@ vivek sir thanks On Mon, May 3, 2010 at 9:03 PM, vivek bijlwan viv...@gmail.com wrote: copy the array(A) in a different array(B) to store the index info.(space O(n)) sort(A) take each pair's sum ( complexity O(n^2) ) and with that do a binary search for the 3rd element needed.(O(log(n))). Check for the indices in B. i believe it can be done in better time somehow. On Mon, May 3, 2010 at 6:48 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(N2log 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. -- 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. -- 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.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...it
[algogeeks] Complexity of Algorithms
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: a google question
@Varun output for your test cases are as below: arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 33 arr1[1] + arr2[0] = 28 arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 37 arr1[0] + arr2[2] = 36 what i was talking about worst case was that is if one have to find more than N elements of array c then it is possible that one of the pointer go out of boundry of 1 to N in worst case. On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal varun.nagp...@gmail.comwrote: @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. -- 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] Where does OS scheduling run??
Windows Task Manager Performance tab shows the presence of two processors. Will 2 instructions be executed concurrently?? With Regards, Prabagaran. On Wed, May 5, 2010 at 4:56 PM, Varun Nagpal varun.nagp...@gmail.comwrote: 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.
