Re: [algogeeks] Re: tree from linked list

[Yalla Sridhar]

@atul linked list can be converted to array with O(n) both space @ time
overhead. then tree can be built in O(n)

On Sat, May 15, 2010 at 2:53 AM, W Karas  wrote:

> See the definition of:
>
>template
>bool build(fwd_iter p, size num_nodes)
>
> Within the iter subclass, within the base_avl_tree template in:
>
> http://wkaras.webs.com/gen_cpp/avl_tree_h.txt
>
> On May 2, 9:08 am, divya  wrote:
> > u are given a sorted lnked list construct a balanced binary search
> > tree from it.
> >
> > --
> > 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] BST

[Yalla Sridhar]

if the tree has parent pointer then we can apply similar approach,,
increment and decrenent... and can also be done in O(1)

have to poninters pointed to the min and max nodes and them move pointers by
checking the sums..

On Fri, May 14, 2010 at 5:03 PM, anna thomas  wrote:

> @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum,
> then decrement the 2nd ptr(ptr at end of array)
> In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
> dec ptr2 1+4 = 5 (sum < 6)
> inc ptr2: 2+4 =6 (got the ans)
>
> But the qs mentions that it should be in O(1) space.
> Regards,
> Anna
>
>
>
>  On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf  > wrote:
>
>> @divya : i guess... it wont work.
>> consider Array {1,2,3,4,123456}
>> and you want sum 6.
>>
>> @prashant: Is it O(n)?
>>
>> I guess after converting to array and removing all entries > sum, we
>> should start with the smallest element
>> and scan the elements from last till we get some value x which together
>> with the smallest value sums to < sum. Call this position POS1.
>> If we get required sum somewhere in the process, cool !
>> Else take drop the elements after POS1 and also the smallest element.
>> Recurse on the remaining.
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>>
>>
>> On Fri, May 14, 2010 at 3:51 PM, Prashant K wrote:
>>
>>> i think it can done like this,
>>> assume we have to find 'x' and 'y'  wer s='x'+'y'
>>>
>>> 1) select ith node from tree (from beginning to end)
>>> 2) y= s - " ith number (node)"
>>> 3) now search for 'y' in BST if we found then there is node such that s=
>>> x + y; otherwise no..
>>>
>>> -- Prashant Kulkarni
>>> || Lokaha Samastaha Sukhino Bhavanthu ||
>>> || Sarve Jana Sukhino Bhavanthu ||
>>>
>>>
>>>
>>> On Fri, May 14, 2010 at 2:47 AM, divya jain wrote:
>>>
 form a sorted  array from inorder traversal of tree. now take to
 pointers one to the beginning of array and other at the end. now check if
 the sum of element is greater than reqd sum then increment 1st ptr. if 
 their
 sum is less than reqd sum then decrement 2nd ptr. if their sum is equal to
 the reqd sum then this is the ans..
 hope it will work..


 On 13 May 2010 20:11, jalaj jaiswal  wrote:

> given a bst... find two nodes whose sum is equal to a number k ... in
> O(n) time and constant space...
>
> --
> 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.
>

 --
 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.
>>>
>>
>> --
>> 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.
>

-- 
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] Convert a Binary tree into spike.

[Yalla Sridhar]

do the levels need to be linked?? either case... the approach should be

use BFS to get the elements by level and then link them
On Thu, May 13, 2010 at 9:18 AM, vinayan c  wrote:

> Something like this
>1
>2   3
>  4 5 67
>
>
>  1
>  |
>  2->3
>  |
>  4->5->6->7
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
> --
> 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!

[Yalla Sridhar]

python int has no bounds, it can scale upto the mem u have available on your
computer.

On Thu, May 13, 2010 at 7:53 AM, Nikhil Agarwal
wrote:

> @jitendra: your python code is awesome and it works.:)
>
>
> On Wed, May 12, 2010 at 6:37 PM, divya jain wrote:
>
>> thanx to all 4 the solutions..
>>
>>
>> On 3 May 2010 18:39, Varun Nagpal  wrote:
>>
>>> @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
>>>  
>>> On Mon, May 3, 2010 at 2:34 PM, Anil C R  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  wrote:
>
>> But is there any way to accomplish this without an array ? Even for
>> 100!.
>>
>>
>> On 2 May 2010 06:15, Prasoon Mishra 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 wrote:

> google it... u will gt it
>
> i am on mobile... cannot explain now..
>
> On 5/2/10, divya jain  wrote:
> > wat is tail recursion plz explan in detail
> >
> > On 2 May 2010 08:15, Rohit Saraf 
> 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/~rohitfeb14
> 
>>>

Re: [algogeeks] Complexity of Algorithms

[Yalla Sridhar]

it is impossible 2 give a formula or a generic method to calculate the
complexity for any algo..

method to calcuate complexity differs per algo

On Mon, May 3, 2010 at 11:45 PM, scanfile  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.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??

[Yalla Sridhar]

yea if your processor has multiple cores or is Hyper Threading support then
it can execute more than 1 instruction concurrently.

On Thu, May 6, 2010 at 12:10 AM, praba garan  wrote:

> 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 wrote:
>
>> 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 
>> 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 
>> > 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 instruc

Re: [algogeeks] Where does OS scheduling run??

[Yalla Sridhar]

after each instruction is executed cpu checks for any pending interrupts and
services them before executing the next instruction

On Sun, May 2, 2010 at 10:25 PM, praba garan  wrote:

> @ Pradeep
>
> *CPU stop its current processing and goes to the interrupt subroutine*
>
> you have mentioned that the CPU stops its current processing and goes to
> the interrupt subroutine..
>
> My Question is how does the CPU stops its execution(any special hardware
> involved) because it is busy in executing the current instruction.
>
>
> With Regards,
> Prabagaran.
>
>
>
> On Sun, May 2, 2010 at 4:02 AM, pradeep verma wrote:
>
>> lets suppose Processor executing a instruction(process1) and another
>> process2 tries to take the control of CPU so inorder to inform CPU it has to
>> interrupt the CPU right
>> now we know that if interrupt comes CPU stop its current processing and
>> goes to the interrupt subroutine...now CPU knows that its a pre-emption
>> interrupt so CPU first run its short term scheduler(this will inform CPU
>> that the interruting process priority is less or greater ..n if greater than
>> CPU goes to previous process1 preempt it and start executing higher priority
>> process2 )
>>
>> I think its clear
>>
>> Regards
>> Pradeep
>>
>>
>>
>> On Sun, May 2, 2010 at 3:06 AM, praba garan wrote:
>>
>>> @ Guillermo Garcia
>>>
>>> The link gives the overall abstract idea.
>>> I am talking in register level.
>>> When a user process executes
>>>
>>> 1. PC program counter will contain the address of the next instruction in
>>> user code.
>>> 2. Processor registers(accumulator ...) contain the current instruction
>>> data.
>>>
>>> Then where does the interrupt actually arrives??
>>>
>>> And by that time the user process the control, then who does the
>>> preempting and how??
>>>
>>> With Regards,
>>> Prabagaran.
>>>
>>>
>>>
>>> On Sun, May 2, 2010 at 2:35 AM, Guillermo Garcia 
>>> wrote:
>>>

 read here -> http://en.wikipedia.org/wiki/Preemption_%28computing%29



 Time slice

 The period of time for which a process is allowed to run in a preemptive
 multitasking system is generally called the *time slice*, or *quantum*.
 The scheduler is run once every time slice to choose the next process to
 run. If the time slice is too short then the scheduler will consume too 
 much
 processing time.

 An interrupt  is scheduled to
 allow the operating system
 kernel  to
 switch between processes when their time slices expire, effectively 
 allowing
 the processor’s time to be shared between a number of tasks, giving the
 illusion that it is dealing with these tasks simultaneously, or
 concurrently. The operating system which controls such a design is called a
 multi-tasking system.




 On Sat, May 1, 2010 at 5:26 PM, praba garan wrote:

> @ Guillermo Garcia
>
> Suppose a user program is executing and and clock interrupt arrives..
> Then who receives the interrupt??
> Can you xplain me the clock interrupt(like any hardwares involved) bit
> detailed??
>
> With Regards,
> Prabagaran.
>
>
>
> On Sun, May 2, 2010 at 1:38 AM, Guillermo Garcia  > wrote:
>
>> The scheduler takes control with a clock interruption. Then it
>> analyzes if it has to preempt or not the running task.
>>
>>   On Sat, May 1, 2010 at 5:00 PM, praba garan > > wrote:
>>
>>>   Hi all,
>>> I have a doubt in OS.
>>> The scheduler does the process of preemption.
>>> And one processor can run atmost 1 instruction at a time.
>>> Then how & where does the scheduler run??
>>>
>>> With Regards,
>>> Prabagaran.
>>>
>>> --
>>> 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.
>>
>
>   --
> 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
>