Re: [algogeeks] 10 Most Frequent Search Text

2010-12-27 Thread Chi
erfect hashing with universal hash function. > > you can also use an alternative solution hash function and priority queue > using MAX heap... > > On Mon, Dec 27, 2010 at 2:20 AM, Chi wrote: > > > A trie is a binary tree with it nodes has as many leafs as is > >

Re: [algogeeks] 10 Most Frequent Search Text

2010-12-26 Thread Chi
The only difference to a radix-trie is that the decision to branch either left or right is used with a key of 32-bit. - Ursprüngliche Mitteilung ----- > @Chi: Would you please explain the process in a little bit more > details? It will be helpful. > Is Trie and Radix-Trie same? > >

Re: [algogeeks] 10 Most Frequent Search Text

2010-12-26 Thread Chi
Radix-Trie + Additional Payload Counter - Ursprüngliche Mitteilung - > When we type in google for search it will generate search text. For a > stream of searchtext how you will find most 10 frequent search text. > Give an efficient data structure for this. and also solve it with > possibl

Re: [algogeeks] Re: Simulation algo

2010-12-26 Thread Chi
mming? Can u calculate the lower bounds of a tsp? That I need also to know. Best regards, Chi - Ursprüngliche Mitteilung - > Hello , > discret event simulation is description of the behavior of a referent > (real or virtual) as a digital model . > > On 25 déc, 22:20, Ch

Re: [algogeeks] Re: Simulation algo

2010-12-25 Thread Chi
n send to me , please . > > All the best . > > On 25 déc, 19:12, Glauben wrote: > > Hello , Thank you very much Chi and pschaus for your answers , i know > > that The Ant-Colony-Optimization is related to computer science > > simulation but to Discrete Event Simula

Re: [algogeeks] Simulation algo

2010-12-23 Thread Chi
Ant-Colony-Optimization - Ursprüngliche Mitteilung - > Hello, I'm looking for an algorithm of computer science simulation and > specifically the discrete simulation of any model. Please > All the best. > > -- > You received this message because you are subscribed to the Google > Groups "

Re: [algogeeks] smallest cycle

2010-12-21 Thread Chi
Fleury algorithm. - Ursprüngliche Mitteilung - > The question is to find the length of the smallest cycle in a > bipartite graph G=(V,E) (V - vertices, E - edges). > > Required time complexity: O(|V|^2) > > A given graph is bipartite iff it has no odd length cycles. > > -- > You recei

[algogeeks] Re: switch vs if --> which is faster

2010-11-21 Thread Chi
@Mohit: No, it's just the hierarchical occurent of conditions that makes the switch faster. I really doubt that a compiler build a binary search tree for switches. Also, it a binary tree works for switches why it can't optimize the if-else-condition? Did you make some testing? On Nov 21, 3:28 pm

[algogeeks] Re: switch vs if --> which is faster

2010-11-21 Thread Chi
As he told you it depends on the data runs to the condition. If for exampe statistically there is more of 1's then 0 then the switch loop is faster, because: 1.) case is isolated 2.) You can reorder the case-statement according to the occurrent of the conditions On Nov 21, 2:59 pm, shiva wrot

[algogeeks] Re: compression

2010-11-17 Thread Chi
@Jaladhi: That's why I'm asked him about what file or what data he wants to compress. On Nov 17, 10:14 am, jaladhi dave wrote: > Aren't all files sequence of 1s and 0s while getting stored on disk ? > > On Thu, Nov 4, 2010 at 4:36 PM, neeraj agarwal > wrote: > > >  i have a file contain only 0's

[algogeeks] Re: compression

2010-11-04 Thread Chi
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. On Nov 4, 12:06 pm, neeraj agarwal wrote: >  i

[algogeeks] Re: Knapsack problem

2010-10-30 Thread Chi
> http://rosettacode.org/wiki/Knapsack_problem/0-1 > http://jhave.org/learner/misc/knapsack/knapsack.shtml On Oct 30, 4:26 pm, Rashmi Shrivastava wrote: > pls any one give me solution of this question with detailed description, > > Find an optimal solution to the Knapsack instance > n=7,m=15,(p1,

[algogeeks] Re: Job scheling

2010-10-26 Thread Chi
Looks to me like a variant of the bin-packing problem. Best-Fit, FIrst- Fit, Worst-Fit. I've written an implemention here: > http://sourceforge.net/projects/bin-packing On Oct 26, 8:15 pm, ziyuang wrote: > Job scheduling, sorry for the typo. > > On Oct 26, 8:21 pm, ziyuang wrote: > > > 2 machi

[algogeeks] Re: 10 most repeating words

2010-10-24 Thread Chi
>From Wikipedia: >Thus the MapReduce framework transforms a list of (key, value) pairs into a >list of values. This behavior is different from the functional programming map >and reduce combination, >which accepts a list of arbitrary values and returns >one single value that combines all the va

[algogeeks] Re: 10 most repeating words

2010-10-24 Thread Chi
cision' at each note to be on something other than the first character, so each node stores an offset and the branch options (e.g. if the letter in position 5 is A, go down this branch) On Oct 23, 9:13 pm, Chi wrote: > I've written a kart-trie in php. You can easily extend yourself the

[algogeeks] Re: 10 most repeating words

2010-10-23 Thread Chi
cision' at each note to be on something other than the first character, so each node stores an offset and the branch options (e.g. if the letter in position 5 is A, go down this branch). On 23 Okt., 21:13, Chi wrote: > I've written a kart-trie in php. You can easily extend yourself the

[algogeeks] Re: 10 most repeating words

2010-10-23 Thread Chi
I've written a kart-trie in php. You can easily extend yourself the payload to count the word frequency. > http://sourceforge.net/projects/kart-trie After you build your dictionary from your large file, you can easily find the highest frequency be recursively search the trie. It should be faster

[algogeeks] Re: Lop in Linked List

2010-10-11 Thread Chi
                |            LOOP                | >                                       --- > > -Sri > > > > On Sun, Oct 10, 2010 at 11:23 PM, Chi wrote: > >>http://fgiesen.wordpress.com/2010/10/08/cycle-detection-algorithms-ar... > > > On Oct 10, 7:50 pm, bittu wrote: > >&

[algogeeks] Re: wiki issue on dijkstra's algorithm

2010-10-11 Thread Chi
I have a dijkstra-algoritm-program in php here. If you can send me an adjacent matrix like this: 1 2 3 4 5 2 0 x x x 3 x 0 x x 4 x x 0 x 5 x x x 0 Or better a 2-dimensional array with (start, end, cost) $map = array ( "1", "2", "10", "2", "4", "10", "

[algogeeks] Re: Lop in Linked List

2010-10-10 Thread Chi
> http://fgiesen.wordpress.com/2010/10/08/cycle-detection-algorithms-are-handy-to-know/ On Oct 10, 7:50 pm, bittu wrote: > Can anyone xplain me what is exaxct meanig of lopp in slngly linked > list ...wat should be the approach to solve dis problem > > thnx in advancs > > shashank -- You receiv

[algogeeks] Re: Largest Rectangle in a binary Matrix:

2010-10-10 Thread Chi
23121212" ) > p[i][j]=min(p[i-1][j],p[i,j-1],p[i-1][j-1]]+1;} > > else p[i][j]=0; > f > find p[i][j] such that its has max value. > > On Sun, Oct 10, 2010 at 7:13 PM, Chi wrote: > > Nevermind. I don't think Z-curve is a good solution for this problem. > &g

[algogeeks] Re: Largest Rectangle in a binary Matrix:

2010-10-10 Thread Chi
tp://en.wikipedia.org/wiki/Z-order_%28curve%29 >http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves On Oct 10, 2:04 pm, Harshal wrote: > @Chi > pls provide a link to learn z-curve implementation in such problems -- You received this

[algogeeks] Re: Largest Rectangle in a binary Matrix:

2010-10-07 Thread Chi
Travers the matrix in z-curve or hilbert-curve. This is a heuristic algo. Thus you can find largest square matrix. On Oct 7, 10:39 am, malli wrote: > Largest Rectangle in a Matrix: > > Given an n by n matrix with zeros and ones, find the largest sub- > matrix full of ones in linear time.  I was t

[algogeeks] Re: Ternary Huffman Algorithm

2010-10-05 Thread Chi
A huffman-tree is looking like this: #root # | # 30 # /\ # / \ # /\ #/ \ # 10 20 # || #

[algogeeks] Re: binary matrix

2010-10-04 Thread Chi
can calculate the "Bigmin". On Oct 4, 5:25 pm, mac adobe wrote: > @chi .. can you please share what is this and how it resolves the issue at > hand ? > > regards > --mac > > > > On Mon, Oct 4, 2010 at 5:50 PM, Chi wrote: > > Traverse the matrix in z-order, o

[algogeeks] Re: binary matrix

2010-10-04 Thread Chi
Traverse the matrix in z-order, or hilbert-order. This is a heuristic- algo. On Oct 4, 1:51 pm, mac adobe wrote: > Given a binary matrix, find out the maximum size square sub-matrix with all > 1s. > > For example, consider the below binary matrix. > >    0  1  1  0  1 >    1  1  0  1  0 >    0  1

Re: Fwd: [algogeeks] Prim's algorithm using min heap

2010-10-01 Thread Chi
That's kind of a nice hint. Rather then asking: Where is the link!? On Oct 1, 7:10 pm, Soundar wrote: > i couldn't find any link here. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@go

Re: Fwd: [algogeeks] Prim's algorithm using min heap

2010-10-01 Thread Chi
Where is the link?! On Oct 1, 9:31 am, Rashmi Shrivastava wrote: > @soundar,This link may help u... > > -- Forwarded message -- > From: soundar > Date: Thu, Sep 30, 2010 at 12:48 PM > Subject: [algogeeks] Prim's algorithm using min heap > To: Algorithm Geeks > > Please some one

[algogeeks] Re: Partition of flow graph

2010-09-28 Thread Chi
> http://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/ On Sep 28, 2:52 pm, "yako...@gmail.com" wrote: > Hello > For the data flow graph G= (V,E),I have to determine a partition - in > such a way that > sub graphs created could be computed in parallel and the sub graphs > are approximate

[algogeeks] Re: arrays

2010-09-27 Thread Chi
Move-To-The-Front. On Sep 27, 11:58 pm, Anand wrote: >  Given an array of integers, for each index i, you have to swap the value at > i with the first value smaller than A[ i ] that comes after index i -- You received this message because you are subscribed to the Google Groups "Algorithm Geek

[algogeeks] Re: Inserting a box with lesser dimension into a box of bigger dimensions than that.

2010-09-22 Thread Chi
This is also called bin packing. This is a NP-(Hard) problem. There is no good algorithm to find a solution. All the code you published here a heuristics. Here is a good tutorial: > http://www.developerfusion.com/article/5540/bin-packing/ On Sep 22, 9:12 am, vikas kumar wrote: > you can search f

[algogeeks] Re: Amazon Question-Linux Shell

2010-09-21 Thread Chi
What does [0-9]\+. means? Why do you nested it? On Sep 21, 3:46 pm, Neeraj <17.neera...@gmail.com> wrote: > *grep -R "\<[0-9]\+.[0-9]\+.[0-9]\+.[0-9]\+\>" * | awk -F':' '{print $1}' | > uniq > * > works on my system :P > > > > On

[algogeeks] Re: Amazon Question-Linux Shell

2010-09-21 Thread Chi
With perl installed: find directory | xargs perl -pi -e 's/needle/replace/g' With sed installed: #!/bin/bash find directory > mirror exec 3 $file done On Sep 19, 11:30 pm, bittu wrote: > Linux shell command to find all files in a directory which contain ip > addresses -- You received t

[algogeeks] Re: Amazon Question

2010-09-13 Thread Chi
50% should be define like this: select * from product where name like '%foo%' and len(name) <=6; On Sep 13, 9:18 am, Bharath wrote: > What does 50% or more similarity means?? Trie will work only if prefix is > equal. > > > > On Sun, Sep 12, 2010 a

[algogeeks] Re: Amazon Question

2010-09-13 Thread Chi
Well, no, it is not told that you are given the binaries for the database, too. On Sep 13, 1:27 pm, sharad kumar wrote: > cant it be like '%f%' > > On Mon, Sep 13, 2010 at 2:55 PM, Praveen Baskar > wrote: > > > > > i think that we have to generate substrings from the given string such that > > t

[algogeeks] Re: Amazon Question

2010-09-13 Thread Chi
No, best way is to use a trie, or a suffix-trie. Look here: > http://phpir.com/tries-and-wildcards On Sep 13, 12:32 pm, anuj maurice wrote: > you will have to use the concept of edit distance .. > google for edit distance and you may find too many good articles on it. > "Levenshtein distance" is

[algogeeks] Re: Amazon Question

2010-09-12 Thread Chi
trie On Sep 12, 3:09 pm, sharad kumar wrote: > pagerank algo > > > > On Sun, Sep 12, 2010 at 5:42 PM, Snoopy Me wrote: > > You are given the amazon.com database which consists of names of > > millions of products. When a user enters a search query for particular > > object with the keyword say "

Re: [algogeeks] Re: Modified subset-sum problem

2010-08-31 Thread Chi Hoang
Pairs of: ['1_2'] ['1_3'] ['1_4'] ['1_5'] ['1_6'] ['1_7'] ['2_3'] ['2_4'] ['2_5'] ['2_6'] ['2_7'] ['3_4'] ['3_5'] ['3_6'] ['3_7'] ['4_5'] ['4_6'] ['4_7'] ['5_6'] ['5_7'] ['6_7'] N^2-(N-1). Am 31.08.2010 14:37, schrieb Maria: > @Wladmir- Can u plz explain ur code??? > > -- You received this

[algogeeks] Re: Help with Increment Operators in C!

2010-08-28 Thread Chi
In php it is 19. On Aug 28, 1:35 pm, jagadish wrote: > I ran this code.. > > int main() { int x=5; > printf("%d",(x++ + ++x + x++)); > > } > > The output printed was 18 instead of 19.. Should it not be 19? -- You received this message because you are subscribed to the Google Groups "Algorit

Re: [algogeeks] Binary tree to LL

2010-08-26 Thread Chi Hoang
Am 26.08.2010 18:59, schrieb krazee koder: > Give all possible methods to flatten a binary tree to a linked list. > > for eg. > >50 > / \ > 25 60 > / \ / \ > 530 55 75 > > > should be flattened to 5->25->30->50->55->60->75 > > PS: note that the tree should be

[algogeeks] Re: knight moves in chess

2010-08-25 Thread Chi
her I know your nickname). At least can you confirm me this number n^2-(n-1) edges if the knight start-position and end-position is such that he travels all points of the graph? On Aug 25, 4:08 pm, SHRISH MISHRA wrote: > @Chi > Have a look ofhttp://www.codechef.com/SNACKTST/problems/KNIGHT

[algogeeks] Re: knight moves in chess

2010-08-25 Thread Chi
(no path to T was > found). > > Great Minds Discuss Ideas > Average Minds Discuss Events > Small Minds Discuss People > Shrish Chandra Mishra > CSE NIT,Allahabad > > > > On Wed, Aug 25, 2010 at 8:25 AM, Chi wrote: > > This is a spacefilling-curve. Optimal so

[algogeeks] Re: knight moves in chess

2010-08-24 Thread Chi
This is a spacefilling-curve. Optimal solution is a Hilbert-Curve or a Morton-Curve. I have written one: http://sourceforge.net/projects/hilbert-curve/files. On Aug 25, 4:27 am, Algo geek wrote: > find the minimum no of moves by which a KNIGHT reaches the destination > from source in a 8x8 chess

[algogeeks] Re: Sorting algorithm

2010-08-23 Thread Chi
Time is measured in O(n^2) where n is the size of the string. Quicksort can do in O(n * log(n)) but it uses extra spaces on the stack, as most sorting method using recursion. On Aug 23, 12:36 pm, Subhranil Banerjee wrote: > Can anyone suggest a sorting algorithm that sorts in linear time without

Re: [algogeeks] Re: Longest Palindromic Substring

2010-08-23 Thread Chi Hoang
pe of > trie, but the difference lies in the intent. > > > On Sat, Aug 21, 2010 at 7:22 PM, Chi wrote: > >> Isn't that by definition a compressed trie, i.e patricia-tree, crit- >> bit tree (suffix-tree)? Or what is the difference? >> >> On Aug 20, 5:17 pm, Nikhil

[algogeeks] Re: solutions

2010-08-22 Thread Chi
It's a turing test. On Aug 22, 10:40 pm, Subhranil Banerjee wrote: > what are these solutions for -- 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

[algogeeks] Re: BFS

2010-08-22 Thread Chi
rd to read, and not very respectfull to the others. That's my opinion. Kind regards, Chi On Aug 22, 6:20 pm, Giri wrote: > by stacks i meant the usage of extra space.. recursion stack is > handled by the OS.. so it doesnt bother.. ok > > On Aug 22, 1:08 pm, "R.ARAVINDH&q

[algogeeks] Re: Longest Palindromic Substring

2010-08-21 Thread Chi
Isn't that by definition a compressed trie, i.e patricia-tree, crit- bit tree (suffix-tree)? Or what is the difference? On Aug 20, 5:17 pm, Nikhil Jindal wrote: > @chonku > As i understand, a trie is used when we have a lot of strings (such as a > dictionary). > Here we just have a single string.

[algogeeks] Re: Data Structure for URL matching

2010-08-19 Thread Chi
Hi Amit, are you some sort of a genius or what do I expect now!? Can you answer my question? Best regards, On Aug 17, 12:24 am, Amit Jaspal wrote: > http://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/t... > > Refer this link. > > > > On Mon, Aug 16,

[algogeeks] Re: BFS

2010-08-17 Thread Chi
Or do you mean without a recursion, without a stack!? On Aug 17, 7:40 pm, Chi wrote: > What you want is a php-traversal of a file-system: > > >http://devzone.zend.com/article/1235#Heading7 > > On Aug 17, 7:24 pm, Giri wrote: > > > the point here is not the language.

[algogeeks] Re: BFS

2010-08-17 Thread Chi
What you want is a php-traversal of a file-system: > http://devzone.zend.com/article/1235#Heading7 On Aug 17, 7:24 pm, Giri wrote: > the point here is not the language.. when you could understand what > those words mean, it serves the purpose.. then sorry itz Breadth First > Traversal ofa tree w

[algogeeks] Re: BFS

2010-08-17 Thread Chi
At least creative usage of a language. What is a BFS of a tree? On Aug 17, 6:39 pm, Dave wrote: > @Giri: Could anyone tell how to spell "could", "anyone", "how", and > "to"? > > On Aug 17, 11:23 am, Giri wrote: > > > Cud any1 tell hw 2 implement BFS of a tree without queue?! -- You received th

[algogeeks] Re: Data Structure for URL matching

2010-08-17 Thread Chi
tp://www.ahhf45.com/info/Data_Structures_and_Algorithms/resources/t... > > Refer this link. > > > > On Mon, Aug 16, 2010 at 10:29 PM, Chi wrote: > > I'm not sure what you want. I have post a solution to search for > > wildcards in tries. Now you claim to do it better with

[algogeeks] Re: Data Structure for URL matching

2010-08-16 Thread Chi
ry-tree version of the trie, then can you explain me the advantage of a ternary-search-tree? On Aug 15, 8:31 pm, Amit Jaspal wrote: > Seems a gud idea . > I have read we can do better with Ternary Search Trees .Can anybody has any > idea about it? > > > > > > On Sun, A

[algogeeks] Re: Data Structure for URL matching

2010-08-15 Thread Chi
What you need is a reverse trie dictionary. You may take a look at this: > http://phpir.com/tries-and-wildcards On Aug 15, 3:21 pm, amit wrote: > In our indexes, we have millions of URLs each of which has a link to > some page contents, that is, URL->contents. Now, suppose a user types > a query

[algogeeks] Re: Data Structure for URL matching

2010-08-15 Thread Chi
What you may need is a reverse trie. You may take a look at this: > http://phpir.com/tries-and-wildcards On Aug 15, 3:21 pm, amit wrote: > In our indexes, we have millions of URLs each of which has a link to > some page contents, that is, URL->contents. Now, suppose a user types > a query with w