Wish you all a vary happy and safe Diwali! On Fri, Nov 5, 2010 at 4:53 PM, <algogeeks+nore...@googlegroups.com<algogeeks%2bnore...@googlegroups.com> > wrote:
> Today's Topic Summary > > Group: http://groups.google.com/group/algogeeks/topics > > - Graph Theory Problem <#12c1bc6dc083548e_group_thread_0> [1 Update] > - HAPPY DIWALI FOR ALL...............<#12c1bc6dc083548e_group_thread_1>[1 > Update] > - Happy Diwali .. <#12c1bc6dc083548e_group_thread_2> [1 Update] > - Happy Diwali! <#12c1bc6dc083548e_group_thread_3> [1 Update] > - Max pyramid path <#12c1bc6dc083548e_group_thread_4> [8 Updates] > - compression <#12c1bc6dc083548e_group_thread_5> [4 Updates] > - design_algo <#12c1bc6dc083548e_group_thread_6> [1 Update] > > Topic: Graph Theory > Problem<http://groups.google.com/group/algogeeks/t/94f550d17fdb7a6> > > Raj <rajmangaltiw...@gmail.com> Nov 05 03:11AM -0700 > ^<#12c1bc6dc083548e_digest_top> > > http://en.wikipedia.org/wiki/Graph_partition > > > > > Topic: HAPPY DIWALI FOR > ALL...............<http://groups.google.com/group/algogeeks/t/c9432e1d3f8bb4cb> > > UMESH KUMAR <kumar.umesh...@gmail.com> Nov 05 03:40PM +0530 > ^<#12c1bc6dc083548e_digest_top> > > > > http://topwebdownloads.com/wp-content/uploads/2009/10/diwali-greetings-2.gif > > > > Topic: Happy Diwali > ..<http://groups.google.com/group/algogeeks/t/adaf4d0456d34a75> > > LALIT SHARMA <lks.ru...@gmail.com> Nov 05 02:36PM +0530 > ^<#12c1bc6dc083548e_digest_top> > > Wish u all a happy diwali ... > -- > Lalit Kishore Sharma > IIIT Allahabad (Amethi Capmus) > 5th Sem > > > > Topic: Happy > Diwali!<http://groups.google.com/group/algogeeks/t/5c10d1754d2051b6> > > sourav sain <souravs...@gmail.com> Nov 05 11:26AM +0530 > ^<#12c1bc6dc083548e_digest_top> > > Wish you and your family a Bright and Prosperous Diwali. > > Regards, > Sourav > [image: > > diwali-diyas.jpeg]<?ui=2&ik=4f1ebe5da5&view=att&th=12c1a980b57e423f&attid=0.1&disp=inline&realattid=f_gg4neyjf0&zw> > > > > Topic: Max pyramid > path<http://groups.google.com/group/algogeeks/t/9646a5dd56e88632> > > "juver++" <avpostni...@gmail.com> Nov 04 09:40AM -0700 > ^<#12c1bc6dc083548e_digest_top> > > Use dynamic programming. > > > > > > Dave <dave_and_da...@juno.com> Nov 04 09:50AM -0700 > ^<#12c1bc6dc083548e_digest_top> > > @Piyush: Treat the data as an implicit binary tree, with the children > of a[i] being a[2*i] and a[2i+1] if a[] is a 1-based array, or a[2*i > +1] and a[2*i+2] if a[] is a 0-based array. Traverse the tree and > accumulate the sum as you descend. When you reach the leaves, keep > track of the maximum sum and its path. When the traversal is finished, > you will have your answer. > > Dave > > > > > > piyush rai <piyushra...@gmail.com> Nov 05 12:48AM +0530 > ^<#12c1bc6dc083548e_digest_top> > > Thanks, I think that will work :) > > > > > > "juver++" <avpostni...@gmail.com> Nov 04 01:19PM -0700 > ^<#12c1bc6dc083548e_digest_top> > > You are wrong. It's not a binary tree. Cause multiple elements have > adjacent childs. > Right solution is to apply DP: > dp[i][j] - maximum sum that is ends into i-th row and j-th column. > Then make only 2 transitions to the (i+1)-th row. > Complexity is n^2. > > > > > > Dave <dave_and_da...@juno.com> Nov 04 08:31PM -0700 > ^<#12c1bc6dc083548e_digest_top> > > @juver++: Oops. Right you are! A corrected solution is just a little > more complicated. If the data is presented in an array as in the > previous posting, a[]={1,2,3,4,5,6,7,8,9,10} corresponding to the > triangle > 1 > 2 3 > 4 5 6 > 7 8 9 10 > then we let A(i,j) be the jth entry in the ith row, both 0-based, so > that in this example, A(2,1) = 5. Then the array can be treated as an > implicit DAG (directed acyclic graph) where the children of A(i,j) are > A(i+1,j) and A(i+1,j+1). Using the correspondence that A(i,j) = a[i*(i > +1)/2+j)], you can traverse the DAG the same way I described > traversing the binary tree. > > Dave > > > > > > piyush rai <piyushra...@gmail.com> Nov 05 09:30AM +0530 > ^<#12c1bc6dc083548e_digest_top> > > there is a better way to get a child of node at index i and level l > The child will always be @ index (i+l+1) and (i+l+2) then solve > recursively > keeping and array of length of level, top-down approach OR do a bottom > up > approach without using any extra memory. > > > > > > > > Dave <dave_and_da...@juno.com> Nov 04 09:31PM -0700 > ^<#12c1bc6dc083548e_digest_top> > > @Piyush: Hmmm. Children of i = 0, l = 0 are a[0+0+1] and a[0+0+2]. > Check. > Children of i = 0, l = 1 are not a[0+1+1] and a[0+1+2]; they are a[3] > and a[4]. > Am I missing something? > > Dave > > > > > > Piyush <piyushra...@gmail.com> Nov 05 11:02AM +0530 > ^<#12c1bc6dc083548e_digest_top> > > sorry children of index i at level l should be > > a[i+l] and a[i+l+1] ( it is 0 index array and the level starts from 1 , > 0 > level signifies no elements) > > lets take a simple example > a[0]=1 has two children and (0+1) and (0+1 +1) i.e a[1] and a[2] > for a[1] the children are at ( 1+2) and (1+2 +1) i.e. at a[3] and a[4] > for a[3] the children are at (2+2) and (2+ 2 +1) i.e. at a[4] and a[5] > > I hope you got it now. > > > > > Topic: > compression<http://groups.google.com/group/algogeeks/t/498f1baffb1f60b5> > > Chi <c...@linuxdna.com> Nov 04 04:47AM -0700 > ^<#12c1bc6dc083548e_digest_top> > > Short: Without an distribution model, you can't. I.e. you have to give > us more information what kind of data do you want to compress ( text, > image, music, video, radio, etc. pp. ). Compression is always based on > redundancy. > > Length: RLE, Golomb-Code. > > > > > > umair <umirz...@gmail.com> Nov 04 10:58AM -0700 > ^<#12c1bc6dc083548e_digest_top> > > try to use huffmans encoding for such kind of compressions. > > > > > > neeraj agarwal <itsneerajagar...@gmail.com> Nov 05 12:20AM +0530 > ^<#12c1bc6dc083548e_digest_top> > > > > > > piyush rai <piyushra...@gmail.com> Nov 05 12:41AM +0530 > ^<#12c1bc6dc083548e_digest_top> > > For input such as > 00000001111111111111100000000000001111111111110000000 > > Can be written as: > 0 7 14 14 12 7 > > The first character determines the the first character in the original > sequence. > Since there are only two possible values 0 and 1 > the above should be read as > > 7 times 0 then 14 times 1 then 14 times 0 then 12 times 1 then 7 times > 0 > (i.e alternate the bit pattern after each value) > > The worst case will occur when pattern alternates at each step i.e > > 01010101010 > > In this case answer will be > > 0 1 1 1 1 1 1 1 1 1 1 1 > > Total space required will be of the order of the space required by the > previous sequence about 2*size of original input. > > Is this correct? > > > > > > > On Fri, Nov 5, 2010 at 12:20 AM, neeraj agarwal > > > > Topic: > design_algo<http://groups.google.com/group/algogeeks/t/69f2628af1320982> > > kanika suri <surfatheig...@gmail.com> Nov 04 10:08PM +0530 > ^<#12c1bc6dc083548e_digest_top> > > @juver++.Thanx 4 rplyin. > @mohit. I dont thnk so ur logic vl work in all cases. > -- > regards > kanika suri > MCS 2nd yr > DUCS > University of Delhi > > > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Mihir Patil 3rd year, BE (Computer Science), Joint Co-ordinator, Computer Science Association Birla Institute of Technology and Science,Pilani +91-9772974127 -- 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.
