Date: 06/16/06     Keywords: php

To select an optimal 32-bit hash function, I tested several different algorithms. I hope, the results would be useful for the community: http://vak.ru/doku.php/proj/hash/efficiency-en

Source: http://community.livejournal.com/algorithms/78204.html

Date: 06/15/06     Keywords: java

Speaking of zany sorting algorithms...
I've managed to put together one of my own (probably best to be thought of as a mental exercise), and I really am not too sure on how to analyze its time complexity. It takes a rather unique approach to get the job done. The basic concept of the sort is that it calculates the mean, estimates the variance, and then throws each value to where they would belong in the array if they were in a normal distribution (more specifically it plugs the value into a function equivical to the cumulative distribution function to return a value between 0 and 1, and multiplies that value by the total elements in the array (converts this to an integer) and places the value in the corresponding position in the array). It starts sorting at the first value, then sorts the value that it replaced. It marks when an element has been replaced. When an element is replaced, it flags the location. If a value tries to go into a location that is flagged, it compares the values, and moves the new value to the left or right acording to if it is less or greater than the previous value. If the value to the left or right is also flagged, it makes this comparison, and if the value is going to move back the way it came from, it instead takes that spot and shifts all the flagged values over the direction it was initially moving. There are also left and right borders, which once crossed force this shifting to go the other direction as there is no more room. The left and right border value becomes the last location that was shifted. If a value is placed on the border, the border shifts by one. When the left and right borders meet, the array is sorted.

Here is a link to some not so clean java code that implements this...
http://dayreader.com/foo/statSort.java

Certainly, hardware is not optimized for this kind of sort, but I still am curious as to what kind of time complexity it creates for larger sets, or if there is a way to eliminate the memory use.

Source: http://community.livejournal.com/algorithms/77941.html

Date: 06/15/06     Keywords: java

I know that a stable sort is a sorting algorithm that doesn't change the order of elements that are already in order.

What I don't understand is why this is so important. Because it seems like it shouldn't matter if elements that are equal are re-arranged in another equal order.

But I've seen and heard things which make me think there's an importance to stable sorts that I'm not getting. For example, the Java documentation from Sun says: "the algorithm used by sort does not have to be a mergesort, but it does have to be stable." So, clearly, it's regarded as being very important...

Source: http://community.livejournal.com/algorithms/77719.html

Date: 06/14/06     Keywords: no keywords

On this site which claims the author discovered a sorting algorithm faster than QuickSort?

Source: http://community.livejournal.com/algorithms/77526.html

Date: 06/07/06     Keywords: no keywords

Now I'm looking at this page on recursion, which contains the following the following text:

" Algorithms that are by nature recursive, like the factorial example above, can be coded either as a loop, as in the first example, or as a recursive function, as in the second example. However recursive functions are generally smaller and more efficient than their looping equivalents. "

So, I have two questions about this:
1. Is it really true that everything that one can code recursively can also be coded in an internal looping mechanism? I'm thinking of advanced recursion, such as that encountered when finding the optimal path down a tree, or finding the solution to the stable marriage problem. Without having named loops, it sure seems that there must be some tasks that can only be done with recursion.

2. "However recursive functions are generally smaller and more efficient..."

Huh? I thought recursive solutions almost always took up more space than their iterative counterparts, so this statement just doesn't make sense to me. Maybe someone knows something I don't.

Source: http://community.livejournal.com/algorithms/76936.html

Date: 06/07/06     Keywords: no keywords

I think it's sad when educational institutions have errors in their pages. Here is one on a SparkNotes page.

(The below code is not mine, it is copied from the above page.)

void print_permutations(int arr[], int n, int i)
{
    int j, swap;
    print_array(arr,n);
   
    for (j=i+1; j
Now, there is an error in the for loop where the j should be j++, but even more than that, the purpose of this function (supposedly) is to print all permutations of a data set. I traced it on paper and got 16 (instead of 24,the intended number) , so I figured I'd traced it wrong, and double-checked my work. Then I ran it in a compiler where I in fact got 16 results.

Now, I'm curious if I'm misunderstanding something very fundamental. Does "Let's write a function to take an array of integers and print out every permutation of it" have some meaning different than I think it does? Or is this "study guide" page really just spouting misinformation? Any idea on what the code is really supposed to look like?

Source: http://community.livejournal.com/algorithms/76631.html
	

Date: 05/28/06     Keywords: no keywords

I was just wondering how frequently treaps are used in practice. According to wikipedia, they were discovered recently in 1996. The definition is: " A treap is a binary search tree in which each node has both a key and a priority: nodes are ordered in an inorder fashion by their keys (as in a standard binary search tree) and are heap-ordered by their priorities (so that the each parent has a higher priority than its children)."

Source: http://community.livejournal.com/algorithms/76398.html

Date: 05/10/06     Keywords: no keywords

Anyone have papers on "Models for Distributed Authorization"?

Source: http://community.livejournal.com/algorithms/76262.html

Date: 05/03/06     Keywords: mysql, database, sql

I've got a large transition matrix (2000+ states) that is pretty sparse (most transitions are 0 probability). Right now I'm storing the thing in a MySQL database, and generating sequences based on the probability matrix is soooo slow.

There must be a more compact way to represent these transition probabilities, so that I don't have to do a query on a 2000+ row x 2000+ column database table every iteration of the system. But I don't know how.

Any thoughts?

Source: http://community.livejournal.com/algorithms/75944.html

Date: 04/16/06     Keywords: no keywords

I never really came to a sound understanding of Cantor's diagonalization argument (pops in a new window) in terms of it actually showing there are an uncountable number of total functions from N to N. While I intuitively know that there are an uncountable number of real numbers due to the existence of irrational numbers like the square root of 2, I was under the impression that Cantor did this without this assumption. Wikipedia’s version of the proof is entirely different from the book I was taught it from, and I’m not so sure about some of the steps it takes. So to ask questions about the version it presents, how is step 3 true? That is, how can we assume that each of the numbers in the range [0,1] can be represented by decimal expansion? It seems to me that this statement is not analogous to the assumption that the numbers are countably infinite (step 1). It seems to me that if you assume this, then you assume that you can create an infinitely unknown sequence of integers in the form of decimal expansion, which is analogous to the assumption of an irrational number.

http://en.wikipedia.org/wiki/Cantor%27s_diagonalization_argument

Source: http://community.livejournal.com/algorithms/75306.html

Date: 04/15/06     Keywords: no keywords

Our professor teased us that there is a way, in languages that have xor operators, to switch two variables without introducting a temporary variable. I can't figure out how to do it. Can anyone here?

And, to clarify, xor is true if either A or B is true, but not both. I'm not clear how it relates to the problem though, since I'm imagining that A and B can be any type of values...

Thanks for any pointers. Now I'm really rather curious. :-).

Source: http://community.livejournal.com/algorithms/75175.html

Date: 03/27/06     Keywords: software, database, asp, security, web

Hello

I am a software engineer in MA for a small internet company. Currently I am working on a webservices API our product and have been struggling with the authentication model. I read around and found an article that talked about WSSE authentication This seems relatively easy to implement and I kind of have a mock demo set up, but there is a problem with my demo, that I am not sure how to fix, as I am not a cryptologist and though I use crypt() and know how to compare a plain text password to a crypt encrypted password, more advance topics are beyond me. So this is my problem I will refer to the ideas in the article so I recommend you giving it a quick read.

In the artcle it discusses creating a "password digest" using a "Created Date" a "nonce" and the "password string". as a Base64 encoded sha1 string(i'll probably ise md5). the sha1 string is "nonce"+"created date"+"password string". They then pass the nonce and create date in the header and assume that you have the password on the other end and can piece it back together creating another sha1 string to compare it too and verify authentication.

I have a test ap, and here is the problem problem I am running into. Say I have my api, and I have a company writing an app to use it. I tell them to use the above method and to use crypt to create their password string from their user inputed password. I get their data parse the headers and have the 3 aspects. I decode the base64 string to the sha1 string, but when I compare them it fails. The problem being that they are not encrypted with the same salt when crypt was used. Therefore the encrypted password they put in their string is different than the encrypted version in my database. This can be fixed if they know my salt, but that's a security risk. So I am not sure how to get around this problem.

Suggestions?

Source: http://community.livejournal.com/algorithms/74647.html

Date: 03/19/06     Keywords: no keywords

I was looking at wikipedia's explanation of a normal distribution http://en.wikipedia.org/wiki/Normal_Distribution , and I was wondering how one would go about calculating the area under the curve algorithmically (aka a cumulative distribution function). Now I guess you would have to resort to an estimate, but what bothers me more is I can't begin figure out how one could get this kind of estimate in O(1) time due to the integral.

Source: http://community.livejournal.com/algorithms/74462.html

Date: 03/09/06     Keywords: php

I'm working on a major enterprise scheduling/asset management/kitchen sink application and recently ran into the common calculate x number of business days from given date problem. I had trouble finding a simple,concise algorithm to handle it on the net(i found plenty of ugly ones) so i decided to share the one I came up with - which is clean and seems to work nicely - with you guys. Any comments/improvements are much appreciated. This example is implemented in php. $offset is the number of business days ahead to calculate. $date is unixtime start date.

function increment_business_days($offset,$date){
                if($offset > 0){//if the offset is greater than 0
                        $dayofweek = date('D',$date);
                        if($dayofweek == 'Fri'){//if today is friday
                                $date += 259200;//add 3 days worth of seconds to push us to Monday
                        }else{
                                $date += 86400; //else add 1 days worth of seconds
                        }
                        $offset--;//decrement the offset
                        return $this->increment_business_days($offset,$date);//call me recursively
                }else{//else we have arrived at our end date, get outta here
                        return $date;
                }
        }

$date += 3600;//add an hour to compensate for daylight savings weirdness.

Source: http://community.livejournal.com/algorithms/74067.html

Date: 02/28/06     Keywords: no keywords

At least half of what I learn about computational theory is through dialouge.
This proves to me that Computer Science should not be exclusively limited to the domain of text and diagrams.

Has anyone found respectable Audio Streams on advanced CS topics such as algorithms, architecture, patterns, etc?


//-- (Not including MIT-OCW)

Source: http://community.livejournal.com/algorithms/73804.html

Date: 02/23/06     Keywords: no keywords

Anybody take me link where I can read about Game Theory with minimum math.(Sorry for English)

Source: http://community.livejournal.com/algorithms/73595.html

Date: 02/16/06     Keywords: no keywords

what is a common method for decision making algorithm ? For example in hiring process, there are multiple candidates but can only choose one (or couple). There are factors to consider such as grades, education degree , work experience, honor awards etc ... some are considered more important than others.

Fuzzy Decission tree is one of the methods comes to mind, any other ? And what most important is how I can tell whether a method is better than another ? Can I use Monte Carlo to do those statistic ?

Thanks,

Source: http://community.livejournal.com/algorithms/73226.html

Date: 02/12/06     Keywords: no keywords

i'm working on something vaguely inspired by grimson & stauffer's use of multiple gaussians to model the appearance at a pixel ("the" background subtraction paper in the computer vision literature). the basic algorithm is this:

• compute the mahalanobis distance from the current sample to each appearance model.
• if the minimum distance is sufficiently small, we have a match — update the model that matched best using exponential averaging to get the mean and (co)variance; otherwise create a new model with initially high (co)variance.

that's where the similarity between my stuff and grimson & stauffer's ends. what i see in low variance regions is precisely what one would expect — only one active model with fairly small (co)variance. however, in high variance regions, it does something unexpected — instead of creating multiple models with uniformly distributed means and moderate (co)variances, it creates very few models with really high variance. what frustrates me is that if i didn't clip the (co)variances, it would degenerate to a single model with such huge (co)variance that it's essentially a uniform distribution.

any thoughts on how to fix this? i suspect that what i want to do is pull the matching model slightly closer to the input point, then apply a single round of "charged particle" type thing where each pixel model tries to move a little bit away from all the others, then adjust the (co)variances to minimize overlap — sound reasonable?

Source: http://community.livejournal.com/algorithms/72967.html

Date: 02/05/06     Keywords: no keywords

question


In a program how do you use static_cast???


Any examples would be appreciated. like where do i put it and so forth.


thanks

Source: http://community.livejournal.com/algorithms/72788.html

Date: 01/30/06     Keywords: no keywords

I'm trying (and failing miserably) in trying to work out how the characters - ij4jkK can express the number 44.

Basically I'm just trying to decode it. But I've really no idea how to even begin doing so, so can anyone help/point me in the right direction?

I've a few examples of the encryption in action -

ij4jkK == 44
ijfjnj == 47
il6jg0 == 60
iipjmwkk7 == 363

I can program to some degree, can I write something to help me solve it?

Wasn't entirely sure where to post this, but um, please don't hurt me if it's bad place...


Thanks.

Source: http://community.livejournal.com/algorithms/72225.html